AtCoder Beginner Contest 241（Sponsored by Panasonic）に参加しました。
結果
A,Bの2問正解でパフォーマンスが669でした。
C問題が頭で考えると簡単だけど実装が面倒な問題だった。延々とバグが取り切れなくてAC出来なかった。
D問題もざっくりとした方針は思いついたけどイテレータの操作が慣れていないからACまでは出来なかった。
A - Digit Machine
を遷移先のインデックスとしたときに
から3回遷移するとインデックスがどれになるのかを答える問題。
問題の意味がわかればすんなり解ける問題だと思う。配列が使えるかどうかを問われている問題なのかなあ。
B - Pasta
と同じ値の
が何個あるのかを管理して答える問題。mapや連想配列が使えれば簡単に解ける問題だった。
同じが複数出てくるかもしれないのでデータ構造はmapを使うのが正解だと思う。
が小さいなら配列
の最大値分の長さの配列でも対応はできると思うけど、今回は
なので配列は確保出来ないと思う。
C - Connect 6
目で見ればすぐわかるのにコードにするのは難しい… 賢い方法が思いつかなかったので愚直にチェックしていくことにして解いた。
横のチェック、縦のチェック、斜めのチェック2方向をしゃくとり法で実装しようとしたけど、少しバグってたみたい。テストケースの半分くらいはWAだった。
何も見ずに尺取法を書くのは慣れていないのもあって少し手間取った。結局ACは出来ず…
概念やアルゴリズムは理解しててもきれいにコードにするのは難しいなあ。1回きれいなコードを書いてメモしておかないとなあ。
D - Sequence Query
まずは愚直に解いてみた。
Aをvectorで用意してクエリの1つ目の値が2,3のときはソート、2分探索でx以上やx以下のインデックスを探索、k個分インデックスを移動させてそのインデックスが指す値を出力。
だけど、思っていたとおりTLE。たぶん毎回ソートするのでちょっと時間がかかりすぎていたんだろうなあ…
次に思いついたのはvectorではなくmultisetでAを処理する。setならソートの必要がないけど、同じ値が複数Aに追加される可能性を考慮して同じ値を複数含められるmultisetが適切だと思う。
あとは2分探索だった部分をupper_boundかlower_boundに置き換えて、それらで取得できるイテレータをk個分ずらせば良さそう。
問題は、k個分ずらした後のイテレータがmultisetの範囲ないかどうかを判定する部分だけど、イテレータの扱いに慣れていなくでただの不等号でbegin()、end()と比較しようとしてシンタックスエラーになった。
ここまで考えてC問題を解くのに戻ったけどCが解けなかったのでこっちに戻ってくることはなかった。
解説を少し読むと第2案がそのまま解法として載ってたから、C問題に戻らずにこっちに注力すればよかったかも。
