大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)に参加しました。
結果
A,B,C,E問題の４問正解でした。
D問題は問題文を読んで難しそうだったから後回しにした。E問題を終わらしてから解き始めたけど最初に思っていたよりは難しくなさそう。
A - ^{-1}
問題文の通りに処理する。
与えられた数列Pのうち指定されたXとなる項番を出力する問題。
ループで先頭から順番に値がXとなる項を探していけば良い。数列の長さも最大で100程度なので線形探索で十分間に合う。
項数が大きいと何かしらの工夫が必要になってくる。
B - Playing Cards Validation
これも問題文の通りに実装するだけの問題。
3つの条件を愚直に実装すればいいけどちょっと手間がかかる。 １つ目と２つ目の条件に関わる文字を連結して文字列にしておいて、チェックしたい文字がその文字列に含まれるかどうかを検索すれば判定は楽にできそう。(コンテスト後に気づいたから本当に解けるかの確認はしていないけど)
C - Ladder Takahashi
1階層をノード、はしごを辺とみなすと、
ノード数が極端に多いけど辺の数はそれほど多くないグラフでどれだけノード番号が大きいノードにまでたどり着けるかを答える問題と見なせる。
深さ優先探索や幅優先探索で探索すれば十分だと思う。（ノード数が多すぎるので線形探索だと階まで探索する前にTLEになる。そもそも線形探索だとどうやって解くのかすぐには思いつかないけど…）
工夫すべき点としては以下かなと思う。
- 辺のないノードの方が圧倒的に多いので辺を持つノードだけを対象にして、辺を持たないノードは存在しないものとして扱う。
今回は連想配列を使って辺を持つノードだけ隣接ノードを管理した。 あとは普通の幅優先配列でどれだけ上の階層へ行けるのかを更新しながら処理をしていった。
D - Takahashi's Solitaire
問題文にmodとか出てきてなんか面倒そうな印象を受けた問題。
問題文をよく読むとそれほど難しくなかった。結局、手札から好きな数字のカードを1枚出して、以降はそれと同じか1大きな数字のカードを出し続ける。数字の最大値はM-1でその次に出せるカードは0といった具合に大小関係が循環している。
最終的に手札のカードの数字の合計をどれだけ小さくできるのかを答える問題。
まだACはできていないけど問題文を読んで考えた方針としては以下の通り。
- 手札Aはソートしても問題を解く上では問題ない。
- 数字がXのカードを出したとして、手札にXがある限りXを出し続け、XがなくなってからX+1のカードを出す。
- はじめに手札の数字の和を求めておいて、捨てるカードにかかれている数字をまとめて引く。
- XとX+1が連結していると考えて、尺取法あたりで連結部分のカードに書かれている数字の和を求めて、1番和が大きい部分を手札から捨てることにする
コンテスト後の時間も使って上記を実装してみたら一部がWAだった。コーナーケースかなあ。
E - Crystal Switches
ちょっと変わった最短経路の距離を求める問題だと思った。
変わっていると思った部分は、以下の通り。
- スイッチの状態に応じて辺の通れるかどうかが変化する。
- 一部のノードでは辺の通れる・通れないの状態を一斉に反転させられる
通常のダイクストラ法に状態管理の要素を加えれば良さそうだと思ったので、ダイクストラ法をベースとして解いていった。 大きくは以下の変更をした。
- 辺の情報に初期状態で通れるかどうかを追加する。
- ノードの情報にスイッチを持っているかどうかを追加する。
- 優先度付きキューで管理する情報にスイッチのON/OFFの状態を追加する。
- 距離を管理する配列の次元を1つ増やしてスイッチがONのときの最短距離、スイッチがOFFの時の最短距離を管理する。
あとは距離情報を比較・更新する処理でスイッチの状態を考慮するようにした。
実装にちょっと時間がかかったけど一通り実装したら大きな問題もなくACできた。
