Codeforces Round #616 (Div2) 参加記録

A, B, Cの3完でしたが、ムーブが最悪だった感じでちょっと悲しかったです。 C通った後に速度が不安になってC#で書き直して20分消費した後、Dが数分間に合わなかったので... が、何はともあれ青色になれました。次は紫目指します。

A Even But Not Even

２つ以上奇数があれば奇数を２つ並べるといいです。 奇数が１つ以下だと無理です。

B Array Sharpening

0indexで以下を満たすkがあればいいです。

ai<i (i<=k) and ai < N-1-i (k<=i)

ミスが相次ぎ3WA出しました。第一の失敗ポイント

C Mind Control

N人(自分含む)が一列に並んでいて自分はM番目にいます。また、長さNの数列が与えられます。 列の先頭の人から順に数列の最初または最後の数を適当に取っていきます。 自分はK人に対して予めマインドコントロールしておき、最初を取るか最後を取るか操作できます。 一人目が取り始めた後はもうマインドコントロールはできません。 ある操作をしたときに自分は最低でもx以上の数が取れるようになるとして、xの最大値を求める問題です。

まず、自分より後ろの人は操作しても意味なしです。 前の人を操作しましょう。 自分の番が来た時、数列は長さN-M+1になっています。このうち、最初と最後の大きい方をとればいいです。 操作することを考えないと、自分に残される長さN-M+1の数列候補は当然M個あります。 前の誰かに前を取るように操作したら、数列候補から先頭が消えます。後ろを取るように操作したら最後が消えます。 こうして残った候補の中で最小となるのがxです。

前を取るように指示するのをj人、そうでないのをK-j人として全探索すればいいです。 各jについて最小値を求めるので愚直にやれば、K*(N-M-K+1)の計算量となります。スライド最小を使えばKlogKになります。

愚直でもK<=1500なので通ると思ったのですが、制約が1sを見て不安になりC#で書き直し20分ロスしました。 C#の練習をした後だったので出来上がったpythonコードがあるなら数分で描き直せると思ったのですが...

D Irreducible Anagrams

はじめ問題設定が複雑に感じて苦戦しました。 ある文字列sがあって、それとanagramになる文字列tのうち、irreducible anagramとなるものがあるかを判定する問題です。 sとtをそれぞれ2つ以上に分割してs1, t1 , s2, t2, ..., sk, tk を得たときにsi, tiが全てアナグラムになっているような分割の方法があるとき、s, t をreducible anagramと呼びます。 irreducible anagramはreducibleでないものです。

結論からいうと、長さ2以上で先頭と最後の文字が同じで2種類しか文字種類がないときにはirreducible anagramとなるものはありません。そうでない時はirreducible anagramとなるものが構成出来ます。 ここまでなんとなく気付いたのは割と早かったのですが、自信がなく証明しようとしても上手くいかず、ギリギリにとりあえず出そうと実装をはじめた結果間に合わず破滅しました。 エスパーで出そうとして完全に嘘で失敗して時間を溶かしたこともあるので証明をちゃんとするか取り敢えず実装するかは迷いどころですね。