トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)に参加しました。
結果
A,B,C,D,Eの5問正解でした。
実装重めな問題が多くて、じっくり実装してたらE問題を解き終わるまでで時間切れになった。
E問題が1発ACできたから良かったけど何かバグがあったら修正する時間が無いくらい時間がぎりぎりだった。
A - Attack
体力Aの敵にBだけダメージを与えるとして何回攻撃すれば倒せるかを答える問題。ただの算数の問題。
Aから何回Bを引くと0以下にできるかを計算すれば良いので、端数切り捨ての割り算をする。 AがBでちょうど割り切れる時以外は1回おまけに攻撃が必要なので+1して最終結果を出力すれば良い。
B - Find snuke
長方形にマスが並んでいて各マスに何かしらの英字が書かれているので、1箇所だけ存在するsnukeと言う並びの場所を探して位置を出力する問題。
長方形のサイズはそれほど大きくはないので全探索を縦、横、斜め分行えば良い。
念のため右から左とか下から上方向に並んでいる場合でも検出できるようにコードを書いたけど、そんなひねくれた場合の考慮はいらなかったかも。
丁寧に全探索すれば解ける問題だと思う。
たまにある、マス目の中から特定の何かを探索する問題。探索を簡単にできる書き方があった気がするけど覚えてなかったので愚直に探索して解いた。
（グローバル変数で探索する長方形を宣言して、探索用に関数を用意して引数として開始位置と探索する方向を渡してどうこうするって解き方だった気がする。縦と横の探索する方向を1とか-1とかで制御すると1つの関数で縦、横、斜めとそれぞれの逆順どの方向の探索も対応できるとか言うやつだった気がする。）
C - Almost Equal
M個の文字列が与えられるので、それらを並び替えて隣り合う文字列が1字違いにできるかどうかを答える。
文字列を頂点、1字違いの文字列同士は無向辺で繋がっているとみなすと、与えられたグラフの連結成分が1つになるかどうかを答える問題と見なせる。
連結成分の数が知りたいことになるので、Union-Findで解くことにした。
文字列の数も長さも大したことないので全組み合わせで2つの文字列が何字違いか数えて、1字違いの場合は同じ連結成分に統合していった。最後に各文字列がどの連結成分に含まれているのかを確認して、連結成分の数が1個になっているかどうかで答えを判断して答えた。
D - Impartial Gift
AとBのグループからアイテムを1つずつ選んで、条件を満たす組み合わせの中から価値の最大値を求める問題。
2つのアイテムの価値の差がD以下になるように選ばないといけないのがちょっと厄介かな。 Aグループでアイテムを1つ選ぶと、Bグループの中から選べるアイテムの候補が決まって、その中から価値が最大のものを選ぶような処理を実装できれば良さそう。
Aグループからアイテムを1つ選び、Bグループの中から選べる価値の上限を計算する。Bグループの中から計算した上限に1番近いアイテムを探して、2つのアイテムの価値の差がD以下なことを確認しつつ価値の和の最大値を更新する。この処理をAのアイテム全通り行えば解ける。 Aはループなりで全通り確認すれば良い。アイテムが1つ決まってからBグループの中から探索するのは2分探索を使えば計算量を抑えながら探索できる。
E - Isolation
クエリを処理しながら条件を満たす頂点の数を出力する問題。
クエリの内容は
- ある頂点とある頂点を辺でつなぐ
- ある頂点から伸びている辺をすべて削除する
の2通りで、各クエリの処理後に、どの頂点とも辺で繋がっていない頂点の数を答える。
クエリの数は多いので、各クエリの処理後に全頂点に対して辺を持っているかどうかを確認していたらTLEになりそう。
欲しいのは辺を持たない頂点の数で、ある2つの頂点を辺で結ぶと1か2減るし、ある頂点の辺をすべて削除すると1以上増える。辺を追加したり削除するときに両端の頂点が他に辺を持つかどうかで答える値が変化するので、
要素数が簡単にわかって、かつ、指定した値を簡単に削除できるデータ構造で処理すればなんとか解けそうと思った。
いくつか使い慣れたデータ構造を見ているとsetなら条件を満たしていそうなのである頂点に隣接する頂点はsetを使って管理することにした。
辺を追加する時は、その頂点が他に辺を持たないか確認し、辺を持たないなら答えが1小さくなる。これを2頂点ぶん処理すれば1つの目のクエリは対応できる。
ある頂点vの持つ辺をすべて削除する時はその頂点vに隣接する頂点それぞれに対して、隣接頂点のリストからvを削除し、隣接する頂点が0になれば答えが1大きくなる。最後に頂点vの隣接頂点リストをクリアして答えを1大きくする。 これで2つ目のクエリに対応できる。
こういった具合で2つのクエリそれぞれの処理を実装して、管理している答えを出力する。
