競技プログラミング
AHC 024
先週日曜に AHC 024 に参加した。トポロジーを保って格子上の図形を縮小せよという問題だったと思う。たとえば以下の『地図』が与えられる:
それぞれの『区』の隣接関係を保ったまま、地図全体を小さな面積に圧縮すると高いスコアが与えられる。ただし内部に穴を開けてはならない。
しばらく悩んだが、外縁の区のセルを削ることしかできなかった。歯は立つが食い破れず？
左上に注目すると、 3 行 4 列目のセルが橋になっている。このようなセルを削ると WA になるため気を遣った:
削って良いセルの判定方法 (Chokudai さん)
8近傍だけで連結性を良い感じに確保し続ける典型みたいなのあるから置いとくね。今回は連結性維持の関係で下は要らないけど、下のテク結構大事な問題もおおめ。
— chokudai(高橋 直大)@AtCoder社長 (@chokudai) September 25, 2023
焼きなましはこれでやって最後0.1秒で連結性厳密にして山登りとかするとほんのり伸びる印象#AHC024 pic.twitter.com/7AoBAlusUR
訓練
引き続き AtCoder Tags で 青 diff DP を探して 解いた。 数え上げの問題 で計算式を整理できずに途方に暮れたが、フィボナッチ数列に近かったらしい。
思えば、愚直解を作って答えを並べれば良かった。数学的考察は抜きに、法則性は見つけられたはず。似た経験も 1 つや 2 つではない。
したがって、今回の ABC では『愚直解を余分に作る実装力』をテーマにしたい。数学的能力を期待するのはその後でも遅くない。
ABC 322
ABC 322 に参加した。実況を録画したので、文字起こし〜読み上げまでを自動化して遊んでみたい。 Siri でさえピッチを下げると快適になるのだから、合成音声には可能性を感じる。
| 順位 | パフォーマンス | レーティング変化 |
|---|---|---|
| 2,327 | 1,036 | 1,261 (-14) |
A 問題 では zipWith3 で長さ 3 の窓を左端から右へ流した。
B 問題 では添字で混乱した。実は isPrefixOf, isSuffixOf という関数があったらしい。
C 問題 では状態を持って右から左へ走査したが、状態管理で戸惑った。実は単なる map で計算できたので、次は stateless に解く発想を持ちたい。
D 問題 では全探索すると \(10^8\) 程度になって間に合わないと思ったが、テストケースが弱めで助かった。枝刈りできるようなので復習したい。
それでも 45 分で解けて大して悪くない。 A 〜 C で 20 分使った方がまずかった。
E 問題 では進数変換のバグが取れなかった。苦手分野なのでライブラリ化しておきたい。
F 問題 では遅延セグメント木が出たらしい。最大流も ABC で出るようになったし、順当に PAST 上級を目指していけば良い気がする。青 diff DP と PAST をやろう。
読書
入門監視 を読み終えた。しばしば過去の考察を引用する展開が熱い。ネットワーク監視はプロトコルがレガシーで最悪というのも面白かった。
React の本を買い、 8 ページ読んで投げ出してしまった。文語として校正してほしい。
気を取り直して 数学から創るジェネラティブアート を読み始めた。数式を使って迫力のある絵を描けるみたい。ミラーボールも回せるようになるだろうか。
Misc
記事を書くのに tempel スニペットが大活躍した。特に ABC の番号を書けば、すべての問題へのリンクを生成してくれるのが助かった。
スニペットの定義ファイルでは、以下のように S 式が並ぶ。これが (スニペット名 → スニペット内容) のマップとなるのだから冴えている。インデントが無い上に変数を自然と書ける。
;; `src' スニペット
(src "#+BEGIN_SRC " (p "hs") n> "#+END_SRC")
;; `abc' スニペット
(abc "[[https://atcoder.jp/contests/abc" (p "300" no) "][ABC " (s no) "]] に参加した。
[[https://atcoder.jp/contests/abc" (s no) "/tasks/abc" (s no) "_a][A 問題]] では
[[https://atcoder.jp/contests/abc" (s no) "/tasks/abc" (s no) "_b][B 問題]] では
[[https://atcoder.jp/contests/abc" (s no) "/tasks/abc" (s no) "_c][C 問題]] では
[[https://atcoder.jp/contests/abc" (s no) "/tasks/abc" (s no) "_d][D 問題]] では
[[https://atcoder.jp/contests/abc" (s no) "/tasks/abc" (s no) "_e][E 問題]] では
[[https://atcoder.jp/contests/abc" (s no) "/tasks/abc" (s no) "_f][F 問題]] では")