ARC113

体調が悪いかどうか始まってみないとわからないところがあって(始まると元気になるような体力温存型の沈み方もある)、今日は悪かった。ものを考える頭をしていない。でも、昨日もそれに近い状態で黄パフォだったし、今回も青パフォはしっかり確保している。なかなかの安定感。

A - A*B*C

直前に行ったのにトイレで考えてた。B*Cがそれぞれ何通りあるか考えようとしてなかなかまとまらない。たくさん解かれてるので「正面から行けるんじゃ?」と思い三重forを書く。なるほど調和級数ね。AとBを全探索すればあとは割り算なのでO(N*log(N))。一目簡単そうで実際そうなんだけど、知らないと瞬時には出てこない。

B - A^B^C

Aと比べるとこっちのが安心感ある。正面から解けそう。まず、mod 10でa, a^2, a^3, ... には短い周期がある。それをプログラム書いて確認。全部aに戻ってくるのがわかったので楽に書けそう。あとはB^C mod 周期 がわかればいい。これは繰り返し二乗法でいい。最後がちょっとややこしくて、1乗がaなので0乗はその一つ前(aが2だったら6)になる。周期を足してしまえばいい。こういうの面白いけど、基本的なことをコンテスト中に面白がってちゃ時間めっちゃ食うことになる。

C - String Invasion

リバースして前から貪欲。そこまでの各文字の個数を管理(普段は普通にインクリメントするだけで、操作をしたら全部その文字にする)。これで通る。解法自体は実験していれば思いつくが、正当性が全然わからず、結局何もわからないまま書いてしまった。何やってんだかなあ。WAを出したのは、操作した3文字のお尻1文字が次の操作に使われることを見落としたため。

D - Sky Reflector

とりあえず列Aを固定してみる。各行がどうなるかしばらく見ていたが、そっちじゃない。列Bの要素が全部max(A)以上になるのだ(max(A)がある行の整数は全部それ以上なため)。そうなると、max(A)を全探索すればよさそう。それをiとして、列Aはi以下なんでも、列Bはi以上なんでも。サンプル全然合わなくて、列Aにiが含まれる必要があることに気づく。「包除か?」と一瞬思うが、単に「i以下なんでも」から「i-1以下なんでも」を引けばいい。列Bはiが含まれなくてもよい。これでサンプルが大体通る。サンプル2が通らない。いや昨日のABCと比べて親切すぎんか?列が1個しかないため、「i以上なんでも」ではなく「iだけ」になっている。そのように修正してさっさと提出、WA。行が1個しかないとき、列Bは「i以上なんでも」でない。iが1個は含まれる必要がある。そのように修正してAC。

E, F

E大変そう。解説に「ポテンシャル」というのが出てくるけど、そういう量がないかなーと思ってた。操作するときの文字パターンで場合分けする必要があるのかなとか考えてた。結局、こういう重そうな問題を解くには簡単な問題を瞬殺する力が必要になる(それだけでいいかはわからないが、必要ではある)。なんか貪欲がないか考えてみるけど、正当性が見える気がしないし、C問題でさえわからなかったんだから、はあって感じ。Fは見た目簡単そうだけど、難しいんだろうなと思って少しだけ考えてみると、何もわからないになった。