3完 97:23 506位
テスト勉強で出るつもりじゃなかったんですが、問題見てみたらC解きたかった＆思ったよりテスト勉強の進捗がよかったので15分くらい遅れて参加
C->A->Bで通したのでAC時間が変なことになってます
A Divide String
ARC-Aによくありがち
もし2個より多く分割できたときt1 < t2 < t3 ... となっていますが、そのようなときにt1 < (t2 + t3 + ... )が必ず成り立ちます
なぜなら t2に何を足しても辞書順でt2より小さくなることはないからです
よって、条件を満たすなら2つに分割する解が存在するので、切れ目をどこに入れるか全探索すればよいです
(AC 90:55)
B Favorite Game
問題名の由来、なんだろ
ある区間があって、その中に含まれるものの個数を増やしたいという問題です
どういう操作ができるか考えると
・区間を広げる(縮める意味はない)
・外にあるものを区間内に持ってくる
の2つになります
A = (1,3,5,5)のようなものを考えるとわかりやすいかなと思うんですが、区間の外にあるものを2個以上持ってくるなら、そもそも区間を広げてあげたほうがよいです
というかそもそも、外にあるものを1つ区間内に持ってくる操作回数と同じ操作回数で区間を広げることができるので、「区間を広げて損することはない」です
よって、A1, A2のみ動かせばいいということになります
ここまでくれば、A1,A2を除いたものをCとすると、Cをソートした配列で長さMの区間をすべて調べればよいです
区間を固定すると操作回数は max(0, A1 - C[i]) + max(0, C[i+M-1] - A2)で表されるので、この最大値を計算すればOKです
(AC 97:23)
C Harmonic Mean
判定込みの構築で、ちょっと苦手なタイプではありますが頑張ります
まず自明なところを処理すると、N=1 は A=(1)で満たします
N=2は無理です(1/3以下を2つだと1にたどりつかない & 1/2を使うともう一つも1/2)
N=3,5があるので少なくとも奇数はつくれるんだろうなと思います
いきなり大きなNのときの解をつくるのは難しそうなので、N=3,5の解をもとにして作ることを考えます
N=3を参考にすると、1/2 = 1/3 + 1/6になるのでこれを使ってみます
たとえば、1/3 = 1/6 + 1/12, 1/6 = 1/12 + 1/24のように分解していくと、1つの分解でNを2増やすことができます
ただ実際にこれでプログラムを動かしてみると、重複がない場合100個にも到底届かないようなものしか構築できません
よくよく考えると、これで表されるのは 1/2^a 3^bの形で表されるものですが、この個数を愚直に全探索で計算してみると(たぶん)276個になるので、制約的にどんなに天才でも達成できないことがわかってしまいます
解決策としてはもう少し複雑な形(1 / 2^a 3^b 5^c 7^d など？)を考えるか、ほかの手段を考えるかになりますが、前者でうまくいくビジョンがあまり見えなかった(tatyamさん解説に解法あり)ので他の手段を考えます
さっきの手法だと答えに使いたい数の分母が指数的に増えていって困ったので、あまり増えないようにしたいなと思ってみると、そういえば1/6 = 1/7 + 1/42にできたなとなります(え？)
こう考えると、1/k = 1/(k+1) + 1/k(k+1)に変換できるので、これを使えないかなと思います
直感的には小さいものを分解すると、すでにつくっていたものとかぶりやすいかな？と思うので、一番大きな値を分解していって、かぶらない＆10^9を超えないならば貪欲に分解することにします
実際にこれでプログラムを回すとN=500でも問題なく、1回の操作でNが1だけ増えるのでN=3~500で構築できることがわかります
(AC 88:20)
総括
Cこんなに通されるのか...みんな構築に強すぎる
