ABC278

6完。Bを飛ばすとかそういう次元じゃなくFまで典型やるだけ(実装クソ重)じゃん。ABCに参加する価値がとても低くなっている。

A - Shift

KがNより大きいかもしれないのがいやらしい。dequeでやった。

B - Misjudge the Time

Clarにあった同じ数字を入れ替えるやつ気づかなかったね。まあこれは気づく必要ない(問題文がちゃんと読めている)。20時台だと一の位にも制約がかかるというのが最初認識に乗ってなかった。時計を1分ずつインクリメントする処理はまあ書けるので、あとは桁をバラバラにして条件を書く。

C - FF

時事ネタっぽい(Twitterが話題になっているので)。なんか大げさに考えてしまったけど、unordered_mapにunordered_mapを載せるかという段階になってようやく、フォローの矢印をunordered_setで管理するだけと気づいた。順序が付いた2ユーザーの組の有無を管理する。

D - All Assign Point Add

かなり簡単そう。具体化するのはけっこう大変だった。最後に全体をxで塗りつぶした時刻を持っておく。Aの各要素に対し、塗りつぶしを最後に反映させた時刻を持っておく。A_iにアクセスするときは必要ならxにして時刻を更新する。意外と実装が重い。解説わからん。

E - Grid Filling

種類数は難しい。Nが小さいので存在するかという問題をN回解こう。存在するかを知るには個数がわかればいい。制約を見ると差分計算するだけでよさそう。しかも横方向にだけ差分計算して縦に動いたら計算し直しでいい。実装自体はけっこう重くて、定数倍高速化をする余裕がなかった。

解説、原案者の想定解法すごい。数えない方法があるんだ。

F - Shiritori

前にも同じ問題名あったよねとAtCoder Problemsで検索してしまった(あった)。Nが小さいのでDPするだけ。文字列は最初と最後の文字だけを保存する。しかしかなり脳を破壊される。普通にbitDPするとありえない状態も処理してしまう。DPで直前の整数を持つのか直後の整数を持つのかややこしい。初手が何でもいいというのも表現しづらい。結論としては、残っている整数がkで直前に選ばれた整数がiのとき手番側が勝ちならdp[k][i]=1(負けなら0)。ありえない状態は、普通に処理したうえでDPの遷移のときに無視する(というかありえる状態からは触れないけど)。最後に、N通りの初手を試して相手が負けになるのが一つでもあるかを調べる。

え、解説何やってんだこれ。

G - Generalized Subtraction Game

とりあえずGrundy数を愚直に計算してみる。使えそうな規則性は見られない。大体先手が勝ちそうではある。実行してみて意外と速い。コードをよく見ると3乗にはなっている。L=Rなら間に合いそう。しかしLとRの差が大きいときに高速化できそうかというと無理。そもそもGrundy数が計算できたとして実装が間に合う気がしなかった。

解説見て、いやあ真似っこ思いつかないのさあ。この前のARCで出たからGrundy数はすぐ計算できる。それはいいけど他の発想が完全に潰れてるじゃん。

(追記)ACしたけどこの実装をコンテスト中にやるのは無理だ。これ要求されるのきつすぎ。