G解けたと思ったんだけどな
44:57 6完 + 1ペナ 173位
A Anyway Takahashi
なんだこの問題名！？とはなるけど、さすがにやるだけ
入出力の練習ですね
(AC 1:22)
B Rectangle Detection
左上のマスと右下のマスがわかればよいです
マス目を全探索して、x,yのmin,maxを抽出すればよいです
ふつーのB
(AC 4:48)
C Submask
制約が大事で、K≦15みたいなのですね
Cに出ているということもあって、定番のbit全探索です
全探索する桁をあらかじめ取り出しておけば、あとはすんなり
細かいテクとしては(1<<i)でi番目のbitだけ立てた数がわかります
例： (1<<2) = 100(2)なので、4
わざわざぼくの記事読む人はみんな知ってそうだけど
(AC 8:12)
D Do use hexagon grid
うっわ、六角座標だ...と思うけど内容はめちゃめちゃシンプル
連結成分の判定なので、UnionFindなどが使えます
移動方向もご丁寧に問題文に書いてあるので、気を付けて書き写せばOK!
全ペアを走査するとO(N^2)になるけど、setで存在しているマスを管理しておくと、O(NlogN)になりますね
N ≦100000でもよかった気もする
(AC 12:33)
E Last Rook
インタラクティブだ！となるけど、その中ではかなり簡単なほう
Twitterでも言われてたんですが、「インタラクティブ、とりあえずにぶたん考えると解ける説」あると思います、少なくとも探索回数を減らす簡単な手段なので考える価値はありそうです
ちょっと丁寧目に考察します
「1つの行に2個以上のルークがない」「1つの列に2個以上のルークがない」という条件から、i行目~j行目にあるルークの数は j - i + 1個以下になります(列も同様)
今欠けているのが一か所なので、i行目~j行目にあるルークの数が j - i 個、つまり全部埋まった時より1個少なければ、そこが欠けた箇所であるとわかります
そこで1行目~X行目にX個あるか？を聞くことにします
もし、X個あればそこには欠けている箇所がありません
逆にX-1個ならば欠けている箇所があるとわかります
このXを二分探索で求めればよいです(列も同様)
(AC 22:53)
F Numbered Checker
最初二次元累積和かな？と思いますが、制約が厳しい(N,Mが大きい)ので素直に持つことはできなそうです
0になるところが規則的なので、どんな風になるか考えると
0?0?0
?0?0?
0?0?0
みたいな形になります、図あるけどね
いい感じにまとめられそうなところをまとめて計算したいので、どこをまとめようかな～と思うんですが、もし1行目がわかれば、3行目はその数にすべて2*Mをたしたかたちになっています
ここに注目すると、偶奇で分ければいいかな？と思います
偶奇で分けた場合は、1行目、2行目の値さえ計算できればよいです
1行目について、どうするか考えてみます
まず一番左上のマスの値をXとします、すると1行目の次の値は、X+2、その次はX+4...となっています
つまり、初項X、等差2の等差数列の和が計算できればよいです
1行目の和がSだったとしましょう、3行目の和はどうなるでしょうか？
3行目の数字は1行目の数字にすべて2*Mを足したものになっています
つまり、S + (2*M)*W (W = 等差数列の項数)が3行目の和になります
3行目、5行目...と計算するにあたって、足される数は(2*M)*Wで固定されているので、こちらも等差数列の和で計算できます
偶数の場合も同様に処理することで解けます
実装の工夫？ですが、端っこが0だとめんどくさいので、もし0ならx1,y1に+1, x2,y2に-1するなどして調節してから考えると楽になると思います
説明しづらいので実装例を置いておきます(等差数列の計算の仕方が若干違う)
(AC 44:57)
G Reversible Card 2
和がM以下というあまりに変な制約があるので、そこを見ます
これは典型知識なのですが、和がM以下ならば、種類数は多くとも√M程度になります
なので、比較的愚直な以下のようなDPを考えてもO(M√M)程度になりそうです
dp[i][j] := i番目の種類の値まで考慮した時、和をjにするための最小値
あとはこの更新が高速にできればよいのですが、
dp[i+1][j] = min(dp[i+1][j], dp[i][j - k*x] + x) [k = i番目の値, x = 使う個数]
という形になり、ちょっと厄介そうです
kのあまりごとに考えることでいくつかのminを計算すればいいことになります
ここでsetを使ってしまったのですが、TLEで落とされました
うーん、まあそうだとは思ったんだけどね...SWAGやるか
総括
Gの壁厚い
