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 は完全に独立して考えることができる。よって、それぞれ独立に最大化すればよい。これは貪欲にできる。