GCJ 2017 Qual

A 問題

+- の列があって、連続する K マスを反転するのを繰り返して全部 + にする問題。まったく同じ問題が蟻本にある。

B 問題

10 進表記で数字が昇順になるような N 以下の最大の整数を求める問題。なるべく上位桁は動かさない方がいいということ、ある桁の数字を 1 減らしたらそれに続く数字はすべて 9 にすればいいことを踏まえれば解くことができる。

C 問題

区間の長さだけ保持しておけばよくて、大きい区間から順に分割していくのを繰り返せば良い。 分割過程では値が重複しやすいため、同じ長さの区間をまとめて処理すれば速くなりそうである。

分割の様子を図にすると以下の通り。

木の高さは O(log n) である。また、各レベルにおける値の種類数はたかだか 2 である（これは最大値と最小値の差がたかだか 1 であることから分かる）。ゆえにまとめて処理すれば O(log n) 回で収まる。

D 問題

条件を整理すると

  • どの列/行も、x を 2 つ以上含まない
  • どの列/行も、x と o の両方を同時に含まない
  • どの列/行も、o を 2 つ以上含まない
  • どの対角線も、+ を 2 つ以上含まない
  • どの対角線も、+ と o の両方を同時に含まない
  • どの対角線も、o を 2 つ以上含まない

となる。あるマスに o が書かれているというのは、あるマスに + と x の両方が書かれていると言い換えられる。この言い換えにより条件はよりシンプルになる。

  • どの列/行も、x を 2 つ以上含まない
  • どの対角線も、+ を 2 つ以上含まない

+/x を o に変える操作は許されているので、+/x は完全に独立して考えることができる。よって、それぞれ独立に最大化すればよい。これは貪欲にできる。


AtCoder Grand Contest 012 C: Tautonym Puzzle

http://agc012.contest.atcoder.jp/tasks/agc012_c

解法

空の列も良い文字列だとみなす。

順列 A, B があって、AとBを連結したもの(A+Bと表す)のパターン数が X だったとする。

  • A←A+[foo], B←B+[foo] とすると A+B のパターン数は 2X になる。
  • A←A+[foo], B←[foo]+B とすると A+B のパターン数は X+1 になる。

これを利用することで 4log(N) 個の要素で構築できる。


AtCoder Grand Contest 012 B: Splatter Painting

http://agc012.contest.atcoder.jp/tasks/agc012_b

解法

di が小さいのが鍵に見える。

dp[v][i] を「頂点 v から距離 i の範囲を dp[v][i] で塗りつぶせ」と考えると上手くいく。命令を小さい距離へどんどん伝搬していくイメージ。

補足

ある頂点から距離 d の範囲を塗りつぶすという命令は、距離 d-1 の塗りつぶし命令に分解できる。



距離 2 の命令を距離1の命令に分解するイメージ

頂点 v から距離 d の塗りつぶし命令が複数あるならば、最も新しい命令以外は無視しても良い。無視することにより計算量は O(d(n+m)) になる。


AtCoder Grand Contest 012 A: AtCoder Group Contest

http://agc012.contest.atcoder.jp/tasks/agc012_a

解法

入力を昇順にソートして考える。

適当な戦略を取ってみる。先頭から3つずつペアにしていくのはどうだろう。

_o__o__o__o_
000111222333

oになっているのが中央値。

これは改善ができる。

_o__o___o_o_
000111232233

改善の雰囲気から最適構造が見える。

____o_o_o_o_
012300112233