脳log[20221112]

2022年11月12日 (土) [AtCoder] 今日は大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277) があった。コンテスト成績証。自分のすべての提出。ここひと月ほど ARC の開催が途絶えていて、そうするとレートが安定するんだなあ。今回は E 問題でも緑 diff 止まりだった一方、F、G 問題がともに橙 diff だったらしい。F 問題はてっきり自分が苦手なタイプの水 diff だと思っていたので意外。■G 問題「Random Walk to Millionaire」の方が見込みがあると思って考えている。とりあえずサンプルが合うところまではできたのだけど、これは O(KKM) であり K,M≦3000 の制約下では時間オーバー。報酬がレベルの２乗だというところが嫌らしいと思うんだよね。２乗でなければレベルの和と個数を覚えておくだけで良さそうなところが２乗だからまとめることができないでいる。レベルごとに独立して遷移を行うせいで K(移動回数)×K(レベル数)×M(辺の数) の計算が必要になってる。■F 問題「Sorting a Matrix」も考えてる。行のソートと列のソートをそれぞれでがんばれば解ける気がするんだけど、「がんばる」が曲者。行のソートは比較的問題が少なくて、列の統計情報を一度記録しておけば素直に比較ができる。列のソート。行ごとに非ゼロの列を選んでソートして列の序列を作り、マージして１本のソート列にする。入力がすべて非ゼロだった場合、最初のソートに O(HWlogW) かかるのと、扱う２項関係が 行×(行内の２項関係) = HW(W+1)/2 個存在するのがつらい。最大ケースで数十秒かかる。あと制約も曲者で、H と W のそれぞれは上限を持っていない。ものすごく縦長の行列もものすごく横長の行列も考えられる。ソート部分の logW がほぼ logHW だったとしても問題はないけど、２項関係の W(W+1) は非常によろしくない。ソート列をソート列として保持したままうまくマージする方法は。それ以前の問題として、エラーなしでは最初の提出 #36477837 (WA×12 / TLE×5) が一番 WA と TLE の数が少ないこともある。愚直にやったものの TLE が一番少ないところと、愚直なのに WA があるところが問題。ケアレスミスなのか根本の方針が答えにたどり着けないものなのか。ダメケースを１つ２つ見つけては結果が改善してるのを確認してるのに提出すると WA 数が何も変わらないのつらい。列のソート(比較)の肝は一方または両方が 0 の行では順序づけを保留することと、同値の場合はグループ化することだというのが今の理解。■@2022-11-14 G 問題。ヒントを見ました。「G は i 回目の移動で頂点 u にレベル X で来る確率が p だとすると、知りたいのはすべての i と C_u=1 なる u について pX^2 の和。(i,u) を状態として \sum pX^2 を管理しようとすると、レベルアップの処理が \sum pX^2\rightarrow\sum p(X+1)^2=\sum pX^2+2\sum pX+\sum p となる。よって \sum p、\sum pX、\sum pX^2 を管理しておけば更新も含めて計算できる。」 これがヒントであって答えでないのは、これを読んでさえさっぱり遷移が書けなかったから。何度も何度もガチャガチャやって考えてガチャガチャやって考えてお風呂に入って考えた。提出 #36502350 (TLE×13)。書けなかったのは 29 行目と 30 行目と 32 行目。それで苦労の結果が TLE。計算してみたら N,M,K≦3000 で Ds.size=3 で E.sum(&:size)=2×M で C0.size+C1.size=N だからループの回数が K×(3×2×M+N) = 6300 万。Ruby は 1000 万回を超えたあたりから厳しくなってくるのでこのままでは無理だよ。