3匹の猫

みみねこの競プロ精進メモ

AtCoder Beginner Contest 183の解法・感想

ABCに出るのは久々でした。

100-200-300-400-500-0(2)で0ペナ5完1500点。

A - ReLU

問題文の通りの値を返す関数を実装する。入力された値によって出力される値が異なるので、条件分岐を用いて書けばよい。

計算量は、O(1)

B - Billiards

入試数学とかでよく見る考えで、「ある面で跳ね返る」というのは、「その面と対称な空間を考えたとき、面を跨いでその空間へ直線移動する」ことと同じである。

今回は始点と終点が決まっていて、反射するのは1回と決まっている。よって、例えば終点をx軸を対称軸として反転させた位置に設定すれば、「始点と移動後の終点を結んだ直線」と「x軸」との交点を求める問題になる。

2直線の式が出ているので、方程式を解けば交点が求まる。「x軸」と交わるというのはy=0であることと等価なので、始点と終点を結んだ直線の式にy=0を代入してxを求めればよい。

計算量は、O(1)

C - Travel

制約より、どの2都市を選んでも移動可能である。都市1からすべての都市を通って戻ってくるようなルートの数は、都市2から都市Nまでの巡り方の数に等しく、(N-1)!通りである。制約の最大値がN=8であり、すべてのルートに対して移動時間を計算しても間に合いそうなので全探索する方針で実装する。

このように、その通り数が階乗で表されるような全探索を界隈では順列全探索と呼んだりする。実装の詳細は省く。長さがN-1の順列を生成した後その各項の数を都市の番号と紐づけ、実際にかかる移動時間を計算する。

計算量は、O((N-1)!\times N)=O(N!)となり、実行時間制限に十分間に合う。

D - Water Heater

ある区間[S, T)が決まっていて、その区間内すべての要素にP足す…という処理をN回した数列が欲しい。ただ、愚直に実装すると計算量がO(NT)となり間に合わないので、imos法を使って解く。アルゴリズムの詳細と実装方法の説明は省く。

imos法を用いることで、計算量をO(N+T)に削減することができた。あとは、生成した数列の全ての項がWを超えていないか愚直に判定すればよい。この処理自体はO(T)で出来る。

全体の計算量は、O(N+T)

E - Queen on Grid

動的計画法で解けそうだが、遷移方法が複雑になりそうなので細かく分けて考える。

まず、横一列にマスがつながっている場合に、各マスに移動する方法がそれぞれ何通りになるのか考えてみる。最初のマスにはすでに駒が置かれているので1通りとして考えると、それぞれのマスに対する移動方法の通り数は以下の通りとなる。「あるマスより手前にあるマス」からならどのマスからでも移動可能なので、通り数はそのマスより前のマスの通り数の合計となる。

f:id:mmnkblog:20201116000600p:plain
通り数を求めるには、赤の区間と青いマスの数値が必要

しかし、いちいちそれまでのマスの合計値を計算する方法だと、1つのマスを計算するのにO(W)の計算量がかかってしまう。ここで、直前のマス(図の青の区間)とそれより前のマス(図の赤の区間)の合計が通り数となっていることがわかるので、この二つの情報を一つのマスにまとめて記憶させれば計算量はO(1)となり高速になる。

これを、上方向・右上方向・右方向の3つについて考えれば、それぞれの解の合計値がそのマスへの移動方法の通り数となる。

f:id:mmnkblog:20201116000605p:plain

f:id:mmnkblog:20201116000612p:plain
H=3, W=5の場合の例(緑のマスが各マスの通り数)

あとはこの図を動的計画法に落とせば解ける。注意点として、壁のマスの場合、そのマスには遷移できないのですべての数値を0にする。

計算量は、O(HW)

F - Confluence

ACコードを提出できなかった。以下に考察を残しておく。

集合を結合するクエリが存在する(しかも一度結合した集合がわかれることはない)ので、UnionFindを使って解けそうだと考える。ただし、もう一つのクエリである「生徒xが含まれる集合に含まれる生徒のうち、クラスyに属する生徒の数を求める」のがやっかい。これを実現するために、各集合の親ノードに「どのクラスの生徒が何人いるか?」という情報を持たせるための辞書(map)を追加する。

しかし、これだと集合を結合するときに辞書データも結合しなければならず、毎回O(N)の計算量がかかるので、その集合に1人以上含まれるようなクラスだけ保持する集合(set)も親ノードに持たせることにして、結合時はその集合に含まれるクラスの情報だけを反映するようにした。こうすることで、いわゆるデータ構造をマージする一般的なテクと呼ばれるテクで、小さい方を大きい方にくっつけるようにすればならし計算量O(\log N)で結合できる…はず。

こうすれば計算量はO(N + Q\log N)で(この計算量解析も怪しい)、問題が解けるはずだと考えたが、sample以外のテストケースでかなりWAが出ているので嘘解法のような気がする…


(追記)考察はあっていた。「生徒xが含まれる集合に含まれる生徒のうち、クラスyに属する生徒の数を求める」クエリに答えるには、

  1. 生徒xが含まれる集合の根を取得する。O(\alpha (N))
  2. その根が持っている辞書データの中のクラスyの値を取得する。O(\log N)

という段階に分けられる。ここで、集合の根を取得するとき、UF内のメンバ関数root(x)を使うべきところを、同じくメンバ関数であるpar(x)と書いてしまっていた!root(x)xが含まれる集合の根(頂点)を返す関数であり、par(x)xの(一つ上の)親を返す関数である。あるノードの親が何になるかは実装により変わるので、基本的に外部からpar(x)を参照する必要はない。つまり、ただの実装ミスだった…。

(追追記)全然ちがーーーう!!!!!!
集合の根を取得するのはroot(x)という関数。par[x]は、今現在のxの親を保存しているだけの配列。これを一緒くたにしてはいけない!!さらにいうと、root(x)が呼ばれたとき、par[x]の値が根の値に更新されるだけで、本当に親かどうかも外から見ただけではわからない。つまり、本当にpar[x]は外部から参照してはいけない!!!!!!!



嫁、ありがとう

感想

なんか全体的に簡単め?だった気がする。上位陣の全完スピードが異常だった。