6完81:23 0ペナでパフォ2395でした。
Eで詰まったので失敗かと思ってたんですが結構勝ってました
日本96位なので、賞金ワンチャンスがない...
A問題
こういうのが一番怖い
O(1)でもできるんですけど、沼ると嫌すぎるので1秒ごとシミュレーションしました
あまりを使って移動中か休憩中か判定できます(AC 7:30)
B問題
これもちょっと難しめ？
setで種類数を管理する + isupper, islowerで大文字小文字の判定をします(AC 10:24)
C問題
N ≦15で普通にbit全探索を適用できそうです
使う文字列を決めたら、あとは出現する文字の数を愚直にカウントすればいいです
やっぱりbit全探索はdiff高めにでますね、初心者の時に苦戦した記憶があります(AC 15:31)
D問題
分数のかたちになっていますが、Ai = Aj*Akとしても問題ありません
つまり、AiとAjを決めるとAkが一意に定まります
なので、Ai, Ajの全探索ができないか？と考えます
AjはAiの約数でなければいけないので、約数列挙をします
約数はそんなに多くない(200000以下なら160が最大)ので、十分間に合います
約数列挙も√Aiだけかかりますが、まあなんとかなるでしょう
計算量はO(N (√Ai + D) ) [Dは約数の個数] で雑に見積もっても10^8以下にはなるのでC++なら余裕で通るはずです
Aiを固定した時に、Aj, Akがわかれば、あとはその個数をかけてあげればいいです
まあ想定ではないよなと思っていたんですが、調和級数的に候補を絞れますね、賢い(AC 19:19)
E問題
やることはわかるけどめんどくさいー－－
まあ初手の方針としてはDPがよさそうです
i番目までみたときに長さj
みたいなのはDPに落とし込むのかなり多そうです
ただ、今回は何回同じ文字が連続しているか？によって遷移先が変わる(aaaならa3で2文字増えるだけ、aaaaaaaaaaならa10で3文字増える)ので、そこが大変そうです
遷移はいったんおいておいてDPテーブルを
dp[i][j] = iでいったん区切りが来るもので、そこまでの長さがjであるものの数
と定義します
普通の配るDPだと、dp[i][j]からは
dp[i+1~i+9][j+2]
dp[i+10~i+99][j+3]
dp[i+100~i+999][j+4]
dp[i+1000~i+9999][j+5]
に対して遷移する必要があります
これは区間に対する遷移なので...遅延セグメント木だ！！！！
さあ実装するぞ～～、バグらせたけどなんとかできたぞ
サンプル4は................おっそ....TLE
そもそもN = 1000でギリギリくらいです、かなしい
こういう配るDPで区間に配るやつは、逆に言えばもらうDPで区間からもらうことでも解けます(たぶん？)
こっちを使うと、何がうれしいかというと、もらう場合はすでにそこまでのDPの値が確定しているので、前計算しておくことができます
つまり、
sum[i][j] = dp[k][j] (k = 0 ~ i)の和
と定義した累積和のテーブルをもつことで、sum[i][j]を使って遷移をO(1)にすることができます
これで遅延セグメント木で無駄にかかっていたlogと重そうな定数倍を排除することができて間に合います
遷移の時にj = 0のときは26をかけるが、そうでないときは25をかける(今と違う文字でなければいけないので)ことに注意しましょう
累積和でDPを高速化するのかなり典型だけど無駄に遅延セグメント書いたせいでめちゃくちゃ時間かかってしまった...(AC 71:24)
F問題
爆速で通しててえらい！！こういう最適化はすき
まずt=1によって値が変わるのであれば、それより前は完全に無視してよいです
なぜなら、その前にいくら足し引きしていたところでxに変わってしまうからです
逆に、このt=1を残すと決めたのであれば、それ以降のt=1は必ず無視しなければいけません。そうでなければ、残す意味がありません
ということで、残すt=1を決め打ちすることを考えます
決め打ちした場合に、どう操作するのが最適か？というと
1. それ以降のt=1はすべて無視しなければいけません(無視できないならばその決め打ちは達成できません)
2. 残った操作回数では、それ以降の負の数の中から、できるだけ小さいものを取り除くことが最善です
ちょっと突然かもしれませんが後ろから考えた方が楽に解けそうです
理由としては、後ろから考えると前の方は考えなくてよくなって、選択肢が少ないのでいいかな～という感じです(前からでも無理やりすれば解けるはずです)
後ろから考えたときに1,2をどうすればいいか考えましょう
1については簡単でそこまでにでてきたt=1を数えればよいです(実装上はKをデクリメントすると楽かも？)
2のほうがちょっと難しいです
そこまである数のうち小さい方K個の和がわかればよいということになります
無理やりSegment Treeで殴るのもできそうですが、priority_queueで十分です
t=2のとき、負の数をpriority_queueにつっこみます
これが小さい方K個の候補になります
もしK個を超えてしまった場合は、候補にならないので捨ててしまうとよいです
単純にpriority_queueの和を計算する機能はないと思いますが、priority_queueの和を表す変数をもっておいて、加える/捨てる操作をしたときに足し引きすればよいです
これでt=1の場所を決め打ちした時の最善がわかるので、あとはそれぞれの最大値をとってあげるとよいです
この実装をするとt=2しかない時にめんどいので、t=1, x=0をはじめに入れておくと場合分けなくできてうれしいです (AC 81:52)
G問題
xorの最大化・最小化は行列で頑張るとできることが多いのでそうかな～とは思ったんですが、よくわからなかったです...
総括
またEでやらかしたかと思っていたんですが、普通に難しかったらしくて助かりました
久々にABCで2300over出せてうれしいぞ～～～
ただいま黄色
