昨夜は大学の送別会で朝までカラオケしていた。頭が痛い。
ABC296のバチャをした。
A: N-1か所ある隣接部を確認する
B: やるだけ
C: やるだけ
D: 時間内に解けなかった。a,bについてa≦bという制約を考えるとa≦√M≦10^6なので、これを全探索すればよい。対応するbはにぶたんで求める。
順序を入れることで計算量を減らせるやつ、久しぶりに見たのでパッと出なかった。
E: 時間内に解けず。自明になもりグラフになる。ループ部に含まれる箇所ならば、どんなSiが来ようと適切にKiを指定すればよい。逆にループ部に含まれない箇所ならば、Siを十分大きくとることによってどうやっても高橋君は勝てなくなる。
頭が回っていなくてSi=iというように誤読した。そうはならんやろ。
F: 時間内に見れず。バチャ後に自力で解けた。結構好きなタイプの問題。
まずAとBがソートとして一致しなければどうやっても一致させられないので除外。以後はソートして一致することを前提とする。
N>3のとき、Aj=Akとなるようなj,kを指定すれば必ず1か所そろってサイズの1小さい問題に帰着できる。そして最終的にはN=3の問題を解けるかの問題になる。これが解ける条件を調べるため、試しに手を動かして実験してみる。
A: (1,2,3), b:(2,3,1)
仮にこのような状態になった場合、i=2,j=1,k=3とすることで解ける。
A: (1,2,3), B:(1,3,2)
このような状態になった場合、これはどんな操作をしてもどうにもならない。パリティ関係の問題のにおいが漂ってくる。
A: (1,1,2), B:(1,2,1)
このような状態になった場合、i=1,j=3,k=2とすることで一致させられる。同じ値が2か所あれば無条件に解ける。N>3の問題についても、同じ値が2か所あった場合、適切に操作の手順を選択することで同じ値の2か所を最後に残すことができ、無条件に一致させることができる。以後は値のかぶりがないことを前提とする。
値のかぶりがないということはつまり順列ということである。ご丁寧に$1\leq A_i \leq N$となっているので座圧の必要もない。
順列が2つでは解析しづらいので、順列1つの問題に言い換えてみる。
$i,j,k$を指定して操作をしたとき、$(A_i,A_j,A_k)=(s,t,u), (B_i,B_j,B_k)=(p,q,r)$→$(A_i,A_j,A_k)=(t,s,u), (B_i,B_j,B_k)=(r,q,p)$となる。並べなおすと$(A_k,A_j,A_i)=(u,s,t), (B_k,B_j,B_i)=(p,q,r)$となる。
初期状態の順列Bの置換の逆置換を$\sigma$とし、新しい順列$P$を$P_i=A_{\sigma(i)}$と定義すると、i,j,kを指定したときの操作は$P_{\sigma(i)},P_{\sigma(j)},P_{\sigma(k)}$の値を$P_{\sigma(k)},P_{\sigma(i)},P_{\sigma(j)}$とすることに対応する。これは偶置換だ。
ということでこの順列Pを算出して転倒数の偶奇を調べてやればよい。偶置換なら一致可能で奇置換なら一致不可能。
G: 時間内に見れず。しばらく考えたら思ったより簡単だった。実装はやや面倒だが。
多角形は凸多角形であると保証されているので、x=(定数)の直線を凸多角形に重ねると、端以外では常に2点で交わる。x=(定数)の直線はこの2点によって3つの領域に分割される。OUT,IN,OUTに対応する。
ということで、凸多角形の上側の線と下側の線に対してクエリで与えられた点が上側になるか下側になるか判定すればよい。上側と下側それぞれにおいて、二分探索やstd::setなどでx=Aiの直線が多角形のどの線分と交差するかを調べることができる。これによって2本の線分に対して上か下か判定すればよくなるので$O(Q\log N)$になる。
筋トレをした。今日は腕立て。
Categories: 未分類