AtCoder Beginner Contest 183の解法・感想
ABCに出るのは久々でした。
100-200-300-400-500-0(2)で0ペナ5完1500点。
B - Billiards
入試数学とかでよく見る考えで、「ある面で跳ね返る」というのは、「その面と対称な空間を考えたとき、面を跨いでその空間へ直線移動する」ことと同じである。
今回は始点と終点が決まっていて、反射するのは1回と決まっている。よって、例えば終点を軸を対称軸として反転させた位置に設定すれば、「始点と移動後の終点を結んだ直線」と「軸」との交点を求める問題になる。
2直線の式が出ているので、方程式を解けば交点が求まる。「軸」と交わるというのはであることと等価なので、始点と終点を結んだ直線の式にを代入してを求めればよい。
計算量は、。
C - Travel
制約より、どの2都市を選んでも移動可能である。都市からすべての都市を通って戻ってくるようなルートの数は、都市から都市までの巡り方の数に等しく、通りである。制約の最大値がであり、すべてのルートに対して移動時間を計算しても間に合いそうなので全探索する方針で実装する。
このように、その通り数が階乗で表されるような全探索を界隈では順列全探索と呼んだりする。実装の詳細は省く。長さがの順列を生成した後その各項の数を都市の番号と紐づけ、実際にかかる移動時間を計算する。
計算量は、となり、実行時間制限に十分間に合う。
D - Water Heater
ある区間が決まっていて、その区間内すべての要素に足す…という処理を回した数列が欲しい。ただ、愚直に実装すると計算量がとなり間に合わないので、imos法を使って解く。アルゴリズムの詳細と実装方法の説明は省く。
imos法を用いることで、計算量をに削減することができた。あとは、生成した数列の全ての項がを超えていないか愚直に判定すればよい。この処理自体はで出来る。
全体の計算量は、。
E - Queen on Grid
動的計画法で解けそうだが、遷移方法が複雑になりそうなので細かく分けて考える。
まず、横一列にマスがつながっている場合に、各マスに移動する方法がそれぞれ何通りになるのか考えてみる。最初のマスにはすでに駒が置かれているので通りとして考えると、それぞれのマスに対する移動方法の通り数は以下の通りとなる。「あるマスより手前にあるマス」からならどのマスからでも移動可能なので、通り数はそのマスより前のマスの通り数の合計となる。
しかし、いちいちそれまでのマスの合計値を計算する方法だと、1つのマスを計算するのにの計算量がかかってしまう。ここで、直前のマス(図の青の区間)とそれより前のマス(図の赤の区間)の合計が通り数となっていることがわかるので、この二つの情報を一つのマスにまとめて記憶させれば計算量はとなり高速になる。
これを、上方向・右上方向・右方向の3つについて考えれば、それぞれの解の合計値がそのマスへの移動方法の通り数となる。
あとはこの図を動的計画法に落とせば解ける。注意点として、壁のマスの場合、そのマスには遷移できないのですべての数値をにする。
計算量は、。
F - Confluence
ACコードを提出できなかった。以下に考察を残しておく。
集合を結合するクエリが存在する(しかも一度結合した集合がわかれることはない)ので、UnionFindを使って解けそうだと考える。ただし、もう一つのクエリである「生徒が含まれる集合に含まれる生徒のうち、クラスに属する生徒の数を求める」のがやっかい。これを実現するために、各集合の親ノードに「どのクラスの生徒が何人いるか?」という情報を持たせるための辞書(map)を追加する。
しかし、これだと集合を結合するときに辞書データも結合しなければならず、毎回の計算量がかかるので、その集合に1人以上含まれるようなクラスだけ保持する集合(set)も親ノードに持たせることにして、結合時はその集合に含まれるクラスの情報だけを反映するようにした。こうすることで、いわゆるデータ構造をマージする一般的なテクと呼ばれるテクで、小さい方を大きい方にくっつけるようにすればならし計算量で結合できる…はず。
こうすれば計算量はで(この計算量解析も怪しい)、問題が解けるはずだと考えたが、sample以外のテストケースでかなりWAが出ているので嘘解法のような気がする…。
(追記)考察はあっていた。「生徒が含まれる集合に含まれる生徒のうち、クラスに属する生徒の数を求める」クエリに答えるには、
- 生徒が含まれる集合の根を取得する。
- その根が持っている辞書データの中のクラスの値を取得する。
という段階に分けられる。ここで、集合の根を取得するとき、UF内のメンバ関数root(x)
を使うべきところを、同じくメンバ関数であるpar(x)
と書いてしまっていた!root(x)
はが含まれる集合の根(頂点)を返す関数であり、par(x)
はの(一つ上の)親を返す関数である。あるノードの親が何になるかは実装により変わるので、基本的に外部からpar(x)
を参照する必要はない。つまり、ただの実装ミスだった…。
(追追記)全然ちがーーーう!!!!!!
集合の根を取得するのはroot(x)
という関数。par[x]
は、今現在のの親を保存しているだけの配列。これを一緒くたにしてはいけない!!さらにいうと、root(x)
が呼ばれたとき、par[x]
の値が根の値に更新されるだけで、本当に親かどうかも外から見ただけではわからない。つまり、本当にpar[x]
は外部から参照してはいけない!!!!!!!
parを外から弄るとバグの原因になるのでprivateにすると、よい!(無用なバグを防げるので(ぼくはprivateにしてないけど))
— 神崎 (@knzk_ate) November 15, 2020
嫁、ありがとう
感想
なんか全体的に簡単め?だった気がする。上位陣の全完スピードが異常だった。