6完91:23 3ペナでパフォ1816でした。ちょっと失敗ですね...
A問題
Aでforが求められるの新時代って感じがしますね。
二重ループでiにあたるindexが存在するかを判定しました(AC 2:07)
B問題
while文書くだけ、ですがintでもつとN*Kがオーバーフローするので、long longで持ちます。(AC 3:39)
C問題
制約が大きいと高度な内容が必要な典型問題なんですが、小さいのでDPができます。
DPの定義は
dp[i][j] = i番目の要素までみて、その総和がjとなる通り数
とします。
遷移先を毎回計算して配るDPで解きました。(AC 7:45)
D問題
Wavelet Matrixで殴れるんだろうなと思いますが、ぼくは知らないので普通に解きます。Aiに対応するindexを持っておけば、二分探索を使うことで範囲がわかるので、該当するindexを引き算して答えを出します。番兵(最後にINFを置くなど)は入れてもいいんですが、いりませんでしたね。(AC 11:39)
E問題
ここですよ...めちゃくちゃ迷走してしまった...。
まずN≦300なので、O(N^3)が許されます。とりあえず2点を決め打って直線を決めて、それがK個以上の点を通るか？という判定をすればよさそうという方針が立ちます。
これで問題になるのは
・直線上にあるか？という判定がO(1)ないしはO(logN)でできるか
・直線が重複しているか判定できるか
の2点です。
まず、「直線上にあるか？という判定がO(1)ないしはO(logN)でできるか」なんですが、直線の傾きと切片が求まると、y=ax+bを満たすか？で判定できます。
次に、「直線が重複しているか判定できるか」なんですが、こちらもy=ax+bを計算できれば、aとbをpairで持ってsetに入れればできそうです。
解けましたね！！ ... WA
困ってしまいました。方針としてはあっていそうなんですが、ax+bのところを分数で持っていて嫌なコーナーケースがたくさんありそうです。順位表をみると思ったよりペナルティが少ないのでコーナーの少ない解法がありそうです。今の方針をちょっと粘ったんですが、ダメそうだったのでもう一回方針を見直すことにします。
まず、「直線上にあるか？という判定がO(1)ないしはO(logN)でできるか」なんですが、Google先生に聞くと積の形で整数のみで判定できるそうなのでこれを採用します。
次に、「直線が重複しているか判定できるか」なんですが、よくよく考えるとi, j (i < j)を選んで直線としたときに、k(k < i < j)がその直線を通るのであれば、k, iを選んだ時にすでにカウントしているので数えなくていいことになって簡単に判定できます(これ思いついたとき天才かと思ったけどめっちゃ通されてた)。
これで誤差や分数のコーナーケースを考えることなく解けました(AC 62:54)
こういう重複判定の仕方勉強になりました。
F問題
制約・設定からさすがにDPです。
dp[i][j] = i番目まで考えて、切った辺がj本あるものの通り数
と置くのがベースになりそうです。
ただ、上下がつながっているかどうか？がわからないと、辺を切ってよいかがわからないので、これを情報として持つ必要があります。
本番では、そもそもi番目の上下がつながっているか？を持っていたんですが、よく考えると不要でした...
dp[i][j][k][l] = i番目まで考えて、切った辺がj本あり、k番目の上下がつながっているか(0/1)、上下がすでに連結しているか(0/1)の通り数
と定義して解きました。
頑張って遷移を整理して、DPの式を立てると通ります (AC 91:23)
なんか思ったよりTLがギリギリ(1500msくらい)だったのですが、k = 9000までやっていたのが原因でした。C++ならこういうミスしててもなんとか通るね、いえい。
G問題
Ai ≦ 10^5なので、gcdが大きい方から計算していって被るところを省く方針で解けそうだなと思ったんですが、Fまでが遅くて手を出せませんでした...
総括
E以外は悪くなかったんですが、Eでやらかしましたね。
分数みたいなコーナーが多い方針はもう一回考えてマシなのがないか探すようにしたいです。
