競プロ練習: EDPWを解けずに終わった

Posted on 2 mins read

これは戒めのメモ。DPに慣れたくて、後述する記事を一通り読みながらリンクされた問題を解いてみた。 AtCoderには教育目的のコンペもいくつかあり読んでいた記事からたどり着いた。 そのなかでW - Intervals が解けずに立ち往生している。 どうしても最後の2つがWA。。あまりにもWAが続くので一度、諦めてしばらくしてから戻ってくる事にした。遅延セグメントツリーの問題なのかDPの設計や境界条件の考慮に問題があるのかわからない。

勉強中に得た成果: ojコマンド

調べてたら ojコマンド にたどり着きました。 問題のダウンロードや提出、自作した入力生成スクリプトと組み合わせて大量のテストケースを作ったり、TLEな別実装で回答を生成したりできる。便利だ。

でも TLE は打ち切られちゃうので本当に正答を返してくれるかは謎ってところが悩み。 ちなみに、これを使っても突破できず。

1

$ oj login https://atcoder.jp

とりあえず通してやった記事・解き残しのある記事・再読予定あたりを記録する。

DPで知ったこと

前にDPは順序が必要でインスタンス同士の関係がDAGじゃないとダメって思ってると書いたけどDAGとは限らないらしい。 DAGじゃないときに無理やりDPを複数回やることで突破するような問題もあるらしい。

複数の更新と問い合わせを繰り返すデータ構造としてフェニック木(BIT)、セグメント木、レンジ木、遅延セグメント木を知った。 遅延セグメント木は解けてない問題に絡んでいて実装できてるか不安。

それぞれのデータ構造を適用できる集計は利用する演算の代数構造によって決まる。 型変数でその辺を使って多層型としてコレクションを定義できる言語いいなぁって思った。 あと逆元がない群(単位元を持つ半群)をモノイドと呼ぶらしい。 セグメント木ではモノイドによる集計を扱える。基本的な代数も復習したい。

読んだ記事とか積み残しとか

一通りやった

リンクされた問題を残している

流し読みで再読予定

解き残し

あとまわし

読んでいて面白いのはこのあたりだった。けどもう少し基本的なことを素早くできないとなぁってことで我慢している。 大学とか高校の数学が楽しいけど単純な計算問題を手早く解けるようにしとく方が考えられる範囲が広がるよなぁって感じ。

comments powered by Disqus