00:42成績:ABEを解いて100位コンテストページ:https://beta.atcoder.jp/contests/agc026とりあえず、Fから考え始めた。Nが偶数の場合は、どちらかの端から取っていくのが最善であることがすぐ分かる。Nが奇数の場合は、すぐには思いつかなかった。Fは、配点的にも難しい可能性があるので、放置して次に進むことに。(ここで消費時間10分ほど)Eを考え始める。Eは、ある条件を満たす部分列であって、辞書式で最大のものを作る問題。N=3000なので、O(N^2)解法まで許されるということを念頭において考察を開始した。辞書式順序を考えているので、まず最初にbが幾つ並ぶかが重要。そこで、その部分から考え始めることにした。最初に選ぶbの場所の座標をxとして、またそれに対応するaの場所をyとする。x>yは、aから始まるという酷いシチュエーションなので、とりあえず、x<yの場合を考えることにした。</ppp>すると、xとyの中間の位置にあるbは全て回収していくのが最善となる。よってスタート場所を指定すれば、最初にbが幾つ並ぶかが分かることになる。この個数が単独一位になっている箇所が1箇所だけであれば、それで開始箇所が分かるが、そんなに甘くないことはすぐに分かる。よってb...baとなってから以降の箇所についても、ちゃんと考えないといけない。このあたり、じっくり考えないとすぐに混乱するので、時間がかなり消費される。ここを考えてると、aの個数とbの個数が一致するような切れ目(i番目までに含まれるaとbが一致するようなi)が重要になってくることに気づいた。これに気づいた理由は正確には覚えてないが、丁寧に考えれば、どんな道筋を辿っても必然的に思いつくことで、非自明な箇所ではない。反射的に思いつく内容でもないので、少しは時間を消費した。abが同数となる切れ目で分割しておくアイデアに気づいいてからは次の通り。最初の文字がaとbで場合分けをする必要がありそうだと思う。bから始まる場合はさっきの発想を延長させればいい。aから始まる場合は、少し考えてabab交互に並べるのがよいと分かる。実装については次のようになった。endl;}実装自体は綺麗にできたと思うが、そもそも量が多いので、実装にもそれなりに時間がかかってしまった。バグには殆どハマっていない。慎重にやりすぎた可能性はある。結局Eの消費時間は80分ほど。(合計で90分)ここは、時間を使いすぎてる感があるが、今の所、改善方法は思いつかず。残り時間やばいなと思いつつDを開く。左から順に埋めてくdpを考える。全ての数え上げと、右側部分が交互に並んでいる場合の数え上げと、2つ用意してdpすれば良さそうだと思って、漸化式を作り始める。それだと駄目なことに気づく。Dの配点は1100点でBCを解いたほうが配点が高い。それを思ってDをやめてBCに移ったが、結果的にCは解けなかったので、Dに時間を掛けたほうが良かったかもしれない。何はともあれ、BをDを諦めた時点で残り時間は40分ほどだったように思う。