86:01 + 1ペナ 6完でちょっと失敗でした、かなしい
パフォは1725くらいです、青なのでまあ耐えだけど
A ASCII code
AっぽいAですね
cout << (char)N << endl;
でOK
aとの差を計算してa + iみたいにしてもいいですね
(AC 0:49)
B Takahashi's Failure
制約もやさしいし、いつものBですね
まずおいしさの最大値がいくつか？をO(N)で計算して
そのあとに、それと等しくなるindexがあるかをO(K)で計算しました
制約的には、最大値の前計算をしないものも許していますね
(AC 3:25)
C Slot Strategy
これいつものCより簡単と思ったんですが、そんなことないのか...
まず、どの値でそろえるかを決め打ちます
そしたら最適解を求めることができます
同じタイミングで止めたい(=indexが同じ)ものについては、10秒ごとに止めるしかないので、たとえばindexが0のものから3個止めたいとすれば、30秒かかってしまいます
こうして、それぞれのindexについて必要な秒数を求めておいてmaxをとればよいです
全体では値を決め打って求まった最適解のうちのminをとります
無理やりフローに落とすこともできそう？
(AC 8:23)
D Distinct Trio
解説が天才だった...何回かこの議論見たことあるんですけどね
3つあるときは真ん中固定で解けることが多いので、jを固定します
すると条件は以下のように整理されます
・Ai ≠ Aj かつ Ak ≠ Aj (jに関係するもの)
・Ai ≠ Ak (jに関係しないもの)
これらについて一つずつ考えていきましょう
・Ai ≠ Aj かつ Ak ≠ Aj
これは、(自分より左にあるAjでないものの個数) x (自分より右にあるAjでないものの個数)で計算できます
あらかじめ、それぞれの数字の出現回数を数えておき、さらに今見ているindexより左にあるそれぞれの数字の数を数えておけばよいです
・Ai ≠ Ak
上で数え上げたものには、Ai = Akとなるものも混じっているのでこれを取り除きましょう
これは Σa=1~maxAi (左にあるaの個数 x 右にあるaの個数)を求めればよいですが、愚直に計算すると各回にO(N)だけかかってしまいます
ただし、1つ隣にうつったときに変化する部分は高々2つ(i -> i+1に移ったなら、Ai, Ai+1だけ更新すればよい)なので、変化する部分だけ更新しましょう
すると1回あたりO(1)にできるので、全体でO(N)となり間に合います
(AC 18:25)
E Road Reduction
うーん、ちょっと手間取ってしまった
ぱっとみ、最小全域木っぽいですが
3 3
1 2 2
2 3 2
1 3 3
が反例になります
この場合だと、1->2, 1->3と残すのが最善となります
もう少し最善になるパターンを考えてみると、
dist[i]を最小化するには、そもそもそのひとつ前のdist[parent]が小さい方がよいです
そう考えると、それぞれに対して最短にするのがよさそうなので...
Dijkstraをすればいいんですが、自力でDijkstraを再発明していました(？？？)
まずpriority_queueに頂点1からたどりつけるものに対するコストをいれます
その中から最も小さいのをとりだして、そこからいける頂点(かつまだ到達していない)に対してまたコストを入れることを繰り返します
そうすると、Dijkstraができます(？？？)ので解けました
コスト計算を間違えて1ペナ...
本番中は気づいてなかったんですが完全にDijkstraでした
(AC 44:21)
F Bread
なんか瞬殺できそうな見た目してる～～.........解けね～～～となってました
そもそも余るものがある場合は、L - sumを作るとしてよさそうです
まず思いつくのはそれぞれの寄与を計算して少なくしたいということです
で、特に偏りがなければ切る回数の合計を最小化するのがいいかな～と思うので、2べきで切っていくことにします
...んー－まあいい感じ！と思うんですがサンプル2で無事落ちます
言われてみればめっちゃでかいのあるときに困ります
次に考えると、小さい順にソートして、i番目まで使う時の最小コストはどうか？というDPが思いつきます
ただ遷移ができそうでできないのと、「セグ木でDPにしたら解かれすぎでしょ」っていうのと、最善か怪しすぎるっていうのを組み合わせると外れ方針っぽそうです
で、もうちょっと考えるとスライム分割するようなやつだと、マージしてごちゃごちゃするといいときあるよね～っていうのが思いつくので、マージを考えます
すると、いかにもマージした時に小さい2つをとるのが最善っぽくてサンプルも合うので祈って出すと通ります
蟻本既出なのか...知らなかった
(AC 86:01)
G 考える時間がなく...
総括
Eいわれてみればそうなんだけど、ちょっと考えちゃったな
Fもっと速く通せるべきだった
