こんばんは、ゴドーです。
ほぼ毎週土曜日に開催されている競技プログラミングコンテスト「AtCoder Beginner Contest」、通称「ABC」。
数学力を試される問題が多く出題されることが特徴で、頭の体操として都合がつけばチャレンジするようにしています。
パフォーマンス次第でレーティングが増減するので、より上のランクを目指すという数値目標がモチベーションになるのもいいところですね。
今後はABCに参加後、コンテスト中の思考の流れをメモする記事を書いていこうかと。
その時々の思考の流れを記録していくというこのブログの趣旨と大きく外れませんし、ただ問題を解きっぱなしにしていくのではなく、考えを言語化して整理していくことは学習効率を高めてくれますからね。
＊ ＊ ＊
というわけで、さっそく昨日参加した「ABC 273」のメモを。
A~Eの5完で715位でした。
A~Cはほぼstraightforward。
Bの四捨五入は初めて解いた気がしましたが、桁ごとのfor文を書きながら自然と発想できました。
Dについては、ルール自体はわかりやすく、進行方向上の壁を高速に探索すればよいことはすぐ分かりました。
グリッドサイズが大きいですが、直線移動するだけなら上下/左右の方向ごとに壁のリストを持てばよく、高速に壁の位置を見つけるために２分探索できるsetで実装。
実装自体はスムーズでしたが、壁にぶつかる以前に止まる可能性を何故か忘れてWA連発。
グリッド端へ行く手前で止まる可能性は発想できたのに、なぜか壁については発想できなかったのが不思議です。
WAが相当出たときは、そもそも基本的なルールの何かを見落としている可能性が高いですね。
Eについて、正確な計算はできませんでしたが、安易に配列を記録していくのはコピーの計算量を考えて不可能であろうと。
アカシックレコードのように一つの配列を保持し、SAVEしたときの位置だけを保持すればよさそうだと考えましたが、LOADやDELETEによって配列が変わっていくので、同じインデックスでも値が変わりうることから、２次元配列で実装することを考えました。
ただ、２次元配列だけではLOADはできても、DELETEで戻る先がどこになるのか分からないことに気付き、ADD時に２次元配列を１つ進めると同時に、前の位置に戻れるよう位置関係を連想配列で持たせることにして、制限時間ギリギリでAC。
２次元配列上に前後関係の連想配列を持ち込んだ時点でグラフ的な絵が浮かんでいましたが、解説を読むまで要は”根付き木”であることは認識できていませんでした。
問題文通りに配列から発想を始めたので辿り着けませんでしたが、なるほど確かに、スタックに対する追加・削除の記録は根付き木で表現されますね。
たとえグラフを想像できていたとしても、”根付き木”という概念として認識できているかどうかで理解の解像度が変わってきますし、あらためて言語化は大事だと思った次第です。
＊ ＊ ＊
ABC 272 の振り返りはこんなところでしょうか。
書いてみて改めて思いますが、自分以外の人が読んでもまったく分からない記事になりますね。
まあ、元々このブログはマネタイズするつもりが皆無だし、読者想定は未来の自分しかいないので、特に気にはしませんが。
ブログ記事のネタに困るときも多いので、ネタ切れ対策としても、今後もABC振り返り記事を書いていこうと思います（笑）
それでは、また。
/ゴドー
