第一回日本最強プログラマー学生選手権-予選-

コンテスト前36.4、コンテスト中36.7と、いい感じの体温。C問題のバグがわからなかったのは残念だが、久しぶりに普通のコンテストができた。

A - Takahashi Calendar

問題文が表示されるまでに45秒くらいかかった。難しそうな見た目のくせに書くだけ。

B - Kleene Inversion

300点で転倒数とはたまげたなあ（企業コンではよくある）。まあ簡単そうだというのはわかる。K個の領域に分けて考えると、同じ領域内での転倒数は普通の転倒数のK倍、違う領域のは自分より小さい数の個数のK*(K-1)/2倍。Nが小さいのでO(N^2)でいい。

C - Cell Inversion

マスを2つ選ぶとき、右側になるマス（Rとする）と左側になるマス（Lとする）に分ける。すると、全体を反転し、左端からRまで反転し、右端からLまで反転したのと同じ。全体を反転する回数はN回、Nが奇数なら最初に全体を反転させればいいか。左端からのと右端からのがN個ずつあるのでかなり複雑。長さがsと同じtを作りLRからなる文字を入れることにして、RLという並びはペアにして全体をカバーできる。RLを除くとLLLRRRみたいになるのでまだ考えられそう。ただ、逆向きに構成するの大変そうで、ここらで進みが遅くなる。21:40くらいまで考えてDへ。

ていうかsの隣り合う色が同じならtの隣り合うものは異なる、違うなら同じになるように設定するしかないのでは。あとは、その時点で一番左のRの相手のLが何個あるかを掛け算していけばいい。途中でLが足りなくなったらダメ。最終的にLとRの数が同じじゃなかったらダメ。あと、左端はLなので左端の反転は1回、つまりs[0]=='B'も条件（前半に考えたこと全然関係ねえ）。Nの階乗を忘れていたので掛けるとサンプルが合うので提出、WA。以降、間違っている箇所の心当たりが全くないまま終わった。Eが読めなかったのが残念。

D - Classified

N=4の例で考える。別に戻るパスがなくても条件満たすよね、AtCoderにしては珍しくそこの注記がないけど、とか思ってたけど今考えたら部屋につながってる辺を往復するだけで戻れたわ。しばらくして二部グラフを思いつく。どうやら必要十分条件になっていそう。奇閉路があったらダメだし二部グラフなら偶数になる（これも今考えると「奇閉路がない」でそのまま同値だ（というか二部グラフに「偶閉路しかない」という言い換えがあるの気づかない））。辺集合をいくつかに分けるイメージ。すると、頂点集合をできるだけ個数の差が小さい2つに分けていく構成方法が思い浮かぶ。より小さい問題に帰着されているから再帰で書けそう。解法の妥当性だが、親のレベルはもう使えないからまあ小さい問題に帰着されてるし、そうなると最初に分けるのもこの分け方よりいいものはない。厳密ではないがよさそうなので実装に入る。i0からi1までを2つに分けてレベルdの通路を設定する関数を書く。頂点数が2未満になったら何もする必要がない。i<jとなるa[i][j]を出力するので、配列に書き込むときもi<jとなるよう気をつける。

ABC138

開始前36.8、終了20分前36.4、終了時36.1。最近の俺、立ち回りが身の程知らずすぎる。Dまで順調に解いてから、EとFを1秒ずつ見てFをやっていた。しかし、Eは問題文を読めば（これには1分から3分ほどかかる）解き方を知っている問題だった（実装には時間かかるけど）。楽しむという意味では全く問題ない立ち回りだった（Eをどこで解こうがEに使う時間は一緒）が、さすがにもう少し「勝つための立ち回り」をするべきだった。まずEとFを両方読み、片方しか読んでない状態で解法がわかればもう片方を読まずにそれを実装してもいいという感じにしたい。Fに行ったのはxorだからというのもあるし、全完するなら順番は関係ないというのもある。最初に順位表を見たのはEを通したとき。Dを通した時点で見てもよかった。本当に雑すぎる。もうちょっとレーティングを気にしたほうがいい。もちろん楽しむの優先ではあるけど。で、順位表を見たら見たで「Fこれしか解けてないし無理に決まってる」と思ってしまう。体温の低下がそれを示している。コンテスト終了時には「時間をかければ解けそう？」くらいまで行ったので、頑張りたい。まあ小さい可能性に賭けるのは人間にとって難しいので仕方ないとも思ってるけど。今回に関しては、Fにしっかり1時間使ってこれなのでさすがにノーチャンスに近かったか。

昨日は熱があったので負けても「楽しめてよかった」という感じだったが、今日はわりと万全の状態だったので、かなりイヤな気持ちになっている。そもそも、前回も今回もレーティングの期待値を最大化する立ち回りを仮にしていたとして、それが成功してもレーティングは減ってたんだよね。根本的に問題が解けてない。狭い場所で解ける問題だけ解いてる感じだ。

A - Red or Not

「低いほうがred！？」と思った。一応指示通りに実装しサンプルも通って、改めてよく見るとこれはレッドコーダー前提の問題だ。色を自由に変えられるかを問うている。言われてみれば3200は赤と橙の境目じゃないんだけど、なかなか気づかなかった。

B - Resistors in Parallel

一応0除算とかに気をつけながら実装。

C - Alchemist

サンプル2の説明を見て、「最初に小さいの同士を合成するといいのかな」とややキケンな判断をする。これはたぶん正しいんだけど、最初に1個のサンプルから思い込みを持ってしまうのはこわい。まあ大きいやつの寄与を大きくしたいのでこれでいいはず。ただ、今証明を考えてみてもできない。頭が悪い。

D - Ki

各頂点から見て何が足されるかを考えると、DFSの通り道にあるクエリたちということになりけっこう簡単だ。使う変数（メモリ）を減らせそうだと思ったけどまあわかりやすく解けてるのでこのまま。サンプル2が親切で助けられた（考察を進めるうちに、同じところに何度も足すイメージが失われる）。

E - Strings of Impurity

簡単すぎてびっくりした。O(|S||T|)でいいならやるだけ。そこから高速化する方法も典型。ただ実装はそれなりに大変。sの各位置と英小文字の集合の各要素について、その位置から見てその英小文字が次に現れる位置を持つ。ループがややこしいので、sの2倍の長さにしてループを消す。「次に現れる位置」には2種類あり、現在の位置に現れるのを含めるかどうか。あやしいとは思っていたが、これに明示的に気づいたときには実装が進んでいたので実装したほうでそのまま進めた。まあこっちのが簡単かな？位置の初期値をn-1にするときれいに書ける。sを2倍にすることで次の文字までの距離もただの引き算で済む。位置の値だけN未満に維持する。

F - Coincidence

y/x==1&&(y|x)==yという条件が見える。xをxorすることによる増減は+xから-xまでと気づく。あるx視点でx以上x*2未満のy候補を考えると、yがxと同じ桁数なら簡単で、違ったらよくある桁毎に見るやつ。でもxを全探索できるわけじゃないんで、ここで詰まってEへ。

逆にy/x!=1&&(y|x)!=yとか求まらんか？厳しそうだけど別の視点も得られる。y視点を考えてみるがそれも無理。（あるkを固定して）k桁のペアはいくつあるかを考える（これはもっと早く思いつきたかった）。xとyは同じ桁数であることに気づく。yが桁数多いと、xにあるビットの他に上の桁のビットまであるので必ず2倍以上になってしまう（これがなかなかわからないのは感覚がにぶい）。あとはyの最上位以外の立ってるビット数がi個のものがkCi個でそれに対応するxが2のなんとか乗でとまとめて計算できそう。LとRで切られるのが大変。2進法で101000以上101100未満のxの相手のyの個数は、下2桁の0の個数によってさっきのk桁のときと似た計算ができそう。LとRが同じ桁数のときは考える時間がなかった。

AGC037

今日は体調が悪かった。エアコン付けても寒いし暑い。体温は最高で37.5あって今日のAGC出られないかなと思ってた。直前まで様子を見てたけど、36.9まで下がって気分も悪くないので出ることにした。コンテスト中に何度か測ったけどずっと37.2くらいだった。今は36.9。自分では、いつもとそれほど変わらないパフォーマンスが出せている感覚だった。レーティングを気にせず、やりたくないAを途中でやめてBCへ行き面白そうなCをやれたので、まさに最近の自分が目指していた楽しむこと優先の立ち回りができていたと思う（素晴らしい）。ただ、今まで水色パフォ以上しか取ったことなかったのに、灰パフォを取ってしまった。それを知って特にショックを受けなかったのは、熱があったからだろうか。まあそれはいいけど、今夜や明日あたり、tokuminiさんやdasaponさんの結果と比較してわかる自分の無能さに落ち込むんだろうなあとは思う（今から気が重い）。最近思考が遅いのは悩んでるけど仕方ないのかねえ。

体調がうんと悪くなったら撤退することになるので覚悟していたが、最後までコンテストに参加できてよかった。展開上、NoSub撤退になる心配が出ていたが、それも気にせずやりたい問題をやった。結果的にはC問題を提出できた。0完だけど、まあNoSub撤退よりは気分がいい（これも世間体を気にしたゴミみたいな感情だけど）（参加したのに成績表に載らないのはかなしいというのもある）。

A - Dividing a String

ここ「すべてのiについて」って書いてほしいなあ。「あるiについて」かもって思うじゃん。問題文を読むのに2分以上かかった。いくつかの例をいじってみるが、a aaa aみたいな分け方まである（これはaa a aaでも行けるとあとで気づいた）。隣り合う文字が同じときが問題なわけで、両側の文字が同じ境目を管理する？どうせKは|S|*2/3くらいにはなるだろうし。しばらくして、DPを思いつく。高々3文字っぽいし、最初のi文字で区切れて最後がk文字の最小を持つ。ただ、S_iが4文字あれば十分な証明すらできない（あまり時間をかけたくないので）。まあ2文字でいい気がするけど。妥協して証明なしの5文字でやるとして、DPの更新がかなりめんどくさい。さすがにそれはAGCじゃないよね？何か簡潔な解法があるはず（ないならやりたくない）。いつの間にか25分も経っていた。見限るのがちょっと遅い。BとCへ。

B - RGB Balls

RGBではなく012で考える。各1について02を探す。左右両側か、片側だけか。両側の場合両方効くが、片側の場合は遠いほうだけ影響する。いや最小を一つ求めるのでさえ大変なのに、（最小を求める必要があるかは知らんけど）その通り数だなんて最初から無理だと思ってた。10分くらいで切り上げてCへ。

C - Numbers on a Circle

BとCを1秒ずつ見た感じでこっちのが面白そうだと思い、まずCをやる。逆から考えたらどうかと思いついたが、そこから進展せず、10分ほどでBへ。

Bから戻ってきた。逆から考えて、減らせるときは減らす以外にその要素を変化させる方法がないことに気づいた。以降、Cをメインにやった（詰まったときにAやBを考えていた）。面倒なのでソースに書いた考察メモを転記する。

//逆操作を考えると隣2つの和を引いてもA以上でなければならない Aは1以上なので和より大きくないといけない
//引ける候補は多くとも1つおき
// 1 10^9 1 みたいなときは10^9/2回くらい必要になる
//a b c d となっていてbが減らせるとき、b>a+cなのでaやcはbが変化しないかぎり減らせない
//つまり、bが変化しなければならないなら現在のa,cで減らせるかぎり続ける必要がある Aに等しくなるか減らせなくなるまで 最小もくそもなくそうするしかない
//Aより大きくても、隣より小さくなればチャンスはある 隣が減らせるようにならないのにAに等しくならなかったらもうbは変化できないので-1
//減らせるやつをリストアップする a b c d e
//cより大きい間はbを減らし続ける必要があり、結局bは（Aに等しくなった場合を除き）cより小さくなる
//新たに減らせるようになるのは、減らしたやつの隣のみ これをO(N)回繰り返す時間はない
//減らしたa b cだけに注目するとb>a+cがb

最初は、最大でN/2個の更新ポイントを（隣り合ってないので）一気にやっていくことを考えていたが、よく考えるとBは常に更新しているのでそうなってない。ただ、減らせるものは減らす必要があるのでこれでも解けていると思った。提出するもWAとREが出る。REが一つでもあるとコンテスト中は実行時間が表示されないので困ると思った（更新回数は各要素についてO(log(B))で済むと結論は出していたものの）。REの原因は、Bを更新しながらだからN個を超える更新候補が出ることだと見当が付いた。やはりキューにすべきだったかーと思いキューに書き換えて提出。REはACになった模様。しかしけっこうな数のWAがそのまま残っている。絶対に正しいようにしか見えず（こうなったときってほんとバグが見つからない）、逆立ちしてソースを見たりしたいと思ったけどできないので、きれいに書きなおして最後記念提出して終わった。

（追記）関係ない悪夢をみていた気がするが、寝起きにふと気づいて出力のint r; をll r; にしたら通った。これは、-Wconversionとか付けてる場合じゃないなあ。出力が32bitに収まらないのは途中で気づいていたが、まだ解けてはいなかったのでそれどころじゃなくて最終的に忘れるやつ。ここまで「正しい」コードだと、コードの見た目ではバグを発見できないなあ。見た目に頼りすぎ。どうしたら防げるミスかわからない。

ABC137

どうなるんだと思ったけど、結局は実力通りの順位になる辺り新ABCはすごいね（まあ相当運はよかったと思う）。開始前30分前36.8、終了5分前36.9。ちょっと体調が悪かった（途中はもっと上がってたはずで、体温が上がったときにいつもと違って体がきつかった）。途中で邪魔が入ったりもしたが、そこで気分を壊すこともなく20秒のロスは本当に20秒のロスだけで済んでいた。「あとちょっとで黄色になれる」みたいなときにこんな落ち着いた立ち回りはできないわけで、黄色を経験できてよかったと思う（またなりたいけどな）。今回はいい動きができた。

A - +-x

問題を開くのに1分かかった。久しぶりだな。でも、それで意気消沈ということもなく淡々と解き進めていた。

max({ a + b, a - b, a * b })という書き方を覚えて定着してきた。

B - One Clue

K=1のときはそこだけで、Kが1増える毎に前後に伸びる。for (int i = -k + 1; i < k; i++)って書いたけど、i <= k - 1と書いたほうがきれいだったかな。" \n"[i == k - 1]が定型文なので引きずられて普段通りi < kと書いた感はある。

C - Green Bin

これ最近のCと比べるとかなり難しいね。30分前にトイレ行ったのにまたウンコしたくなって、トイレに立った瞬間解けた。各文字列はソートしちゃっていい。その後s全体をソートして同じ文字列が何個あるか数えればいい。それで解けてるけど、実装方針はけっこう迷う。10文字だから10byte必要、でも英小文字だけだから64bit整数に入るかも？結局は、char c[11]で受け取ってソートしてからarrayの配列に入れた。std::arrayは比較できるのでs全体のソートも簡単。あとは数えて（ここの実装けっこう大変なんだけどさすがに何回もやってるしできる）t * (t - 1) / 2 を足していくだけ。問題文のi < jとかに惑わされて、ぐしゃっとひとまとめにしていいのか一瞬迷った。

（短時間でACしてるtokuminiさんのソースを読んで）map思いつかない。いや個人的にmapは好みじゃないんだけど、最近は思いつけるようにはなってきたと、思ってたんだけどなあ。

D - Summer Vacation

「また何かでソートして貪欲かあ」と思いながら読み進める。M-1日後の日にできるバイトはA[i]=1のやつだけなんで、その中で一番報酬が大きいのを選んで損しない。つまり、Aでソートして、同じAの中で最大を選んでいけばいいと思った。が、これは勘違いで、1日後に報酬が得られるバイトはいつでもできるので、いつやればいいか判断できない！これはまずい流れだ。もう少し考えて、セグ木でM-j日目以降の最大報酬を求めれば行けそうだと思った。が、M-j日目がソート済み配列のどこにあたるかは二分探索とかになるし、解けるとはいってもかなり厄介。ここで、Dをやるのをやめた。こういうゴチャゴチャしたのは苦手だし楽しくない。EとFを見て面白そうなFへ。

シンプルな実装が存在するはずだ。Dでセグ木使うわけないというメタ読みもあるし、セグ木が本当に必要になるケースは少ないという経験則もある。今の自分にとっては複雑だが、そんなに複雑な問題には見えない。……priority_queueだ。落ち着いて実装。残り時間が少ない中、さっきまでと違う方針を落ち着いて書けたのはよかった。

E - Coins Respawn

自己辺もあるし相当めんどくさそう。最後に時間でコインの支払いが生じるとか無理でしょ。やっぱりFへ。

Fから戻ってきたが、ここで唐突に気づく。これベルマンフォードじゃん！制約も間に合いそう。唯一のひねりはT*Pの支払いだが、よく考えると各辺のコインがC[i]からC[i]-Pに変わっただけだ。正直言うと、ベルマンフォードがAtCoderで再び出題されるとは思っていなかった。ABC061のときにググって出てきたコードで理解しないままなんとかACとったのを思い出す。そのときのコードをコピペする。まだ競プロ歴が浅いときのコードなのでやや不安だがけっこうしっかり書いてある。そんなことよりそのコードを今回の問題にちゃんと適用する力が必要だ。幸い、少しの試行錯誤でサンプルが通った。頂点0から頂点N-1に行くコードだったし。関係ない場所のループを検出しちゃうのは当時WAを食らって大丈夫なはず（そういうループも検出する必要がある問題だったら困ってた）。提出してAC。これは運でしかない。解けたのでDへ。
（なお嘘解法だった）

F - Polynomial Construction

とりあえず、f(0)=b[0] とか x^(p-1)=1 (x!=0) とか書き出す。x*(x*(x+b[p-1])+b[p-2])+b[0] とかも書いてみるが、関係なさそう。単に行列として書いてみるときれいに書けるが、うーんさすがにO(N^2)では無理だよね。i^jの表を作ってそれをながめながら考えるが、無理。詰まったのでEを見てみる。

唯一面白そうなFに注力する方針だが、さすがに無理そうだという気持ちになってくる。解けると思って解き始めたが、身の程知らずだった。単なる力不足で仕方ないけど、その力不足が悔しい。Eへ。