Google Code Jam 2017 Qualification Round
Dashboard - Qualification Round 2017 - Google Code Jam
無事通過。でも全部解きたかったなあ。
A: 1次元ライツアウト。
右から貪欲にそろえていけばよい。O(length S)
B: 左から数字が増加していくようなもの(1111222255566とか)をTidiy Numberと呼ぶ。N以下で最大のTidy Numberを求めよ。
最初N以下のTidy Numberの総数を求めよかと思い、桁DPを組むとかやってしまった。左の桁からみていって減少する桁を探す。減少する桁が見つかった場合は、直前にある真に増加する桁の数字を1個減らし、更に1を引いたものが答え。
C: 両脇が常に使用中のN+2個ロッカーの列がある(つまり最初の空きはN個)。人が来るたびに両脇の空きロッカーの数が一番多くなるようにロッカーを専有していく。この時、K人目がロッカーを専有したときに両脇の空きはいくつになるか。
いわゆる人からなるべく離れて座りたいという電車の椅子問題(？)。
1人→2人→4人→8人・・・という感じで人を分割して、その時のロッカーの空きを観察すると、ロッカーの空きの連続列は各段階で実はある数xが存在して、xとx+1という2通りしかないことがわかる。このxをシミュレーションで求めていく。
1+2+4+…がKを超えたところでその時のシミュレーション結果が答え。+1とか+2とかがややこしい。
D: Nクイーン問題の発展版。コマx, +, oが合って、縦横にある任意の2個のコマの片方が+、または斜めにある任意の2個のコマの片方がxでなければならない配置に制限するときに、x1点、+1点、o2点でスコアを決める。このスコアの最大値を求めよ。
本番解けなかった。実はこの問題、xと+で独立して考察することが可能。そうして求めた配置のうち、+とxが同じ場所に合った場合にoに変えれば良い。
xの方は単純に貪欲にN個おけばそれが最大配置。+の方はちょっと複雑だがN個おける。2部グラフのマッチングを使うか、複雑な貪欲でもいけるらしい。Editorialは貪欲の説明をしていた。ただ市松模様にした時に、色違いのところは独立に考えられるなどそうやって計算量を減らすことでできそうではある。
