ABC312Dに挑戦

コンテストの結果はさんざんだった。あとからやってみたら素直に解けて、これが本番で出来ていればと思わずにはいられなかった。本番の状態ではとてもじゃないけど、できなかったけどね。

たまにあるABだけ解けた、という状況である。ABの2問しかACできないと非常に凹む。こういうのが続いて足が遠のくことになった。仕事でもないのにしょうもな、と投げやりになりたくなる。

個人的な問題だけど、プログラミング中にタイポが多発して集中力が崩れてしまった。Keyball39でのプログラミングタイピングがまだ慣れていないのもあるけど、それにしてもタイプミスが多い。キーの配置を見直したほうがいいのだろうか・・・。

Bも解くのに時間がかかった。実装が大変だった。

Cがとにかく混乱の元で、自分で考えた方法が何故違うのかが理解できていない。解説見たらあっさりした解法でまったく理解できない。エッジケースで落ちているのはわかるが・・・。もっとも、本番中にはサンプルのケースの時点で正しい答えが出力できずに時間がきてしまった。

https://atcoder.jp/contests/abc312/tasks/abc312_d

パッと見てDPを使うんだろうなというのはわかった。もうちょっと考察していれば本番でも解けていたかもしれない。少なくとも個人的にはCより簡単だったかもしれない。

(()????)というような文字列が与えられて、正しいカッコ列が何パターン作れるかを答える問題。

正しいカッコ列にできるかどうかと、できる場合に?を置き換える方法がいくつあるか数え上げるという2つの論点が混じっている。ただやってみると意外とDPの遷移は単純であることがわかる。

カッコ列が正しいかについての判定については、最近やったことを思い出せた。O(n)で判定できる。

簡単に言うと、前から順番に見ていき、(なら+1)なら−1していく。途中でマイナスにならず、最後に0になればそれは正しいカッコ列ということになる。これをこの問題に応用したらよい。

DPテーブルを考える上で必要な変数は2つ。

• 入力の何文字目を処理しているか
• カッコの開きの個数

これで前から順番に見ていけば良さそう。

dp[i][j]をDPテーブルとして、i文字目で開きカッコがj個ある状態として考える。最終的にdp[s.len()][0]が答えになる。最後の文字までいったときにカッコ列として成立する0の値を見ればいい。

jの部分については、問題文の成約である3000文字分とることにする。本当はそんなに必要ないのだけど。実際にはその半分あれば十分というか、入力の文字列の半分の長さがあればよい。

例えば????で全部開いていった場合はカッコ列として成立しない。イメージとして、見る部分は入力文字列の半分までは山なりに増加していくけど、残りは減る方向だけになる。なぜなら見たところでカッコ列として成立しないからである。重要なのは最後に0になるパターンのみであり、成立しない部分まで見るのは無駄なので省略できる。けど今回はしていない。

開きカッコの数の遷移については、()?それぞれで処理が違うので注意が必要。

• (の場合、dp[i+1][j+1]=dp[i][j]する
• )の場合、dp[i+1][j-1]=dp[i][j]する
• ?の場合は、j+1とj-1の2パターンに分岐する

どこで数が増えるのかというと、?の分岐するときに数が増加する。基本的には遷移前の値をコピーするだけ。ただ分岐の際にカッコを開いたときと閉じたときの両方からコピーしてきた値を足し合わせることになる。間違っても+1しないように。あくまで両方の分岐の結果増えるのである。

私はdpを次の状態へ配る形で実装したけど、もらう形で実装しても良い。

jをどこまで見るかをmjという変数で管理したが、今思えばi+1まで見ればよいのか。mjはmax_jの略で、最大の開きカッコの数を管理するつもりだった。実装していく最中に細かい思い違いに気づくパターン。本当なら実装前に気づいておくべきだが。

提出したものは最後まで開き続けるパターンもそのまま処理しているが、残り文字数より多いときは飛ばすようにしたほうが効率的かも。この問題では3000文字しかないので、無駄に見てもたかが知れているので実装面を優先した。

自分の提出: https://atcoder.jp/contests/abc312/submissions/44150160

DP問題を考えるコツが掴めたような気がするけど、こうやって自分で解説書いてみると再現性については疑問がつく。漸化式をちゃんと考えるのが近道だというのはわかった気がするが、開きカッコの数を添え字にしたらよいのではというヒラメキが全てな気がする。その部分がまだうまく言語化できないでいるから、DPの問題が解けたり解けなかったりするんだろうなあ。

実装面でいうと、jを0からmjまで動かす部分がよくわからなくなる。実装として無駄な気がしているが、計算量から考えて問題なければ無駄でもオッケーという考えでいくことにしてから、多少解きやすくなった気がする。ナップザック問題とかその典型。今回のも少し動かし方迷ったが、少しは慣れてきたのかもしれない。

しばらく前から競技プログラミング活動を再開した。

理由としてはプログラミング能力の衰えを実感しているからである。割と真面目にできなくなったと感じている。コンテストの結果については、やればやるだけパフォーマンスが落ちているので、実際に落ちているのだろう。

使用する言語は、前まではKotlinにこだわっていたが、今はRustで参加している。使っている言語でやるのが一番と思っていたが、バージョンの乖離が無視できないレベルになってきているので、Kotlinを使うのはやめた。

Rustを使っているのは、なんとなくだったような気がする。cargo-competeの存在は大きい。これがあるだけで提出が楽になる。それがRust使っている理由として大きいかもしれない。

RustはRustなりの辛さがあって、たとえば型が違うときに融通が効かない。配列の添字にはusizeを使わないといけないので、indexがマイナスになったら落ちるとか。そのため今回の問題でもj.checked_sub(1)でマイナスにならないよう配慮してある。文字列の入力で戸惑ったりと、本質ではないところでハマることも多い。それでもやってるうちに慣れてきた。

これまでは単純に解いて終わり、だったが最近は本を買って勉強するようにしている。

アルゴリズムと数学が基礎からきっちり身につく、という触れ込みだが数学が全くできない人向けではないのかなあと感じている。全部が全部とはいわないが、数学の解説が細かいところまでされているとは言い難い。数学の教科書読んだほうが早い気がしている。

最大公約数については説明あるものの、章末問題で最小公倍数の問題が出る。そういう説明について端折られているので、AtCoderの解説がわからない人にとってはこの本もつらいのではないのかという気がする。けんちょんさんの解説記事の方が読みやすい気がする。