2020-10-21

Codeforces Round #677 (Div. 3) 出たよ～～～

https://codeforces.com/contest/1433
結果：ABCD4完、微冷え

A.Boring Apartments

1~10000まで部屋があるアパートで、1→11→111→1111→2→22→……と、ゾロ目のところにだけピンポンダッシュする。部屋ナンバーNの人が出たとき、今までピンポンダッシュした部屋のナンバーの桁数の和を求めるというやつ。
部屋ナンバーの末尾をA、桁数をBとすると $(A-1)×10+$ ( $1～B$ の和)ってなる。

B.Yet Another Bookshelf

N冊の本を収められる本棚があり、0のときは空で1のときは本が入っている。1回の操作で、本を右か左の空いている部分に移動させることができる。本を収納している部分を全て連続させたい場合、何回の操作が必要か、というやつ。
前から順に見て行って、最初の本が出てきてから空白を数える。次の本が出てきたら今までの空白を足して空白カウントを0にする。

C.Dominant Piranha

N匹のピラニアがいて、i番目のピラニアの大きさは $A_i$ 。一度の操作につき、左か右のピラニアが自分より小さい場合に、そのピラニアを食べることができる。共食いしたときに最後まで残るのは何番目のピラニアか、というやつ。
全てのピラニアの大きさが等しいとき、-1。そうでないときは、一番大きいピラニアの内左右いずれかの大きさがそれより小さいもの。

D. Districts Connection

N個の都市があり、i番目の都市には番号 $A_i$ が割り振られている。都市間にN-1本の道を作ることにする。割り振られている番号が同じ都市同士を直接繋がずに、すべての都市間の行き来を可能にすることはできるか。できる場合はその組み合わせを出力する、というやつ。
全ての都市の番号が同じとき、-1。そうでないときは、1番目の都市と番号が違う都市は全部1番目につなぐ→まだ使ってない都市について、また番号の違う都市に適当につなぐ……を繰り返したら通ったけど、なんで通ったのか微妙にわからない……。

E. Two Round Dances

まず問題文が読めなくて困る
n個ボールあるからn/2個ずつに分けて輪っかをつくるんだけど、輪っかの作り方は何通り？（byじゅぴろさん）（ありがとうございます！！）
$a(n) = (2*n + 1)!/(n + 1)$ らしいです。（OEISに投げた、ここのnはN/2）
これが大量に通されているのでへこむ

こどふぉ、出る前は出たくね～～って思うけど冷えてもあまり深刻に受け止められない分ちゃんと出て学びを得ていった方がいいなと思いました

2020-09-28

競プロキャンプ2020関西　参加記

※この記事では競技プログラミングについて何も書いていません

競プロキャンプ2020@京都 - connpass
9/26~27に↑に参加しました！とっても楽しかったです！
既に記憶がうろ覚えなので頑張って呼び起こしています　文章は支離滅裂なのでフィーリングで読んでください

1日目

12時に京都駅集合だけどみんな早く来ていて焦る　11時40分ごろにつくと既にたくさん人がいた　サンドイッチを食べてたらかわらさん・まつかわさん・モジャンボさんが来る　モジャンボさんがジャンボでびっくり……！！
京都駅から宇治に移動してレクへ
自己紹介中はいずらいとさんの隣に座ってました　髪の毛が超さらさらで無限にびっくり
「数探しゲーム」ではRyukiさん、かわらさんと同じチームでしたが全く役に立てず……　何問目かでかわらさんがFAを取っていてすげ～すげ～～となりました
次に落語を聞いてから「チーム対抗聖徳太子ゲーム」をやりました（1つお題を決めて、そのお題に沿った単語をチーム全員で一斉に叫び、回答者はそれを聞き取る……みたいなゲームです）　私のいたチームではお題を「お菓子」にして、じゃがりこ・ジャガビー・ポッキーなどなどに加えて「タラタラしてんじゃねーよ」を入れました　まつかわさんに力の限り叫んでもらったところ、全チームがタラタラryしか聞き取れていなかったので作戦勝ちです（？）（まつかわさんに怒鳴られたらムッチャ怖そう、それはそう）

レク施設を出たあとは、駅でのいみちゃん・じゅぴろ・Hyadoくん（全員Topcoderに出てた）と合流
じゅぴろがのいみちゃんを指さして「こいつめちゃくちゃ邪悪だわ」と叫んでいたので不安になる
宿泊施設にはタクシーで向かいました　タクシー待ちの間にkichiさんとのいみちゃんが対面　のいみちゃんに名乗るのをためらうkichiさんを見てめっちゃ笑うなどしました（最悪）

宿泊施設に着いて、雨が小降りになってからBBQを始めたんですが、この時点でかなり時間が押していました　各々の荷物を分解してBBQの材料を分ける段階でもかなり時間がかかってしまい、お酒を飲みながらお腹すいた～と叫んでいました（準備もちゃんと手伝ってました！）（弁明）
酔っぱらってきて運営お手伝いのkakiraちゃんさんに「カワイイ～～～～～～～～」って絡んだら年上で死ぬほどビックリしました　本当にすみませんでした
そこそこお酒が回っていたものの、「ratedなのに出ないとかあるか？」というじゅぴろ大師匠の圧に負けて、肉数枚とお菓子ちょっとを食べた時点でBBQを離脱することに……(´;ω;｀)（誤解のないように言うとじゅぴろさんは他の参加者にはそんなハラスメントはしてません）
しかも施設の風呂が21:30までだったので、BBQを20時過ぎに抜けた後10分で風呂に入り、髪の毛も乾かさずACLBCに出ることに　女子部屋は私のみなのにかなり広かったため、ありがたくじゅぴ・かわらと占領させてもらいました（途中でまつかわさんやのいみちゃんも来た）

スギノキ「イケメンにすっぴん見せたくなかったな……」
のいみちゃん「いいからコンテストに集中してください（正論）」

コンテストは3完微増なので冷えはしなくてよかったです。

終了後はじゅぴ・ノキ・かわら・まつかわ・のいみ・Hyado・沙耶花（・きたむーくん）で「インサイダー」というボドゲをやりました　
後からふるやんさん・いずらいとさん・（武雄さんとかもいらっしゃった気がする？）など、さらにたくさんの人が来て、まつかわさんが出題者になってくれて「ウミガメのスープ」をやりました　文系なので（？）結構解けてたのしかったです（？！）
そのあとは雑談してるうちにかわらさんが床で寝落ち、じゅぴのいみノキも床で寝落ち……という感じで、死体が床にごろごろと転がる

2日目

朝起きる・ご飯食べる
スギノキ「のいみちゃん一人だけ最後まで寝てたね」
のいみちゃん「寝てる間にスギノキさんに1、2回蹴られました」
緑なのに　ころされる　ごめんなさい

BBQの片付け＆部屋を出た後、2時間の自由時間に
歩いて20分のところに展望台があるそうなんですが、疲れていたので私には無理だなとなる
じゅぴろ「バチャやるか」
マ～～～～～～～～ジで言ってる？突発的にCodeForces#498（Div.3）のバチャが立つ（緑が私だけで、橙・青等がたくさんいるにも関わらず、Div.3を選んでくれたのはめちゃめちゃ配慮してもらったと感じているので本当にありがとうございます……）
最初は5人くらい？でバチャするか～みたいなノリだったのに、気づいたら10人以上集まっていて、やっぱりみんな競プロ好きなんだな～とおもいました
いざやってみるとBが解けなくてえーってなる　Bは通したけどCは間に合わず　（Div3にしては）ちょっと難しかったらしいです　精進不足……　
バチャが始まってすぐに、幹事の方から「ゴミ捨てを手伝ってくれる人が2人欲しい」と言われたんですが、のいみちゃんとじゅぴろが「ハンデあげるか～」といって快くそちらへ向かったのを見てかなり社会性を感じました（すごい）

自由時間の後は喜撰茶屋でお昼ご飯を食べる　ここでdokinさんなど2日目だけ参加の人と合流
なんか修学旅行？の学生にめっちゃガン見されて笑われてたらしいです、気づかなくてよかったぜ（？？）
ここで閉会式なども行って、一度解散のような形になりました

スギノキ「平等院鳳凰堂見たいね」
かわら「別に 10円玉に書いてあるやん」
じゅぴろ「全く同じことをHyadoも言ってたよ」
社会性の見分け方です　参考にしてください！
結局、かわらさんの財布には10円玉がなかったので平等院鳳凰堂に行きました（？）　誰が作ったんだっけ？藤原のなんとか？とか言ってたらふるやんさんが「藤原頼通だよ」と教えてくれて知性の差を感じました……ウ

Hyadoくんはチームで出たい5時間バチャがあるため？、平等院はテキトーに見て、カフェ的なところに入る
じゅぴ・ノキ・のいみ・かわら・まつかわ・沙耶花・Hyado・ふるやん・dokin・しんちゃんでのんびりだべりました
議題：関西人全員うるさい問題・関東では冗談のハードルが鬼高いという噂・かわらさんは別に静かではなくない？（byのいみちゃん）・ラブライブ！の女は絶対百合じゃないだろという提案（byスギノキ）
私が高専在学時に問題を起こしてた先生を明石高専のしんちゃんくんも知っていて親近感がわきました（明石から期間限定で奈良に来ていた先生だったため）

帰りは京阪組とJR組に分かれて、のいみちゃん・じゅぴろと京橋でラーメンを食べました　ふっぴーさんは邪悪って聞いたけどほんとですか？（？）

総括

・いずらいとさん、ふるやんさんなど話したことがない方と話せて非常によかった
・キャンプで食べれなかった分の肉はじゅぴろにたかっていいらしいです！やったー！
・幹事のみなさん、参加者の方、本当にありがとうございました

2020-09-17

お布団を温めた初チーム戦（WUPC2020＆HUPC2020 1日目）感想

WUPC2020

https://onlinejudge.u-aizu.ac.jp/beta/room.html#WUPC2020/
早稲田生による有志コン、WUPC2020にれたすさん（@fairly_lettuce）、mo3tthiさん（@mo3tthi）とチーム「melomelody」で参加しました。
チーム戦が初めてなうえに二人とも初めて話す人（mo3tthiさんはFF外）で、しかも私だけメッチャレートが低い（れたすさんは水、mo3tthiさんは青）だったのでビビってましたが、お二人ともすごく気さくな方でした。
結論から言うととにかく足を引っ張りまくってしまったんですが、とても勉強になりました。早稲田の方たち、そして組んでくれたお二人ありがとうございました……。
最初は私がAやる→れたすさんがBやる→その間にmo3tthiさんがC以降を読んで解けそうな問題を探す、という方針を立ててもらいます。Aを出したらCE。なんで？！（using Graph = vector>;を消したら直りました、C++17で提出しなかったことが原因かも）
れたすさんがBを実装している間に後ろから問題文を読み進めていきます。Mはやることは分かりやすい気がする（？）木グラフの問題だったんですが、ぱっとイイ感じの実装方針は全く思い浮かばず、一回どっかからBFSなりしてどうしたらいいんだろう？とか考えてました。次に見たLは自分の手に負える見た目ではなかったのですぐに諦めました。KはLより問題文の意味は理解できたけど、解き方が全く思い浮かばなくてこれも飛ばします。mo3tthiさんがIまで読んでくださってたのでここで合流します。

以下、かなり記憶があやふやなので時系列が間違ってるかも
mo3tthiさん「Fはいけそうです、よければスギノキさんどうですか（菩薩）」
スギノキ「じゃあF見てみます、後ろ三問だとMが難しくなさそうに見えました」←ほんまか？？？
Fを見てみると、2のべき乗をイイ感じにイイ感じすればACできそうなのはそうなんですが、細かいところは全然わかりません。ここでmo3tthiさんが大まかな方針を説明してくれるんですが、私がテンパりまくっていて、死……。結局、Cを解き終わったmo3tthiさんが実装してくれます（ほんとにすみません）。あとから3人で解説見て、「2のべき乗全部見ても全然間に合うんだな～～～」とへこむなどしました。
私がFを見て布団を温めている間に、Mは1回移動するごとに変動する距離はたかだか1だから何とかなるはず、と言ってれたすさんが頑張ってくれます。

mo3tthiさん「GはDPなんですが、スギノキさんはDP得意ですか」
スギノキ「えっとえっと緑コーダー並みって感じです」←ほんまか？？？？？？？
「休憩とか考えないで普通にDPした場合」の結果を利用してあれこれできないかな、と思ったんですが、私が思いついたのは「普通にDPした場合のやつに上書きして、i分目から休憩した場合～」みたいなわけのわからん考え方だったので普通に却下です。次に、mo3tthiさんが「休憩回数を決め打ちしてdpするのはどうですか」と言ってくれて、そこから実装してくれますが通らず……。
スギノキはとくに何の役にも立てないまま5時間が経過しました。
ここで、DPを雰囲気でしかやってきてないなという気づきと反省が生まれます。DPぽいなと思ったときは実装しながら添え字ガチャ！（素振り）てなことをしているので、私には緑並みどころかDPパワーは全くないのでした。DPバチャなどできる範囲で苦手意識を克服する努力はしていたつもりだったんですが、いざやってみると全く身についていないなと感じました。

HUPC2020 Day1

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2020Day1/info
ntkさん（@ntk_ta01）、SEELさん（@Seadogg012）という、レートが近く個人的に気になっている二人とチーム「grin」で参加することができました。3人ともレートが緑中盤くらいという感じです。一応現在のレート順にかんがみて（？）SEELさんがA→スギノキがB→ntkさんがCという方針を立てました。

SEELさんがAを通してくれたあとも、私はBが全然解けていませんでした。
スギノキ「全くわからないです」
ntkさん「この記事どうでしょう」
↓つるさんの「imos 法を線形代数で理解・一般化して，フィボナッチ数列でも足せるようする」記事
https://theory-and-me.hatenablog.com/entry/2020/08/23/182712
スギノキ「全く、分からないです……（勉強不足のため）」
しかしimos法でやれるっぽいことは分かりました。ここで「区間に等差数列を足す　imos法」でググります。
↓アルメリアさんの記事「等差数列の重ね合わせを求める」章
https://betrue12.hateblo.jp/entry/2019/10/19/163736
完全に答えが載っています！やった～～～～～～～！！！！！！！！！！！！！！！ここでなぜか実装をバグらせますが（は？）ntkさんが直してくれてACしました。

次にCについて全員で考えてみます。
ntkさんの、Nが小さい場合とそうでない場合で分けてみるのはどうか、というのを聞いて確かに～～～ってなり、とりあえず小さい場合のbit全探索を書きます。小さい場合は通りました。
大きい場合については審議するうちに「N>18くらいから、答えが一意に定まることはなくなるよね」という話になり、そこから「前20桁くらいだけ見ればよくない？？」と、答えに大きく前進します……！
小さい場合と似たような感じのコード（余った桁はアスタリスクで埋める）を書きましたがTLE。ここで実装をSEELさんに代わってもらいましたが、結局TLEは取れずじまいでした。あとから考えると、私の書いていたコードはN=40の場合1000000*60000くらい計算することになるのでぜ～～～～～～～～～～んぜん間に合ってないんですが、その時は分からなくて首をかしげていました……。

結果は2完でしたが、近いレートの人たちとあれこれ話しながら問題について考えることができた（かつ、3時間なので集中力のない私でも最後まで考え切れた）のでとても楽しいコンテストでした。同じ大学に競プロやってる人がいないので、ICPCとかには全然出られないんですが、こういう有志コンで積極的にチーム組んでいきたいな～って思いました。あともっと強くなってさわれる問題を増やしたいな……となりました。完。

2020-09-07

Codeforces Round #668 (Div. 2) 出たよ～～～～

約2か月半ぶりのこどふぉ、Div.2に参加しました。結果は2完（A,B）で緑落ちです。超絶自業自得……。Dまでは他の人に教えてもらったのでブログに残そうと思います。
コンテストURL：https://codeforces.com/contest/1405

A. Permutation Forgery

問題概要

$1$ ～ $N$ までの整数で、要素の重複なく構成された長さ $N$ の数列に対応して、以下の $N-1$ の長さの数列 $F(p)$ を作ります。
$F(p)=sort(p_1+p_2,p_2+p_3,…,p_{n−1}+p_n)$
$F(p)$ が等しく、かつ $P_i \neq P'_i$ である長さ $N$ の数列をひとつ出力してください。

考え・反省

$F(p)$ が等しくなるためには、ペアになる要素が元の数列と同じである必要があります。たとえば $N=3$ だったら1個目+2個目、2個目+3個目がペアになって長さ2の数列になります。合体後の順番はソートされるので、数列をreverseするだけで通ります。
↑数列を反転させれば通るのに、サンプルを見てものすごく悩んでしまって嘘解法を投げました（懺悔）

B. Array Cancellation

問題概要

$A_1+A_2+...+A_n=0$ となるような、長さ $N$ の数列が与えられます。この中から一度の操作につき $i$ 番目と $j$ 番目の要素を選び、 $i$ 番目の要素に $1$ を足し、 $j$ 番目の要素から $1$ を引きます。 $i < j$ であった場合にはコストがかからず、そうでない場合には1回の操作で1コストかかります。
数列の要素を全て $0$ にするために必要な最小のコストを求めてください。

考え・反省

「今まで出てきた正の数の和」を持っておき、もし負の数が出てきたらそこから引いていきます。これを最後まで繰り返すと、数列の和が0になることから、「残った負数の和」と「残った正数の和」は等しいので、その絶対値を出力します。
↑ $A_1+A_2+...+A_n=0$ という条件を見逃していて、無限に不可能なパターンについて考えていました。涙。

実装（折りたたんでいます）

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
  int Q;
  cin >> Q;
  for( int q = 0; q < Q; q++ ){
    int N;
    cin >> N;
    vector<int> A(N);
    int plus = 0;
    for( int i = 0; i < N; i++ ){
      cin >> A[i];
      if( A[i] > 0 ){
        plus += A[i];
        A[i] = 0;
      }
      else{
        if( plus+A[i] >= 0 ){
          plus += A[i];
          A[i] = 0;
        }else{
          A[i] += plus;
          plus = 0;
        }
      }
    }
    cout << plus;
    cout << "\n";
  }
}

C. Balanced Bitstring

問題概要

$0,1,?$ だけで構成された長さ $N$ の文字列が与えられます。 $?$ には $0,1$ の好きな方を選んで置換します。この文字列の中から連続した $K$ 個（ $K$ は偶数）を取り出した際、どの部分でも $0$ と $1$ の個数が等しくなるようにすることはできますか？

考え・反省

modごとに見るということを全く思いつきませんでした（反省）。
$mod K$ で等しくなる部分の文字がすべて同じで、かつ最初の $K$ 個が条件を満たしていればYES、そうでなければNOです。
たとえば $S=11001100$ で $K=4$ のとき、最初の $K$ 個は「 $1100$ 」で、1個右にずらした部分から $K$ 個取ると「 $1001$ 」です。最初の $K$ 個が条件を満たしていてくれれば、抜き出す部分を1個右にずらした際に新しく部分文字列に入った文字（右端）と、左端にあった捨てる文字が等しいことで、1と0の数の均衡を保てます。
もし最初の $K$ 個の中に $?$ が含まれていた場合は未確定にしておいて、途中で $0$ か $1$ が出てきたら確定させます（そして確定後の文字列が条件を満たすか確認します）。

実装（折りたたんでいます）

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
  int Q;
  cin >> Q;
  for( int q = 0; q < Q; q++ ){
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    bool fg = 1;
    vector<char> num(K, '?');
    int sum = 0;
    int hatena = 0;
    for( int i = 0; i < K; i++ ){
      if( S[i] == '0' ) sum--;
      else if( S[i] == '1' ) sum++;
      else hatena++;
      num[i] = S[i];
    }
    if( abs(sum) > hatena ) fg = 0;

    for( int i = K; i < N; i++ ){
      if( num[i%K] == '0' && S[i] == '1' ) fg = 0;
      else if( num[i%K] == '1' && S[i] == '0' ) fg = 0;
      if( num[i%K] == '?' && num[i%K] != S[i] ){
        num[i%K] = S[i];
        hatena--;
        if( S[i] == '1' ) sum++;
        else sum--;
        if( abs(sum) > hatena ) fg = 0;
      }
    }
    if( fg ) cout << "YES\n";
    else cout << "NO\n";
  }
}

D. Tree Tag

問題概要

AliceとBobは $N$ 頂点の木グラフ🌲の上で鬼ごっこをします。最初はAliceが頂点 $A$ 、Bobが頂点 $B$ にいて、Alice→Bobの順番で移動します。一回の移動でAliceは最大 $dA$ 、Bobは最大 $dB$ の距離を移動できます（ここでの距離とは頂点間の辺の数を指します）。この移動を $10^{100}$ 回する間に、AliceがBobと同じ座標に辿り着けたらAliceの勝ち、そうでなければBobの勝ちです。鬼ごっこの勝者を出力してください。

考え

$10^{100}$ 回移動できる＝いちいち二人の動作を追ってたら絶対に間に合わないので、何かしらの条件があるはず。移動回数が多い分Aliceが有利な気がする（？！）ので、「どうやったらBobが勝てるか」で少し考えてみます。

初期配置で、Aliceとの距離が $dA$ 以上離れてないとダメ（最初の1手でAliceに追いつかれてしまうため）
木の直径がある程度大きくないとダメ（Aliceがどの頂点にも1手で移動できる状態になると詰むため）

→「ある程度」がどのくらいか？を考えます。ちょうどグラフの真ん中らへんに立てば、木の直径が $2*dA$ 以下だとAliceはどこにでも行けてしまうので、それより大きい必要があります。

$dB > 2*dA$

→これ教えてもらうまで理解できませんでした……。
まず、頂点の数よりも移動可能回数のほうがずっと多いので、Bobは逃げ回るときに「Aliceのいる方向」へ逃げないといけない状況が生じます。その際、Bobの移動可能距離がAliceの「1手で移動可能な範囲」よりも大きければ、つかまってしまうゾーンを「飛び越えて」逃げ回ることができます。逆に、それよりBobの移動距離が小さい場合はどこかでAliceが1手で移動できる範囲に入らざるを得ず、捕まってしまいます。

実装（折りたたんでいます）

#include <bits/stdc++.h>
#define int long long
using namespace std;
using Graph = vector<vector<int>>;

signed main(){
  int Q;
  cin >> Q;
  for( int q = 0; q < Q; q++ ){
    int N, A, B, DA, DB;
    cin >> N >> A >> B >> DA >> DB;
    A--; B--;
    Graph G(N);
    for( int i = 0; i < N-1; i++ ){
      int a, b;
      cin >> a >> b;
      a--; b--;
      G[a].push_back(b);
      G[b].push_back(a);
    }

    //木の直径を求める
    vector<int> dist(N, -1);
    queue<int> que;
    dist.at(A) = 0;
    que.push(A);
    while( !que.empty() ){
      int v = que.front();
      que.pop();
      for( int nv : G.at(v) ){
        if( dist.at(nv) != -1 ) continue; //すでに通っていたらスルー
        dist.at(nv) = dist.at(v)+1;
        que.push(nv);
      }
    }

    int start = 0;
    int k = 0;
    for( int i = 0; i < N; i++ ){
      if( k < dist[i] ){
        k = dist[i];
        start = i;
      }
    }

    vector<int> ponyo(N, -1);
    ponyo.at(start) = 0;
    que.push(start);
    while( !que.empty() ){
      int v = que.front();
      que.pop();
      for( int nv : G.at(v) ){
        if( ponyo.at(nv) != -1 ) continue; //すでに通っていたらスルー
        ponyo.at(nv) = ponyo.at(v)+1;
        que.push(nv);
      }
    }

    int dia = 0;
    for( int i = 0; i < N; i++ ) dia = max(dia, ponyo[i]);
    if( dist[B] <= DA || dia <= 2*DA || DB <= 2*DA ) cout << "Alice\n";
    else cout << "Bob\n";
  }
}

競プロなんもわからん！解散！

2020-05-12

Codeforces Round #640 (Div. 4) DETAYO~~~~~~~~

Div.4に参加しましたが、結果はさんざんでした（大反省）
コンテストURL：https://codeforces.com/contest/1352

A. Sum of Round Numbers

問題概要

左端（一番大きい桁）以外が0の数（例：4000、1、9、800）を「丸められた数」とします。クエリ数 $t$ と正の整数 $n$ が与えられるので、「丸められた数」の和で $n$ をあらわすとき、必要な「丸められた数」の最小の個数と「丸められた数」を求めてください。

考え

「 $n$ を10で割ったあまり」をvectorに格納しつつ、 $n$ が0になるまで10で割っていきます。そのあと、格納された数が0でない場合は桁数を見て10を掛けて出力します（とは書いたけどとてもバグらせました……）。

実装（折りたたんでいます）

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N;
    cin >> N;
    vector<int> num;
    int now = 10;
    while( N > 0 ){
      num.push_back(N%10);
      N/= 10;
    }
    int ans = 0;
    for( int i = 0; i < num.size(); i++ ){
      if( num.at(i) != 0 ){
        ans++;
        num.at(i) *= pow(10, i);
      }
    }
    cout << ans << endl;
    for( int i = 0; i < num.size(); i++ ){
      if( num.at(i) == 0 ) continue;
      cout << num.at(i) << " ";
    }
    cout << endl;
  }
}

B. Same Parity Summands

問題概要

正の整数 $n, k$ が与えられます。数列 $A_1, A_2, A_3, ..., A_k$ がすべて奇数、またはすべて偶数である場合に、その和を $n$ にすることが可能か判定してください。可能な場合はそのような数列を1つ出力してください。

考え

全部奇数にする場合は最後以外1、全部偶数にする場合は最後以外2にして、一番最後の数で帳尻を合わせればいいです。どちらでも帳尻を合わせられない場合は和を $n$ にすることができません。
全部奇数にするときは $k-1$ 個の1で $A_1～A_{k-1}$ を埋めて、 $A_k$ に入れる $n-(k-1)$ が正の奇数になる必要があります。全部偶数にするときには $k-1$ 個の2で $A_1～A_{k-1}$ を埋めて、 $A_k$ に入れる $n-2 \times (k-1)$ が正の偶数になる必要があります。

実装（折りたたんでいます）

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N, K;
    cin >> N >> K;
    
    if( (N-(K-1))%2 == 1 && N-(K-1) > 0 ){
      //すべて奇数にする場合
      cout << "YES" << endl;
      for( int i = 0; i < K-1; i++ ) cout << 1 << " ";
      cout << N-(K-1) << endl;
    }else if( (N-2*(K-1))%2 == 0 && N-2*(K-1) > 0 ){
      //すべて偶数にする場合
      cout << "YES" << endl;
      for( int i = 0; i < K-1; i++ ) cout << 2 << " ";
      cout << N-2*(K-1) << endl;
    }else cout << "NO" << endl;
  }
}

C. K-th Not Divisible by n

問題概要

正の整数 $n, k$ が与えられるので、 $n$ で割り切れない正の整数のうち $k$ 番目のものを出力してください。

考え

「小さいほうから $a$ 個見た場合、 $n$ で割り切れない数は $b$ 個含まれる」
上記は $a$ が大きくなるほど $b$ も大きくなる（＝単調性がある）ので二分探索で求めることができるみたいです。「 $n$ で割り切れない数の個数」を求めるには、 $a$ 個の数の中から $n$ の倍数だけを抜けばいいので、 $b = a-(a \div n)$ ということになります。

実装（折りたたんでいます）

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N, K;
    cin >> N >> K;
    int ok = 10e12;
    int ng = 0;
    while( ok-ng > 1 ){
      int mid = (ok+ng)/2;
      if( mid - (mid/N) >= K ) ok = mid;
      else ng = mid;
    }
    cout << ok << endl;
  }
}

算数（数学）orエスパーで $O(1)$ もできます（本番中はこっちだった）

実装（折りたたんでいます）

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N, K;
    cin >> N >> K;
    int A = N*K;
    if( A%(N-1) == 0 ){
      cout << A/(N-1)-1 << endl;
    }else{
      cout << A/(N-1) << endl;
    }
  }
}

D. Alice, Bob and Candies

問題概要

飴が $n$ 個並んでいて、左から $i$ 番目の飴の大きさは $a_i$ です。アリスは左から、ボブは右から、交互に飴を食べるゲームをします。自分の番の時、（一番最初のアリスの時以外は）「直前に相手が食べた飴の大きさの合計」より大きくなるように、1つ以上の飴を食べる必要があります。飴がなくなったら終了です。ゲームの総ターン数と、アリスとボブそれぞれが食べる飴の個数を出力してください。

考え

dequeを使って、アリスのターンの時は前から、ボブのターンの時は後ろから飴を取っていけばいいです。

実装（折りたたんでいます）

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N;
    cin >> N;
    deque<int> dq;
    for( int i = 0; i < N; i++ ){
      int A;
      cin >> A;
      dq.push_back(A);
    }
    
    bool fg = 1; //0のときalice
    int alice = 0;
    int bob = 0;
    int K = 0;
    int now = 0;
    int ans = 0;
    while( !dq.empty() ){
      if( fg ){ //aliceのとき
        now += dq.front();
        alice += dq.front();
        dq.pop_front();
        if( now > K ){
          K = now;
          fg = 0;
          now = 0;
          ans++;
        }else if( dq.empty() ) ans++;
      }else{
        now += dq.back();
        bob += dq.back();
        dq.pop_back();
        if( now > K ){
          K = now;
          fg = 1;
          now = 0;
          ans++;
        }else if( dq.empty() ) ans++;
      }
    }
    cout << ans << " " << alice << " " << bob << endl;
  }
}

E. Special Elements

問題概要

数列 $a_1, a_2, ..., a_n( 1 \leq a_i \leq n )$ が与えられます。 $a_i = a_l + a_{l+1} + ... + a_{r}(1 \leq l < r \leq n)$ であるような $a_i$ の個数を求めてください。

考え

連続する部分数列の和と等しい $a_i$ はいくつありますか？ということなので、まずは累積和をします。lとrの位置をそれぞれ全探索して一通り部分数列の和を求めた後、 $a_i$ と等しい数があるか見ます。~~8000*8000なので、TLEはしなくてもメモリが不安な気持ちになるようなならないような（？）~~ $a_i$ が最大でも $n$ であることから、vectorのサイズは $n+1$ で十分です。じゅぴろさんありがとうございました……。

実装（折りたたんでいます）

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
  
  cin.tie(0);
  ios::sync_with_stdio(false);
    
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N;
    cin >> N;
    vector<int> A(N);
    for( int i = 0; i < N; i++ ) cin >> A.at(i);
    vector<bool> num(N*N+10);
    vector<int> R(N+1);
    for( int i = 0; i < N; i++ ) R.at(i+1) = R.at(i) + A.at(i);
    
    for( int i = 0; i <= N; i++ ){
      for( int j = i+2; j <= N; j++ ){
        num.at(R[j]-R[i]) = 1;
      }
    }
    
    int ans = 0;
    for( int i = 0; i < N; i++ ){
      if( num[A[i]] ) ans++;
    }
    cout << ans << endl;
  }
}

F, G なんもわからん（就寝……）

2020-04-07

競プロお役立ちサイト・ツール

AtCoder Problems以外にも競技プログラミングで役に立つサイトやツールがあるよ～！という紹介記事です。競プロを始めたばかりで、これからたくさん精進したい！という方向けです（全部知ってるわ～という方は、「これ追加したほうがいいよ！」というものがあれば、ぜひ教えてください……）。

AtCoder Scores
AtCoder Rivals
ac-predictor
AtCoder Submission User Colorizer
CF-Predictor
Rating History
AC Logger

AtCoder Scores

atcoder-scores.herokuapp.com

サイト上部「精進グラフ」のリンクを押して、IDを入力することで「レーティングと解いた問題の点数の合計（割る100）」を見ることができます（下画像参照）。

f:id:nokiyade:20200407172614p:plain

細い線が精進グラフ、太い線が実レートです。IDを複数入力することで、他の人の精進グラフと見比べることもできます。

AtCoder Rivals

atcoder-rivals.herokuapp.com

ライバルのIDを登録することで、コンテストごとにライバルと成績を比較出来たり（下画像参照）、ライバルの提出一覧をまとめてみることができます。

f:id:nokiyade:20200407171110p:plain

レートの近い人を登録しておけば、どの過去問を解くか悩んだ時の参考にもなるし、モチベーションも上がります！

ac-predictor

ac-predictor.azurewebsites.net

コンテスト中、現時点でどの程度パフォーマンスがあるのか確認できるユーザースクリプトです。サイト上部にある「インストール」を見ての通り、ユーザースクリプトを実行できる環境を用意する必要があります。

インストールして、ac-predictorを有効にすると、AtCoder上でのみ下画像のように「有効」となります。

f:id:nokiyade:20200407173701p:plain

コンテスト中、順位表からパフォーマンスとレート変動（多少の誤差あり）をリアルタイムで確認できるようになります。

f:id:nokiyade:20200407173857p:plain

AtCoder Submission User Colorizer

greasyfork.org

AtCoderの提出一覧で、ユーザーの色が一目で分かるようになるスクリプトです（下画像参照）。上のac-predictorと同じく、ユーザースクリプトを実行できる環境が必要です。

f:id:nokiyade:20200407175100p:plain

「もっと分かりやすい書き方はないかな？」と強い人のコードを読みたい場合や、解けない問題で同レート帯の人のコードを見たい場合に役立ちます。

CF-Predictor

cf-predictor-frontend.herokuapp.com

ac-predictorのこどふぉ版で、Codeforcesのコンテスト中にレート変動をリアルタイムで確認できます。Chromeの場合、Chromeウェブストアからインストールできるため、ユーザースクリプトの実行環境は不要です。

Rating History

rating-history.herokuapp.com

一番上のリンク「Rating History」から、TopCoder・Codeforces・AtCoder・AOJ・yukicoderでのACを足し合わせた総AC数を確認できます。ツイートリンクもあるため、キリのいい数字で適当にツイートして、AC数を記録することもできます。

AC Logger

aclogger.herokuapp.com

AtCoder Problems等にあるHeatmapをAtCoder・CodeForces・AOJ・yukicoderの合計ACで見ることができます。

f:id:nokiyade:20200407180008p:plain

また、「今日ACした問題」や「過去にACした問題」を時系列順に、サイト関係なく並べて見ることができます。

f:id:nokiyade:20200407180205p:plain

以上です。ちょっとずつ増やしていけたらなと思います。何か誤った記述等あればできる限り迅速に直しますので、ご指摘お願いいたします。

2020-03-13

Codeforces Round #627 (Div. 3) 出たで

コンテストの感想を書いたことないなーと思ったので書きます！

普段より早い時間で参加しやすかったので、Codeforces Round #627 (Div. 3)に出ました。まだHack時間中だけど多分3完です。

Problem A Yet Another Tetris Problem

URL：https://codeforces.com/contest/1324/problem/A
問題文が読みづらくてちょっとビビりました。上から高さ2、幅1のブロックが降ってきます。テトリスとあるように、横一列にブロックが揃うと消えます。幅（要素数）と高さが初期値として入力で与えられるので、ブロックを降らせていって全部消すことができますか？みたいなことが書いてあります（多分）。
読解できたら問題は簡単で、要素同士の高さの差が奇数の場合は2*1のブロックで埋めることができないのでNOを出力します。

Problem B Yet Another Palindrome Problem

URL：https://codeforces.com/contest/1324/problem/B
「Palindrome」って単語めっちゃかっこいいですね。翻訳されなくてググったら回文って出てきました。数列が与えられるので、部分数列（連続していなくてもよいが順番を並び変えてはいけない）に回文数列（1 2 1みたいな）が含まれていますか？という問題。hackフェーズで落ちてしまいました。泣いてええか？
mapでそれまで出てきた数字を管理して、今見ている数字が2回以上出てきてたらYES（1 1 1 みたいな回文数列が作れる）、1回出てきている場合は直前の数字が今見ている数字と違えばYES（1 2 1みたいな）を出力します。

Problem C Frog Jumps

URL：https://codeforces.com/contest/1324/problem/C
「L」と「R」からなる文字列が与えられ、Lにいるときは左に、Rにいるときは右に移動できます。一番右（文字列の長さNに対してN+1番目）を目指すとき、カエルが一度に移動できる最短距離はいくつですか？みたいな問題です。何でかは分からないんですが（は？）Lを踏んでも無駄っぽいのでRまでの最長の距離+1が答えになります。コンテスト中はこっちのほうがHackされるかもと思っていました……（理屈がわかってないため）

Problem D Pair of Topics

URL：https://codeforces.com/contest/1324/problem/D
要素数Nの数列Aと数列Bが与えられるので、i番目とj番目を選んだ時、A[i]+A[j]>B[i]+B[j]となる組み合わせはいくつありますか？という問題です。AとBの差が大切ぽいのは分かるので、A-Bを配列Cに入れていきます。Cを小さい順に並べたとき、たとえばC[0]が-5だったら、5より大きい数字と組み合わせることで条件が達成できます。「配列C内にホニャララより大きい要素が何個あるか」は二分探索で求められるので、C.end() - upper_bound([今見てるやつより一個後ろのイテレータ], C.end(), 今見てる数字)を答えにどんどん足していけばおっけーです。今見てるやつより一個後ろのやつから探し始めることで、重複して数え上げてしまうのを防げます。

ProblemE & Problem F なんもわからん
こどふぉ　なんもわからん
全人類オヤスミ太郎