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へ。

ABC136

堅実な5完で200位以内。よし。Fは難しかったが、Eまでは数学系の面白い問題が多くて得意セットだった。終了後36.9。久しぶりにレーティング上がったー！珍しく0時前にブログも書き終えて、けっこう内容的にすっきりしていた。

A - Transfer

よく考えれば解き方はわかる。要するにどれだけ水を移せるかわかればよく、それはmax(C, A-B)だ。それを出力してもダメで、容器2に残る量を答えるんだった。複雑すぎて、解けたころには道のりを忘れている。

B - Uneven Numbers

じっくり考えた。1桁なのは1から9（0は含まない）、3桁なのは100から999。しかし、愚直より簡単になる気がしないので愚直へ。幸い、ここまでの時間で桁数の簡単な判定方法がわかっている（各iについて10^iを超えるならインクリメントしていく）。

C - Build Stairs

またこの典型か。左から考えていくと、低くして（それより右の人は）損しない。最初深読みして「マスの高さを 1 高くする」と言い換えてしまった。そのままでいい。

D - Gathering Children

RLの境目が1つ以上存在し、そこへ向かって落ちていく。左右対称なので、R側だけやればいい実装に変更。境目に向かって落ちていき、それが偶数個なら境目の前後へ均等に溜まり、奇数個なら「10^100が偶数なので」（←ここ面白い）Rがあった側が1個多くなる。reverseしてLも同様。最後の要素がRでないことも利用できたし、いい実装だった。

E - Max GCD

絶対に解けそうにない問題に見えるが、「0をたくさん作ればいいんじゃね」と思って考え進めたところで+1と-1がセットなことを思い出す。意外と制約がきつい。たとえば全体の和の偶奇は保存される。ていうか、何で割ったあまりも保存されるやん！？全体の和は正なので、最大値が存在しないこともありえない（とりあえず安心しとく）。全体の和は10^9にも達しないので約数を全列挙できる。あとは各約数についてK回以内で実現できるか。ここがむずい。いや、そこまで難しいわけでもないけど、考察の山場が何回も来るのが、十分な実力があるか試されているかのようだ。増やす側と減らす側に分けないといけない。なんとなく減らしたいのとかあるけど厳密にはわからない。まず、（約数をqとして）qで割ったあまりの和はqの倍数になる。逆から考えたり色々やったけど、結局思いついてた貪欲っぽいのでよかったんだよね。これけっこうきついというか面白い。あまりの和をqずつ減らしていくのを(あまりの和/q)回やると0になる。回数が決まってるなら、貪欲に回数が少なくなる（あまりが大きい）ほうから取っていけばいい。全ての約数に対してO(NlogN)の時間をかけることも可能。最大値を求めるのだが、約数を大きい順に列挙してもいいが単に条件を満たすやつのmaxを取ってもいい。min(a[i]%q, q-a[i]%q)とか書いてたのがそのままになっててサンプル合わなかったりした（道のりが長いからなあ）（考察が完了する前に実装すると生じる問題だが実装は考えの整理に有効なので悩ましい）。そこ以外はわりといい実装だった。

F - Enclosed Points

まず座標圧縮できる。x座標でソートすると各ペアの間に含まれる点はわかる。条件を分解する？いや、xでもyでも含まれてない個数がわからないのでダメ。長方形のパターン数はO(N^4)には収まるんよね。どの長方形も、2個から4個の決まった点に支えられてる。長方形が決まればカウントできそうだが、その長方形があるかも大変そうだし、そもそもO(N^2)も許されないからなあ。ずっと、個数がO(2^N)の和とかどうすりゃいいんだよってなってた。

夏アニメ土台部分

タイトルが苦しい。なんかたくさん見てるけど、「文句なしに1位」みたいなのが全然ない。それでも1位と最下位はわりとすぐ決まった。他はもう、どう並べてもよさそうで決めるのに苦労した。そもそもアニメには色々な要素があるのに一直線に並べる順位付けはどうなのというところではあるが、やはりこういうの好きなのでね。

手品先輩

気楽に見れるので。本渡楓のイメージがここたまのこころちゃんなので、こういうキャラで声を当てられるようになる気がしない。最初キービジュアルに男がいるの見えてなくて動揺したが慣れれば大丈夫。かわいいし、体の作画がわりと好み。あとタイトルがいいよね。

まちカドまぞく

初回のアバンがやけにゆっくりだなと思ってた。そしてOP。なんだこの雰囲気のある曲は。これはただごとじゃないと思って画面を凝視していたら桜井！これは1話の本編を見たあとで知りたかったなあ。まあ、大塚舞とかJ.C.STAFFとか、伏線となる情報はそれまでにもあったんだけど。1話は作画クオリティがすさまじかった。2話まで見ると、なんか物理少女の人が性格悪いように見えてきた。小原好美のほうは声に合ったキャラに見える。まあ内容についてはこれから。

女子高生の無駄づかい

これはキルミーベイベー度が高い。ここに来てまさかこんな声が聴けるとは！これが赤﨑千夏だ。あしが短い感じの作画もよい。戸松さんのおさげもかわいい、目もかわいい。3話微妙だったのでこれから内容がどうなるかというところ。ヤバい先生が、「荒ぶる季節の乙女どもよ。」の先生とまざる。

荒ぶる季節の乙女どもよ。

悠木碧かと思ったら河野ひより。今期たくさん出てるけどみんな違うタイプだ。デスマのポチは思い出せないけどそれっぽいな。内容はつらいのでずっとぷよぷよやりながら見てる。わりと密度がある感じなのはよい。ある程度の作画レベルを前提としたデザインに見えるので少し心配もある。あとスカートの長さがバラバラなのはいいね（ちょろい）。あー岡田麿里ねって感じだけど、こういうコケそうな話がどう転がるか楽しみではある。最終回とかどうするんだろうね。

異世界チート魔術師

今期めっちゃ出てる高橋李依。声質で、エミリアとめぐみんでめぐみんタイプの声が聴きたいと思っていたが、ここで。普通の女子高生でもこの声いけるじゃん。元の世界の知識を魔術に応用できるのが強い。ゼロ魔の戦闘機みたいで燃える（火だけに）。凛さん学校の制服とてもよいのだけど、もう着なくなっちゃうのかな。みんなが親切なのもよい。

ダンジョンに出会いを求めるのは間違っているだろうかII

1話はつまんなかったけど、その後はまあ面白い。神らの性格はともかく結果として大迷惑になってもほっとくしかない酷い世界なのは置いといてだ。3話最後のアイズのアドバイスはぷよぷよの話として真剣に聞いていた（モンスターはCPU、あと動きが単純になるとか）。なんか赤﨑が仲間になる。リリの話は苦手。お酒を飲まされたら終わりだと思ってたら飲まされちゃって、どうすんのかと思ってたら普通に気持ちで何とかしてて呆れた（酔ったリリが完全にシャロだったの草）。酒場に洲崎西を配置するの好き。

ダンベル何キロ持てる？

黄色くてふわふわな髪がかわいい。先生は、「街雄さん」が「マリオさん」に聞こえる。食事や体をしっかり描いてるのが強い。ぽっと置いたようなタイトルから、この丸みのある内容にしてくるのは、さすが動画工房というところか。

可愛ければ変態でも好きになってくれますか？

1話の人だけが変態なのかと思ったら全員かい！まあこういうかわいい女の子がたくさん出てくるアニメは好き（そういうのばっかだろと思うかもしれないが、「かわいい」でまとまってるのかなり少ない）。で、こういうのに出てくる妹が好き。さて、2人目がSだったので、もうお前らでくっついて百合エンドでいいんじゃねという感じだ。

博多明太！ぴりからこちゃん

この河野ひよりもよい。けっこう声が豪華。浮いてるイチゴもなかなかいい。EDの最後の微妙な顔が癖になる。博多と思わせてそうでもない世界にいつの間にか引きずりこまれていた。

ソウナンですか？

遭難したまま話が進むやつだ。こういう狭いアニメもよい。登場人物の数で言えばキルミー並。色々できるのかっこいいよなー。「学校で学んだことは、この島では役に立たない」って台詞がすごく嫌だった。

通常攻撃が全体攻撃で二回攻撃のお母さんは好きですか？

すんませんみなみけのハルカみたいなイメージで聞いてたらかやのんだった。こういう声は逆に新鮮だ。最初、お母さんだけが異世界に行くのを想像していたが、子供も一緒だしそもそも異世界じゃなかった。親子で冒険するのは、話作るのキツそうだけどそれはまあいい。異世界じゃないじゃん！いやまあSAOとかもそうだけどさあ。でもこっちは、いわゆる「ゲームの世界に入りたい！」っていうゲームではないでしょ。お母さんはなんか知ってるみたいだし、かなりの緊張感がある。異世界のワクワク感もない。とりあえずワイズとポータがかわいいのでよし。

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を変えようともしてたが、固定されたテストケースでこれをどの程度落とせるものなのかわからなかった（時間的にロリハを信じるしかなかったし、そうそう落とせないだろうと思っていた）。ロリハで候補を得て実際に確認する処理も考えていたが、できそうだけどけっこう面倒そうというイメージだった。