AGC037

今日は体調が悪かった。エアコン付けても寒いし暑い。体温は最高で37.5あって今日のAGC出られないかなと思ってた。直前まで様子を見てたけど、36.9まで下がって気分も悪くないので出ることにした。コンテスト中に何度か測ったけどずっと37.2くらいだった。今は36.9。自分では、いつもとそれほど変わらないパフォーマンスが出せている感覚だった。レーティングを気にせず、やりたくないAを途中でやめてBCへ行き面白そうなCをやれたので、まさに最近の自分が目指していた楽しむこと優先の立ち回りができていたと思う(素晴らしい)。ただ、今まで水色パフォ以上しか取ったことなかったのに、灰パフォを取ってしまった。それを知って特にショックを受けなかったのは、熱があったからだろうか。まあそれはいいけど、今夜や明日あたり、tokuminiさんやdasaponさんの結果と比較してわかる自分の無能さに落ち込むんだろうなあとは思う(今から気が重い)。最近思考が遅いのは悩んでるけど仕方ないのかねえ。

体調がうんと悪くなったら撤退することになるので覚悟していたが、最後までコンテストに参加できてよかった。展開上、NoSub撤退になる心配が出ていたが、それも気にせずやりたい問題をやった。結果的にはC問題を提出できた。0完だけど、まあNoSub撤退よりは気分がいい(これも世間体を気にしたゴミみたいな感情だけど)(参加したのに成績表に載らないのはかなしいというのもある)。

A - Dividing a String

ここ「すべてのiについて」って書いてほしいなあ。「あるiについて」かもって思うじゃん。問題文を読むのに2分以上かかった。いくつかの例をいじってみるが、a aaa aみたいな分け方まである(これはaa a aaでも行けるとあとで気づいた)。隣り合う文字が同じときが問題なわけで、両側の文字が同じ境目を管理する?どうせKは|S|*2/3くらいにはなるだろうし。しばらくして、DPを思いつく。高々3文字っぽいし、最初のi文字で区切れて最後がk文字の最小を持つ。ただ、S_iが4文字あれば十分な証明すらできない(あまり時間をかけたくないので)。まあ2文字でいい気がするけど。妥協して証明なしの5文字でやるとして、DPの更新がかなりめんどくさい。さすがにそれはAGCじゃないよね?何か簡潔な解法があるはず(ないならやりたくない)。いつの間にか25分も経っていた。見限るのがちょっと遅い。BとCへ。

B - RGB Balls

RGBではなく012で考える。各1について02を探す。左右両側か、片側だけか。両側の場合両方効くが、片側の場合は遠いほうだけ影響する。いや最小を一つ求めるのでさえ大変なのに、(最小を求める必要があるかは知らんけど)その通り数だなんて最初から無理だと思ってた。10分くらいで切り上げてCへ。

C - Numbers on a Circle

BとCを1秒ずつ見た感じでこっちのが面白そうだと思い、まずCをやる。逆から考えたらどうかと思いついたが、そこから進展せず、10分ほどでBへ。

Bから戻ってきた。逆から考えて、減らせるときは減らす以外にその要素を変化させる方法がないことに気づいた。以降、Cをメインにやった(詰まったときにAやBを考えていた)。面倒なのでソースに書いた考察メモを転記する。

//逆操作を考えると隣2つの和を引いてもA以上でなければならない Aは1以上なので和より大きくないといけない
//引ける候補は多くとも1つおき
// 1 10^9 1 みたいなときは10^9/2回くらい必要になる
//a b c d となっていてbが減らせるとき、b>a+cなのでaやcはbが変化しないかぎり減らせない
//つまり、bが変化しなければならないなら現在のa,cで減らせるかぎり続ける必要がある Aに等しくなるか減らせなくなるまで 最小もくそもなくそうするしかない
//Aより大きくても、隣より小さくなればチャンスはある 隣が減らせるようにならないのにAに等しくならなかったらもうbは変化できないので-1
//減らせるやつをリストアップする a b c d e
//cより大きい間はbを減らし続ける必要があり、結局bは(Aに等しくなった場合を除き)cより小さくなる
//新たに減らせるようになるのは、減らしたやつの隣のみ これをO(N)回繰り返す時間はない
//減らしたa b cだけに注目するとb>a+cがb

最初は、最大でN/2個の更新ポイントを(隣り合ってないので)一気にやっていくことを考えていたが、よく考えるとBは常に更新しているのでそうなってない。ただ、減らせるものは減らす必要があるのでこれでも解けていると思った。提出するもWAとREが出る。REが一つでもあるとコンテスト中は実行時間が表示されないので困ると思った(更新回数は各要素についてO(log(B))で済むと結論は出していたものの)。REの原因は、Bを更新しながらだからN個を超える更新候補が出ることだと見当が付いた。やはりキューにすべきだったかーと思いキューに書き換えて提出。REはACになった模様。しかしけっこうな数のWAがそのまま残っている。絶対に正しいようにしか見えず(こうなったときってほんとバグが見つからない)、逆立ちしてソースを見たりしたいと思ったけどできないので、きれいに書きなおして最後記念提出して終わった。

(追記)関係ない悪夢をみていた気がするが、寝起きにふと気づいて出力のint r; をll r; にしたら通った。これは、-Wconversionとか付けてる場合じゃないなあ。出力が32bitに収まらないのは途中で気づいていたが、まだ解けてはいなかったのでそれどころじゃなくて最終的に忘れるやつ。ここまで「正しい」コードだと、コードの見た目ではバグを発見できないなあ。見た目に頼りすぎ。どうしたら防げるミスかわからない。