競技プログラミング

訓練

青 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 大好きマンなので 、彼の視点を理解するためにも読み進めてみたい。