7完60:17 + 2ペナ 105位
FGをサクッと片付けたのがえらい、Eでハマったのはダメ...
A Double Click
forやるだけ、言われてみればダブルクリックの時間を快適にするの絶妙な調整だよね
(AC 1:50)
C chess960
元ネタを知らなかったので、1行でチェスするの何が面白いんだと思った
解くのは条件を丁寧に実装するだけ
2重ループ+3重ループで解きました
(AC 5:20)
C PC on the Table
PCTやりたいだけ
左から貪欲に詰めていけば問題ないので、一つ一つ変えていきましょう
(AC 7:33)
D Count Subtractions
直前のARC-Bっぽさを感じさせるけど、解法はちょっと違う
大小関係が入れ替わるまでは操作をまとめて繰り返してあげればよいです
やっていることはユークリッドの互除法とだいたい同じなはず(?)で、高速に終わります
(AC 11:35)
E Kth Takoyaki Set
Twitterで最近流れていた Ai + AjのうちK番目みたいな問題に思いをはせながら解いた
できる可能性がある候補としては現在の値をXとして、X+Ai(1≦i≦N)になるので、これをいい感じに調べていきます
具体的には、あまり大きいと調べる必要がないのでpriority_queueにつっこみながら小さい順に調べていくことにします
今までに出現した値をset, priority_queueで管理しておきます
もし今まで出現した値がK個を超えたら、K番目以上のものは調べる必要はありません
K番目の値以上になるものを加えないようにすると、計算量が抑えられて間に合います
(AC 24:36)
F Minumum Bounding Box 2
期待値を直接計算するのは難しそうなので、総和を求めることにします
解説と方針は違いますが、縦h、横wを固定して「最小長方形が縦h,横wになる通り数」を数え上げることにします
すごくざっくり考えるとh×wマスからK個のマスを選ぶので、二項係数を用いてhwCKになりそうですが、たとえば上一行にひとつもない場合など当てはまらないこともあります
ダメな条件を考えると
・上一行にない
・下一行にない
・左一列にない
・右一列にない
のうちどれか一つでもあるとダメであることが分かります
こうやって整理すると「A,B,C,Dのうち一つでも満たす通り数」を計算する問題になっているので、これは包除原理で解くことができます
bit演算を用いて縦・横の縮め方を管理すれば比較的楽に書けます
実装例
Submission #40507604 - AtCoder Beginner Contest 297
(AC 46:49)
G Constrained Nim 2
各ゲームが独立しているので、それぞれのGrundy数を求めてXORをとるのがよさそうだな～と思います
Grundy数を求めたいので、とりあえず手元で実験してみます
L=3, R=5とすると、Grundy数が0,0,0,1,1,1,2,2,0,0,0,1,1,1,2,2...となって
実験したときの遷移する先も考えると、0がL個、1がL個、2がL個 ...という風になっていくはずで、長さは(L+R)個でループしていることが分かります
変な例外があったら悲しいんですが、とりあえずあってそうなのでGrundy数をAi%(L+R)/Lとして実装します
サンプルが弱くて心配になりますが、投げるとAC
(AC 60:17)
総括
F黄色かと思ったらギリ青色だった
