ABC139

E以外簡単というイメージで解き進めていた。コンテスト中に顔が熱くてしんどいと思って体温測ったときは37.0だった。

A - Tenki

数えます。

B - Power Socket

電源タップを使うと差込口がA-1個増える。差込口をB-1個以上増やしたい。それはまあすぐわかって簡単なんだけど、見慣れない式になるから分子が負にならないか心配したりした。さすがに大丈夫だろうと思って提出したけどけっこう不安だった。

C - Lower

Cっぽい問題。高くなったらリセットでインクリメントしてくんだけど、初期値やインクリメントのタイミングが感覚でわからなかった。C問題として、こういう場所も残ってたんだなという感じ。

D - ModSum

いくら実装が軽いと言われるAtCoderでも限度があるでしょ。紙の上で少し試してこうしたら大きそうと思って、それより大きくならないことが示せたので提出。さすがにこのコード量を提出するのは勇気要った。

E - League

疲労感があるところへ体温が高くしんどい。しんどいから知ってる問題しか解きたくないという気分になり、EとFを読んでEをパスしてFへ行った。

Fを解いて戻ってきた。40分あればいけるやろ（いけなかった）。全部のカードに通し番号を付けてAの各行を合成することを考える。隣の行とは1個だけかぶってる。しかし、全体ではO(N^2)のかぶりが生じる、というかまさにそれが総当たりの全試合なわけで。うーん、グラフか？自信ないが、とりあえずトポロジカルソートしてみる。たまにしか使わないので理解もしてなくて時間がかかる。閉路があったら-1を出力するが、閉路検出もよくわからんので力づくでやる。うまく動かないが、x-yとy-xを同一視する（正規化する）処理を忘れていた（最初はわかってたのに）。グラフの頂点の一部しか使わないのでけっこう混乱する。さて、トポロジカルソートできたからってここからどうするか。時間もないので適当に。k日目から出てる辺の先はk+1日目以降でないといけない。何回か提出したかダメだった。ここはちゃんと考えてないので仕方ない。

F - Engines

双子の片方がwriterなのか？そうだとして、この位置に出してくる問題は面白いのが多そうだし、実際面白そう。えらく簡単そうに見える。とりあえず向きでソート。(0, 0)はスキップして、コーナーケースは先にやっておく。atan2の使い方をググる。まず、最大値を与える向きを固定したらそっち向きの成分を持つやつだけを足せばいいと思いつく。何を足すかは向きがちょっと変わっても変わらない。試すべき向きは高々N通りしかないので行けそう。ソートした隣同士の角の二等分を候補にするのが自然だが、同じ向きのエンジンがあったときやエンジンが1個や2個のときなどが自信ない。そのうち、単純にあるエンジンから180度未満まわるまでのやつを全部足せばいいと思いつき、実装、提出、WA。速度重視だったので、じっくり考察し直すが、考えるほど正しそうに思える。誤差かなあ。この制約で（向きが異なる）2エンジンのなす角の最小値ってどのくらいなんだろ。かなり小さそうだけど。さて、向きが正反対の同士は一緒に入りそうにないが、誤差で入ってしまうこともあるかと思い（希望を見出し）ちょっとマージン入れて提出、WA、しかもWAの個数が変わってない。いやあ、向きさえ決めたら、その向きへできるだけ伸ばすにはその向き側の180度ぶんを取るしかないはずなのになあ（例えば90度ずれた方向のを足すと長くなることもあるけど向きを決め打っているのでそれでいい（最大値をとる向きのときはそういうことは起こらない））。ここで思いつく。例えば、最大値をとる向きから左へ30度と右へ30度のエンジンの和で最大値をとるとする。このとき、右へ120度の向きのエンジンは使わないけど、左へ30度のやつから150度しか離れてない！180度ぶんとっちゃダメなんだ。そして、連続するやつを取るのは間違いないんだから全探索しちゃえばいい。O(N^3)だ。いや簡単すぎるだろ。なぜ思いつかない。ACしたのでEへ。

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

コンテスト前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に収まらないのは途中で気づいていたが、まだ解けてはいなかったのでそれどころじゃなくて最終的に忘れるやつ。ここまで「正しい」コードだと、コードの見た目ではバグを発見できないなあ。見た目に頼りすぎ。どうしたら防げるミスかわからない。