脳log[20210918]

2021年09月18日 (土) [AtCoder] 精進。ARC065-D「連結」(青 diff)。出力部の直前４行の集計部分がキモ>提出 #25899408。必要なのは数だけであって、具体的な組み合わせを明らかにする時間的余裕は制約により与えられていない。結果だけ見ればシンプルだけどけっこう考え込んだよ。■■■[AtCoder] 今日はサイシードプログラミングコンテスト2021 (ABC219)だった。ABC の３完(+2WA)で大爆死の回。DP っぽい D 問題「Strange Lunchbox」が解けなかった。Ruby での AC はコンテスト終了直後の時点でゼロだ。わからん。E 問題「Moat」は盤面が 4×4 なんだからどうとでも処理できる。マス目ごとに堀の内部か外部かを決めて総当たりしても高々 65536 通り。そこから堀の内部が一塊になっていないものを除外する。つまり、堀の内部が連結ではない場合と、堀の内部の内部に堀の外部が島になっている場合を除外する。盤面が小さいから横着して添字をベタ書きした。でも時間内に書ききれなかった。終了後に AC>提出 #25962480。うーん。■D 問題もできた>提出 #25964674。うん、緑 diff なのもうなずける普通の DP だった。同じ形を書いたことがあるし、すらすら書けてバグも明らかなものがひとつだけ(pop と shift の取り違え)。だけど時間に追われると DP は普通に解けない。■F 問題の「Cleaning Robot」が面白そう。橙 diff だけど。K の制約が突き抜けていて予め無駄な努力を拒絶する親切仕様。ネタバレが許されないタイプの問題だと思う。自分でネタを掴みたい。■@2021-09-30 メモ。まず１サイクル巡回して通過点と原点との関係を角度(GCD(X,Y) で割った X 座標と Y 座標)ごとに絶対値(GCD(X,Y))で記録する。１サイクルごとに原点がどこに移動するかも記録する。重複(後追いと交差)を省いて K 回分数え上げる。どうやって？