0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

8/11 AtCoder Regular Contest 080

この前うっかり寝過ごしてで損ねたARC080を解いた.

  • C: 4-adjacent - AtCoder Regular Contest 080 | AtCoder [解答]

    数列の要素を自由に並び替えて隣り合う要素の積が4の倍数になるようにできるか判定する問題. Aiが奇数, (4の倍数でない)偶数, 4の倍数で隣に置かなければならない数の条件が変わることに注目する. Aiが奇数なら, 隣には必ず4の倍数をおく必要がある. Aiが偶数なら, 隣には偶数をおく必要がある. Aiが4の倍数なら, 隣におく数はなんでも良い. ここから考えると, { 奇数, 4の倍数, 奇数, 4の倍数, ..., 4の倍数, 偶数, 偶数, ... }みたいな並びが作れるかを判定すれば良いことになる.
  • D: Grid Coloring - AtCoder Regular Contest 080 | AtCoder [解答]
    1, 1, 1, 2, 2, 3, 3, 3, 3, ...., N, N, Nと左上から順に要素数H * Wのマス目を埋めていき, 奇数番目の行だけreverseして表示すればOK.

  • E: Young Maids - AtCoder Regular Contest 080 | AtCoder [解答]
    辞書順で最小のものを構成するのは後ろから考えるとやりづらいので, 先頭から小さい数字を順に決めていくことを考える. 最初の状態からqの先頭2つの要素を決めるのには, 偶数番目の要素でもっとも小さい値とその要素以降で奇数番目の要素を取るのが最良. この二つの要素がpのi, j番目だとすると, pは[0, i), [i + 1, j), [j + 1, N)の3つの要素に分断される. qの次の2要素はこの3つの領域の偶数番目の値から最小のものを選ぶことになる. これを繰り返していけばO(N^2)でqを求めることができる.
    ここから計算量を落とすためには, 偶数番目/奇数番目の要素から最小を求めるのにセグメントツリー, 分割された領域からどれを選ぶかはpriority_queueを用いればよい. 具体的な手順としては,
    1. { [0, N), min_odd }をpriority_queueに入れる
    2. priority_queueから最小のものを取り出す
    3. 3つの領域に分割して, それぞれをpriority_queueに入れる
    4. priority_queueが空ならループ終了, そうでないなら2に戻る
    という感じ. 結構実装がしんどかった...