競技プログラミング
訓練
回し車に乗ったハムスターのようにタイピングしていた。
もとい、寿司打のスコアで 14,000 円が安定して出るようになった。俺達の戦いはこれからだ。
ARC 168
ARC 168 に参加した。 1 完 (A) だった。
A 問題 では連続した
> の数に注目すれば算数になった。いわゆる『ギャグ』は ARC
序盤に頻出……俺自身がギャグとなることだ。
B 問題 では未知の『Grundy
数』が問われた気がして迂回した。先に鉄則本を解こう。
C 問題 は数え上げが難しい。
ARC の王道か。
D 問題 は
イウイ
の類題だったが考察ができなかった。 Upsolve した。
ABC 330
ABC 330 に参加した。 5 完 (A ~ E)
だった。
A 問題
では寿司打の成果を出せなかった。まだ Keyball の記号入力が難しい。
B 問題
では誤読を積み重ね灰色パフォが出た。整理すると
clamp
にかければ良かった。やはり水色になっても頭が良くなったわけではない。
C 問題
では平方数を列挙して二分探索した。境界の左と右を両方試す必要が合った。極値の探索という意味で
3 分探索でも解けるみたい。こうしたシンプルな問題で練習しておくのが良さそう (未履修) 。
D 問題
では行ごと、列ごとにイテレートするため generate を使用した:
let !rows = U.generate n $ \y -> U.length . U.filter id $ U.generate n $ \x -> gr @! (y, x)
let !cols = U.generate n $ \x -> U.length . U.filter id $ U.generate n $ \y -> gr @! (y, x)
E 問題 では mex
を探すためにセグメント木を使用した。
F 問題 では x, y
成分を独立に考えればよかった。辺の長さで 2
分探索しようとしたが、正方形の最適な配置が分からなかった (重心を選ぶとサンプルで落ちた)
。
evima 氏の解説
に最適な配置が載っていた (まだ理屈は分からず) 。コストの計算は \(O(N)\)
の全探索で十分間に合うようで、シンプルな実装で upsolve できた。
Misc
Haskell 本: 進捗 5%
すべての原稿を消し飛ばしてしまった。細かい情報を詰めていただけにショックだ。
テトリス棒になって全てを消し去りたい
。
枝葉末節を大胆にカットすれば良い気がしてきた。 doctest の
$setup に type defaulting
を書くとか、重要ではない情報に拘りすぎた。
果たして重要な情報が残るのかが不安ではある。