きろく

特筆すべき記録のまとめ

JOI '09 本選:4- 散歩

問題

https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf

解法

1 ~ (N - 1) 回目にたどり着いた場所を知る必要はない.また,詳しいルートを1回ずつ区別して計算する必要はない.なぜならば,N 回目のルートやたどり着く場所に影響を与えないからであり,各交差点を 1 ~ (N - 1) 回目のルートで何回通ったかが重要になる.

まず,交差点 (1, 1) を当然 (N - 1) 回通る.この後,(1, 1) が「東」ならば (1, 2) を [(N - 1) / 2] ((N - 1) が奇数の時は +1) 回,「南」ならば [(N - 1) / 2] 回通る.同様に (2, 1) を [(N - 1) / 2] 回,「南」ならば [(N - 1) / 2] ((N - 1) が奇数の時は +1) 回通る.整理すると,

(x, y) を T 回通るとき,

  • (x, y) が「東」ならば,(x, y + 1) を [T / 2] (T が奇数の時は +1) 回,(x + 1, y) を [T / 2] 回通る.
  • (x, y) が「南」ならば,(x, y + 1) を [T / 2] 回,(x + 1, y) を [T / 2] (T が奇数の時は +1) 回通る.

となる.これを全ての交差点について計算し,N 回目の時に各交差点が「東」か「西」のどちらを示しているのかを知ることが出来る.あとはこの状態でシミュレーションして答えを求めればよい.O(HW).N は時間計算量に関係ない.

解答

atcoder.jp

f:id:babcs2035:20190313223045p:plain

 

JOI '09 本選:5- 認証レベル

問題

https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf

解法

各事務所についてどれぐらいの数の部屋をどれぐらいの認証レベルで入ることが出来るのかが知りたい.ここで,各事務所のマス上で BFS をする.具体的には,(今の認証レベル,今の座標) という状態をキューに持って置き,今の認証レベルの小さい状態から隣接する4方向に移動する.このとき,今の認証レベルが今の座標の部屋のレベルよりも小さい場合は,今の認証レベルを部屋のレベルまで引き上げる.この BFS によって各事務所について,ある入る部屋数に必要な認証レベルの最小値が求まったので,片方の事務所で入る部屋数を決めたときもう片方で入る最小の部屋数も定まり,必要な認証レベルの和も求まる.あとはこの和の最小値を答えにすればよい.O(HWlogHW).

解答

atcoder.jp

BFS で実装すべきところを DFS で実装していたため,原因不明の無限ループが発生してしまっていた.

f:id:babcs2035:20190312134017p:plain

 

JOI '09 春合宿1:1- Sequence 数列

問題

https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day1_20.pdf

解法

数列 A を書き出して実験してみると,1 ~ (m * 2^m) 項目の偶奇が周期的に繰り返していることが分かる.1つの周期の中にいくつ奇数の項があるかを数え,(1 ~ q に含まれる奇数の項) - (1 ~ (p - 1) に含まれる奇数の項) で答えがもとまる.1つの周期の中の偶奇をもとめる中で数列を m 個ずつに分けた群数列を考え,各群の中の偶奇を bit が立っているかどうかだとみなすことで各群を1つの数字で表すことが可能になり,空間計算量を削減できる.O(2^m * m).

解答

atcoder.jp

bit 関連の操作でバグらせていた.

f:id:babcs2035:20190311222129p:plain