競技プログラミング
訓練
青 diff の AC 数が 50 を超えた。自力で解ける気配は無い。
マスター・オブ・場合の数
の §1 を解いた。意外と DP の観点が役立つ。
ABC 335
ABC 335 に参加した。 4 完だった。
感想
今回も手続き型言語 Haskell でゴリ押ししてしまった。
茶 diff の C, D が難しかった。来週は緑色コーダーに戻るかもしれない。
解法
A 問題 では
(`snoc` '4') とか (<> "4") が書けたら格好良かった。
B 問題 は
nubSort $ 全探索 の形で解いた。タイピングが苦手なので、空白区切りの
putStrLn をスニペットに入れようと思った。
C 問題
ではスネークゲームを連想して混乱した。先頭の残像の位置が問われると思えば、可変配列をリングバッファとして使ったり、
cojna/iota の Data.Buffer に
pushBack していけば良かった。
より上手な解答として可変配列を使わない提出が見れた。
scanl
で位置の一覧を作ってから、改めてクエリに答えていくみたい。頭を使う必要があって難度は上がると思う。
D 問題
では螺旋状に答えを作っていけば良いことが分かった。内周がこれ:
--|
|T|
|--
1 つ外側の周がこれ:
----|
| |
| T |
| |
|----
それぞれの周を描くためには、左上の頂点からスタートし、長さ \(2 i\) の辺を 4 回描いた。
accumArray などは使わず、可変配列へ都度答えを書き込んだ。
別解としては、外周から始めて内周へと近づいていけば、壁 or 探索済みのセルにぶつかる度に 90
度回転するだけで済むため、簡単になりそう。
E 問題
は苦手なグラフ問題に見えて飛ばした。最長距離を求める不思議な問題だった。
コンテスト後に Dijkstra や 01-BFS っぽいのを投げてみたものの TLE
。もともと最短経路を求めるアルゴリズムだし、やっぱり上手く行かないみたい。同じ数が振られた隣接頂点を
1 つに潰すと DAG になり、 DP で解けるそう。後でやってみる。
F 問題
が解けなかった。右端から計算する方針は立てたものの、高速化ができなかった。
evima さんの解法
に従って \(dp[x][i \bmod x]\) を周期和とすることで upsolve できた。力こそパワー……
読書: PBT 本
実践プロパティベーステスト
を 28% まで読んだ。ジェネレータが生成したテストケースを分類し、何 %
のテストがどの分類にあたるかを確認できることを知った。
実際、ランダムなテストケースを作るだけでは、境界値を見れず素通りする確率が高い。 AtCoder
における QuickCheck
の使い方としては、実質的に総当たりをしていた。自分でループを書いても良いが、失敗したケースの表示まで
QuickCheck がやってくれる点が便利だった。
PBT 自体の良さはまだ感じ取れていない。
matklad 氏が invariant 大好きマンなので
、彼の視点を理解するためにも読み進めてみたい。