ABC135

終了後37.0。調子悪かったけど、特に悪い動きもなかった。順位もそんなに悪くない。Fがサンプル通すところまで行かなかったのは残念だけど、Fも楽しめたのがよかった。

A - Harmony

よーするに(a+b)/2が候補なんだが、|A−K|=|B−K|を|A−K|=|K−B|と書いてくれているわけでもないので、理解に少し時間がかかる。1個のcoutで出力できないのが面倒。

B - 0 or 1 Swap

Bなので愚直（三重ループ）。あとで考えようと思っていたが、解説放送を聞いてしまった。これコンテスト中もちゃんと考えたほうがいいなあ。そのほうが楽しいもんね。（ほんとはratedコンテストでBをやりたくないが）

C - City Savers

難しそうだけど端から考えればいい。最初の街は最初の勇者が行くしかないのでたくさん倒してデメリットがない（この典型を知らないと大変そうだなあと思った）。そこに気づいたので解けたけど、具体的にその解法がどのインデックスに対応してるとかけっこう時間かかった。0 0 1ってのが。まあ要するに、最初の街のために特別な処理をする必要がないということがなかなか見えなかった。

D - Digits Parade

相当難しそうな見た目をしている。でもまあ気づけば。各iについて10^iを13で割ったあまりは逐次計算できるし、13で割ったあまり13通りについて何通りあるか下の桁から見ていけば行けそう。5をどこで使うか混乱してたけど、最後出力するときに5を選べばいいだけね。混乱してるからキーボードの?を探すので10秒くらいロスした。計算量がO(|S|*M^2)になるけど、O(|S|*M)にできないかは気になった。まあ通るのでそのまま実装。?と数字で処理を共通化できたのがよかった。

実装にわりと時間がかかった。まあ実装は時間がかかるものなので仕方ない。最初はやりたいことがぼやけているのでそもそも難しいのだ。ここは、色々な実装経験を重ねるくらいしか改善のしようがないように思う。

E - Golf

まあマンハッタン距離定番の45度回転が利きそうに見える。クリアできない条件がよくわからず。K=1ならどこでも行けるし、K=2ならすぐ隣の格子点には行けない、じゃあK=3はと図を描くもよくわからない。まあなんかパリティがあるだろと後回し。よくあるパターンとして、2回動けば微調整ができそう。つまり最少スコアは、遠ければマンハッタン距離をKで割ってとかでいいし、近ければ（1回で行けるとこを除いて）2回という感じじゃないかと。しかしこれF問題の雰囲気がある。今の予想が正しかったとしてさえ実装が異常に重くなりそうだ。ここでEに対する興味がやや失われ、以降Fに専念した。

F - Strings of Eternity

sを繰り返したものが持つ周期を考える。sの長さをnとして、長さnかその約数の周期を持つ。周期が違えば噛み合うことはなさそうだし、sもtも周期に分解しておけばいいのでは？1周期分のパーツがsとtで一致すれば無限だし、そうでなければ有限。周期を見つけるのは小さい順に全部試せばよさそう。約数ってけっこう少ない（いちおう高度合成数でググる）。あとは、sを2回繰り返した文字列の中にtのパーツが最大何回連続で現れるかがわかればいい。ここで、「sにtが現れるか」という単純な問題でさえ愚直にやると間に合わないことに気づく。色々検索したが、ローリングハッシュを思い出す。いままで存在は知っていたし性質もなんとなくは知っていたが、これ要するに（文字の種類数がB以下として）B進法で表した数を10^9+7とかで割ったあまりじゃんと気づく（コンテスト中だと理解が進むのほんと現金だよね）。実際は桁を逆方向にすることで簡単にしてるみたいだが、このままでも使えるのでここは今までの経験が生きるこの形で。しかしサンプルも合わず。最初に書き上がったのが残り5分くらいだったのでね。ハッシュ衝突を避けるためにBやModを変えようともしてたが、固定されたテストケースでこれをどの程度落とせるものなのかわからなかった（時間的にロリハを信じるしかなかったし、そうそう落とせないだろうと思っていた）。ロリハで候補を得て実際に確認する処理も考えていたが、できそうだけどけっこう面倒そうというイメージだった。

AGC036

時間ギリギリで2完。Aは気づけばという感じ、Bは重かった、CとDもちょっと見たけど思いつきでどうにかなる問題には見えなかった。途中36.7、終了後36.9。立ち回りはわりとり（わりと理想的）に見えたけど、問題が難しすぎた。楽しかったかというと、やはり勝てないと総合的にマイナスの感情が支配的になる。そういうゲームをやってるということだよね（ぷよぷよとかもそう、面白いゲームはみんなそう、これからの人生ずっとそう）。

A - Triangle

10^9以下しか出力しちゃダメなのに10^18を作れってんだからきつい。図形的に少し考えていたが難しそう。開き直って外積で平行四辺形の面積を求め数式でなんとかする。10^9*10^9の正方形から削り取る感じだと難しそうだが、数式だけで見れば10^9*a-1*bみたいにできる。一つの頂点を(0, 0)に置けばこれでいい（出力の制約からはみ出ないことが確認できる）。ほんとかよって感じ。平行四辺形が10^9*10^9の正方形からはみ出てもいいことに気づいてなくて見直ししたときちょっと焦った。面積1の作り方も、「はーこれでできるんですか（わかってない）」って感じ。

B - Do Not Duplicate

「ヨッシーのたまご」はやったことないです。削除された数がなかったことになり、ある数の個数の偶奇とかが保持されないのが難しいポイント。一方で、自分と同じ数をはさむことはないので、削除が起こる同じ数のペアは列挙できる（ペアの個数がO(N)）。全然わからないので、とりあえずシミュレーションを書いてみる（このコードはあとで流用できる可能性が高く時間の無駄にはならない）。周期があるようだ。色々考えていたが全然わからなかった。CやDも見つつ。時間をおくと脳のステートが変わるので、解けない問題を交互にやるのはかなり効率がいいと感じる。22:30に体温を測り、その少し後に、sが定期的に空になるというアイデアへ至った。

やっと解けそうな気がしてきたが、これをどうすれば解けるのかすぐにはわからない。sの先頭にある数は次にその数が現れたときに消える、ということに気づいて、じゃあ次に自分と同じ数が現れるのがいつか前計算しておけば解けそうだとなった。n*kを超えてはいけないし、ちょうどn*k個を処理したらまさにそれが答えなので、n*kを超えたら超える直前の状態でループを抜けるようにした（慣れない処理で何回も確認した）。そして残りをシミュレーション。歩幅は最大でN+1なので不安だが、N+1個残ったら必ずもう一歩あるので半端はN個以下（0個以上）。sに入っているのは全部異なる数なので、各数についてsに入っているかの情報を保持。問題文通り削除してそこで情報を更新できる。全体でO(N)になるので大丈夫。サンプルが無限ループになるが、そういえば最初にシミュレーションをサンプルでチェックしたときもそうだった。よく見るとサンプル3のKがクソでかい。気づいてなかった。そして、Kがでかいときの処理を忘れていたことに気づいた。最初の場所へ戻ってくる確信がないので、各a[i]へ降り立ったときの位置を保持しておき、初めてループしたときにそのループをその場でしれっとn*k以下の範囲でギリギリまで回す。初めてループするまでの計算量はO(N)だし、そこからゴールまでの長さはループ1周未満なので、全体でO(N)。提出するがけっこうたくさんWA。

コードを画像として見直して、どう見ても正しいので少しコードをいじって様子見提出するが、WAの個数は同じ。地道に読んでいくと、「break。…break！？」。最初に書いたO(N^2)のシミュレーションコードの名残り。forを取り除くとbreakは自動的にさらに外のforのbreakになる。コードを流用する（そのまま使うのではなく改変する）のはあまりいいムーブではない！ちゃんと考えながら書けばそうそうミスは出ないものだ。しかし、既存のコードをいじるのは「コードを書く」思考ではない。厳密に考えることはできないのだ。

C - GP 2

碁石を使ってごにょごにょやっていたが、Nも指定されMも指定されi≠jの条件もたまにしか発動しないし考えることが多すぎて解ける気がしない。Dは読んだだけ。

ABC134

5完早解き回なのでこんなもん。結果が微妙だから気持ちも微妙ではあるけど、先週のAGCと比べたらほんとに楽しめたのでよかった。あと、ノンペナでよかった（自分はわりとノンペナ多いけど、簡単なことでは全くないから）。開始前36.8、終了後36.7。

A - Dodecagon

最近ずっと問題文が5秒くらいで表示されていてよい。さて、「半径aの円に内接する正十二角形の面積」と言われてもすぐには求め方わからないのでビビる。仕方なく問題文にある通りに書く。

B - Golden Apple

こういう簡単な考察を入れさせるBってけっこう珍しいような。難易度はいつもと同じだけどタイプが全然違うので提出時にちょっと緊張した。

C - Exception Handling

こういうのよく出るね。累積GCDのときの下位互換みたいな？まあこれは簡単そうなのでそういうの関係なく考える。大抵、全体の最大値を出力することになるので場合分け。最大値でないものを選んだときは最大値になる。最大値を選んだときは、次にでかいやつ（同じやつも含む）。これで解けている。実装が微妙になった気もするが。

D - Preparing Boxes

「任意の」がちょっと読みづらくて警戒した。サンプルで雰囲気をつかんでからそこを読む。どう誤読しそうだと思ったのかもう思い出せない（問題を既に知っているため）。「すべての」でいい気がするけどなあ。あー、たとえば、「僕が任意に指定したiについてだけ条件を満たせばよい」みたいな誤読。いや「すべての」って書いてほしいよねここは。問題文は、問題文を信頼してゆっくり読んでいるので、石ころが落ちてたらちゃんと処理しないといけない。

内容自体もけっこう難しいが、そこは問題ない。図に書くとそこそこ疎なので、そこを利用できそうな気はする。約数はO(sqrt(N))で求まるというのも思い出す。しばらくして、図を見てひらめく。N番目の箱から見ていけばいい（a_Nに影響するのはN番目の箱だけ、N番目の箱を除けばa_(N-1)に影響するのはN-1番目の箱だけ）。「DでO(N*sqrt(N))が想定マジ？Python間に合うの？」とかいらんことを考える。これを0-indexedで書くのが異様に難しくて「そんなことある！？」ってなってた。ここは要復習。

解説を見る。下じゃなくて上を見るの天才か！？いや確かにそういうO(NlogN)も浮かんではいた。でも思いつかなかった。目に見えてる図しか見えないのは普通のことだと思う。いやこれは見えない。見る方向でこういう計算量の変わり方するというのも全然知らないパターンだ。俺は何も知らない。あと、-1を出力するって説明あるの忘れてた（まあこれは構成できてるので問題ない）。

E - Sequence Decomposing

問題名にある通り、数列をいくつかの増加列に分解する問題。貪欲に増加列をとっていくO(N^2)の解法がまず浮かぶ。具体例をいじりながらその証明を考えるが、もにもにしてなかなか進まない。LISっぽさを感じ、Chokudai SpeedRun 001の自分の提出を見ながら証明を考える。LISの2通りの実装を再理解するのにけっこう時間がかかる。そうしているうち、LISとは関係なく貪欲の証明ができそうに思えてくる。これ逆から見ても同じ問題にしかならないので難しいが。証明できたような気がしてたが思い出せないｗ とにかく、実装に入る。というかそれを実現する方法をまだ見つけてない。増加列を最大N個持ちながら進んでいく。LISのコードと同じになりそうで違う内容なのが難しい。std::setで行けそう。二分探索できる状態で値の挿入と削除ができるから。値の書き換えも、削除して挿入し直せばいい。最後のほうで気づいて​multisetにした。​multisetが役立つ場面なんてあるんだと意外に思った。提出時の不安は、実装が正しいかというのが大きかった（珍しい）（追記：あれ、普段も実装だった（実装にも色々あるんやね））。

解説を見る。あー、（まだ何も考えてないけど）天才っぽい。やっぱりLISなのか。ていうか、俺の提出はLISを求める別解法になってるってこと！？オーダー同じでも効率悪いかもしれないけど。それにしてもあの2つだけじゃないんだ。コンテスト中も「俺はLISを理解してない」と思ってたけど、これほど懐が深いとは。解説放送を見る。set要らないって言ってる。えーこれは別の方法じゃないってことか？確かに、挿入されるのが毎回最小の値になるの気づいてなかった。ほんと何も、何も。

F - Permutation Oddness

奇妙さの最大を求める。まあ逆順かと思うけど、一応実験もしてみる。意外と時間がないのでガンガン行く。ABCってほんと短いよね。n=4やn=5で最大値を求める。予想通りの値。そのときの順列も列挙してみる。ほー。最大値だけでなく、0から最大値までのそれぞれのkについて何通りかも出力させてみる。うん、これ足してn!になるんだよね。よくこんなの見つけるな。絶対OEISにありそうだけど、単にGoogle検索しただけでは出てこない。パスカルの三角形みたいにn=50まですべてを計算できそうに見えるが。規則性がありそうで見つからない。問題に立ち返っても、何もできない（nが一つ小さい問題に帰着させることができないのがつらい）。いや足して階乗になるの絶対面白いでしょ。解きたいなあと思った。

なんか青パフォじゃ満足できない体になってしまった感あり、この先の人生つらそう。Fが解きたい！めぐみんが爆裂魔法を撃ちたい気持ちに共感する。（今日の午後はこのすば一挙を見てた）

AGC035

開始前37.2、終了後36.3。つまらなかった。何だったんだこの3時間は。どうすれば楽しめたのか、何もわからない。なんで何も楽しいことのない人生を送ってるんだ俺がそんな悪いことしたかよイライラするなあ。

A - XOR Circle

とらえどころがないけど、実例で考えるとa, b, a^b, aと周期3で繰り返す。挟まれるのではなく、単に連続する2つのxor取ったら次のになるという状況。なので、a, b, a^bがn/3個ずつあるみたいな感じ。じゃあNは3の倍数である必要があるかというと、全部0というケースがある（制約を確認）。これで行けそう。証明すると時間がかかるしたぶん正しいので、AGCのAはこれで行かざるをえない。きれいな書き方がわからず、きれいでないけど正しいコードを書く。WA。正しくなかった。n*2/3個のこともあるじゃん。1, 1, 0, 1, 1, 0って紙に書いてあるんだが？直すが通らない。これはびっくりする。3種類の数のxorが0になることを確認するのだが、2種類しかないときn*2/3個のほうを2回xorしないといけない。

実装に時間がかかるのもWAのペナルティを食うのも力不足によるものだからいいけど、ここで時間と気力を削がれるの不毛すぎる。AGCは楽しむためにあるんだろう？

B - Even Degrees

長さ2のパスで全体を覆うのと同じこと。どうも辺数が偶数ならできそうだ。辺を頂点とし、2辺に共有される頂点を辺とするグラフを考えると（まあ辺が2乗で増えるから構築はできないんだけど）、完全マッチングを求める問題になる。完全マッチングについて何も知らないし、このグラフが持つ性質もわからない。結局ここまでだった。他には、全域木をとるとか（残りの辺どうすんだよ）、頂点の次数を上手く使って貪欲とか、長さ偶数のパスをたくさんとるとか、色々考えたけど無理そうだった。

解説を読んだが、グラフが木の場合も解けてないので全域木は惜しくない。あまりないタイプのはまり方をしていた。で、この問題が解けることが何を意味するのかわからない。やー、確かに、長さ2のパスで覆うときに木のリーフノードから適当に伸ばして、葉の親の子（または子孫のあまり）が偶数個だったらペアにして奇数個だったら上に押し付けるようにすれば。残った辺は偶数個だからできそうではある。マッチングとは何の関係もないってことでいいのかな。解説読んでも知りたいこと書いてないのつらい（普段は（読むのが大変なだけで）知りたいこと書いてあるんだけど）。

CとDは問題を把握して5分くらい考えただけ。Cは「重みが i であるとする」がわかりにくすぎた。重みがiでない場合については何も述べていないと読める。Dは3乗っぽい制約だけど端が特別なんですかね。Cが読みやすければCもやりたかったし、Dもやりたかった。Bの考察をかなり進めてしまったので、それを捨てる勇気がなかった。レーティングはどうでもいい。AGCをやる方法を考えろ。こんな時間を過ごすためにAtCoderやってるんじゃない。