脳log[20221105]

2022年11月05日 (土) [AtCoder] 今日は ABC276 があった。コンテスト成績証。自分のすべての提出。AC までの所要時間は A=２分、B=３分、C=16分、D=５分、E=16分、F=32分。青パフォで Highest 更新でいい日だなーと思ってたんだけど、E、F がそれぞれ緑 diff、水 diff だったと知って AtCoder の参加者に畏れをなしている。結局あれだ、簡単に解ける問題を(やや)早く解いただけ。実際考えるところは F 問題までなかったし、F 問題も実装しながら考えを固めていった感じ。■A 問題「Rightmost」。サンプルに助けられた。String#index で書いていたところを String#rindex に修正。■B 問題「Adjacency List」。教育的問題。グラフ問題で辺の集合を受け取って頂点本位の隣接頂点リストを作成する練習。■C 問題「Previous Permutation」。100 要素の順列を全探索はできない。入力から直(じか)に直前の順列を作成したい。サンプルを眺めるだけでも手の付け所はすぐにわかると思う。辞書順で後ろにあるものは必ずどこかで隣接２要素の大小関係が初期状態から逆転して降順になっている。それを１段階解消したものが直前の順列。最も後ろの逆転が最も辞書順に与える影響が小さいので解消すべきはそれ。あとはサンプルを見ながら実装をがんばる。けっこう面倒くさかった。これは今の思いつきだけど、普通の数って組み合わせの数じゃない、それを順列の数に変換する手順があれば、K-1 にその手順を適用するだけで答えになりそうだけど、そういう手順はないのかな。10 進数を 2 進数に変換するみたいな手順。……。できそうだけど K がべらぼうな大きさになるからうまみがない。■D 問題「Divide by 2 or 3」。できる操作は素因数から２と３を取り除くだけ。とりあえず全部の２と３を取り除いてから全体が一致するかを比較したり、不必要に取り除きすぎた２と３の分の操作回数を補正したりするのもありだけど、全体の GCD を予め求めて A 数列から取り除いておくのがやりやすいかな。■E 問題「Round Trip」。グリッド問題は制約を一番に見る。一瞬、行と列のそれぞれが１メガだからすべてのマス目をなぞることができないのかと思ったけど、行と列を掛けたマス目の合計が１メガに収まるという制約だった。どうやって環状のパスを見つけるか。スタート地点の上下左右をスタート地点にして(ややこしい！) BFS で陣取りをしていって、異なる陣地がぶつかったときに Yes かなと思った。スタート地点の上下左右からどれかをスタート地点にその他をゴールにして BFS なり DFS をするのもありかな、とは終了後に考えた(※元のスタート地点を経由する長さ２のパスを抜かりなく除外すること)。グリッド問題をグラフに見立てて辺を陽に持つのは原っぱのようなグリッドのときに厳しいかな。大は小を兼ねるというけどサブクラスに固有の最適化を手放す余裕が Ruby にあるかどうか。■F 問題「Double Chance」。制約が 20 万なので累積的に求めていかなければ時間が足りない。カードが１枚ずつ増えていくときにそのカードの寄与を考える。最初は答えそのもの(期待値)を更新していこうとしたが、これはうまくなかった。K 枚での期待値と K+1 枚での期待値では分母が異なるので、直前の分母を掛けて今回の分母で割って、など面倒くさい。すべてのパターンの max(x,y) を合計したものを累積的に更新するのが良い。K=1 なら 1 通りを合計したもの、K=2 なら 4 通りを合計したものを記憶する。K が k から k+1 に増えるときは (k+1)*(k+1)-k*k = 2*k+1 通りの max(x,y) を加算する。更新しながら利用できる累積和が必要なので BIT の出番。BIT は(配列を使った累積和と比較すると)取得が対数時間になってしまうけど更新も対数時間で済むのが嬉しい。■G 問題「Count Sequences」(黄 diff)。とっつきは悪くないと思ったんだけど、愚直解も作れないのでは論外。