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