脳log[20221120]

2022年11月20日 (日) [AtCoder] 精進１。昨日あった ABC278-D「All Assign Point Add」(茶 diff)。クエリ１を愚直にやってはいけないのはわかる。だから Hash を使った。提出 #36620785 (TLE×2)。ちなみにこちらの提出 #36623538 が素直に配列を埋める解法で、全く同じケースに対して TLE×2。どうして２つが同じ性質を示すのかまるでわからない。昨日はもう、TLE になるはずがないと考えてしまって現実に対処するのをやめてしまった。今日の提出１#36664071 (329 ms)。配列２本を使った解法。１つにはクエリ２の累積和を、もう１つには累積和のベースになっているクエリ１のバージョンを記録した。古いバージョンに基づく累積和は無視する。今日の提出２#36664254 (351 ms)。昨日の Hash を使った解法を踏襲したもの。この提出 #36664376 (TLE×2) と比べて間違い探しをしてみよう。Hash#clear を呼ぶと TLE だが代わりに = {} で Hash を使い捨てにすると AC。ベンチマークをとってみても差が出ないので単純に Hash#clear が遅いという話ではない。謎。こういうツイートを見かけた。「AtCoderのABC278D、TLEするのでこんなところで解けないとは耄碌したなーと思ったが… unordered_mapで書いてたところを普通のmapに書き換えたら通った。普通逆じゃないかと思うんだけどまだまだC++、奥が深い。」 Ruby の Hash 実装に固有の秘孔ではないらしい。■精進２。同じ ABC278-F「Shiritori」(水 diff)。D の次に解けたのが F なので E を飛ばして F。bitDP が見えたらちょっと下手なことをしても通る制約。ただし 16 要素の順列はちょっとではない。やるだけ。でもできなかった。提出 #36668555 (AC / 66 ms)。Hash のデフォルトプロックを使ったメモ化再帰で書いた。DP はボトムアップの解法なんだけどメモ化再帰で書くとトップダウンになる。トップダウンの方が頭の中を素直に反映していて書きやすい。気をつけるべきは、DP の詳細を詰めず状態をまとめないままメモ化再帰を書いてもメモ化の意味がないし、TLE になるということ。■精進３。同じ ABC278-E「Grid Filling」(緑 diff)。これが緑 diff ってマジ？ 俺は制約を見て、h=H/2; w=W/2 のときの計算量を計算して、諦めたよ。D と E のコンボでいじけちゃったよ。提出 #36685628 (AC / 737 ms)。書いてみれば通った。２次元累積和はたぶんかなり苦手にしている。それを尺取りにしようなんてしたら脳みそがオーバーフローしてもしかたがない。実態は「書いてみれば」の語の印象の通りではない。138 ms と飛び抜けて速い提出がある>#36636856。数の種類ごとにそれを覆う最小の矩形を求めておいて、それが黒マスに含まれるかどうかを効率良く(変化量の累積和の累積和で)調べてるっぽい。累積和を使わないとこちらのように短く書けてそれでも通るっぽい>#36649717 (347 Byte / 1586 ms)。まねまね>提出 #36698536 (AC / 560 Byte / 131 ms)。答えを求める部分(末尾５行)をこういう風に書きたいというところと Array#transpose を失敗させない条件から逆算して配列の要素数と添字を調整している。ABC278_e.rb27←これを最終形にしたいけど大勢に影響しない程度の計算量の削減(※黒塗りがグリッドの上(左)にはみ出しているときの変化量を１行(１列)に圧縮した)と見た目の違いしかないので提出を控えている。■今日の ARC152 はどうだったか。自分のすべての提出。１時間半かけて２完のノルマは達成した。B の提出が完成してから 15 分くらい粗探しに時間をかけていた。粗というのは書き損じではなく考え違い。ARC では慎重になる。自分にとって２時間で３問を解くコンテストなので ABC とは違う時間の使い方ができる。昨日の ABC がひどかっただけに慰められる結果。C 問題は B 問題の後だったので図形的な意味はすぐに掴めたのだけど、そこからがさっぱり。解説放送があるよ>「AtCoder Regular Contest 152 - YouTube」。