AGC040

ワクワクの深夜コン。ABの2完だった。

A - ><

ナナメ矢印を紙に書いてみると、谷になっているところを0より大きくするメリットがなさそうだと気づく。そこを0にすればあとは左右に増えていく。たとえば右に3連続で増える（その次に列が終わるか減り始める）とすれば、山頂は少なくとも3以上となる。その山に逆側から5連続で増えてるとすれば少なくとも5。そのとき山頂は少なくとも5であることがわかり、それは達成できる。そういうイメージはけっこう早い段階で浮かんだが、実装がきつかった。sがN-1文字しかないとか1の差がややこしい。端っこは (i == 0 || s[i - 1] == '>') && (i == n - 1 || s[i] == '<') のように処理した。こうして谷を検出し、そこから両側へ1ずつ増やしていく。俺が実装に時間かかるのが難点だけど、これがAGCのAだなあほんといいなあと思って考察していた。

B - Two Contests

提出に考察コメントががっつり書いてある。そういうときのほうが調子いいのでは？まず、区間の位置で左右に分けるとか、でかい1問だけのセットにするとか、同じ区間が複数あったときとかを考える。しばらく紙に色々な区間を書いて考えた。ソートして必要なら座標圧縮してBITに足しながらとかを思いつき無理そうだなあとか思ってた。そのうちに、Lが最大の区間とRが最小の区間の2つが特別な性質を持っていてちょうど2つに分けるから使えるんじゃないかと気づく。Lが最大の区間は何と組み合わせてもLが悪化しない。ここらで、区間を足すことにはデメリットしかなく、区間を引くことにはメリットしかないこともちゃんと認識しておく（コメントで「そもそも片方を0問にするメリットはない」と書いたが、コンテストを1回にするならそうだが、普通に考えれば無限に広い区間になってしまう（これはひどいこんな奴がACとっていいのか？））。考えるのが面倒なのでN=2は場合分けしてしまった。Lが最大かつRが最小の区間が見つかったときも簡単なので先に処理。ほんとはこういうのをまとめて処理したいけど、厳密に考えることを優先した（けっこう珍しいパターン）。あとは、2つの特別な区間を同じグループにするかどうかで分けるだけ。同じ場合は簡単（一番長い区間1つだけのグループを作り残りを全部引き受ける）。違うときは、区間をLでソートしておいて、Lが最大の区間は複数あるかもしれないがソートした最後の要素とする。そうすると、分け方はソート済みの列をどこかで切ったものだけを考えればよくなる。なぜなら、Rが最小の区間（のうちの一つ）と区間[L_i, R_i)が同じグループならLがL_i以下の区間も全部同じグループにしてデメリットがないので。昇順にソートした後ろから見ていけばスコアが計算できるので、これで解けた。

ところで、この問題設定はパッと見「全完した人だけが楽しい」ということかと思ってしまうが、「全完する人が多いコンテストは参加者にとって楽しい」と解釈したほうが自然だと（解いてる途中で）思った。

CDEF

残り1時間強。CとDを読んで、難易度的にはCだけどDのほうが得意そうと思って交互に考えていた。しかし全然わからない。Dはランダムじゃなくて位置が固定ならまだしもランダムなうえで最善の配置にする（構成せずに勝率だけ求まるのか知らんけど）とか無理だし。Cはあまり得意なイメージない。'A'と'B'だけで構成された文字列として貪欲に取っていっていいのかな、それなら数えられなくもなさそうだけど、みたいな。'C'が加わるとそれが分断されてしまい、わからなくなる。残り30分（午前2時）になるとさすがに（今の生活リズムだと0時過ぎは目がさえる時間帯だとはいえ）眠くなってくる。考えも進まなくなってつらいので、EとFも読んで4問を順番に考えていた。AGCで配点を全部100点にして問題の順番をシャッフルしたやつに出てみたいと思った（実際に出ることになったらかなり怖いとは思うけど）。「これ実は600点だよ」と言われて反論できるところまでは考えられなかった。残り5分になったところで歯磨き（済ませてあるがコンテスト中にラムネを食べた）とトイレに立った。