AGC016 A 考察

AGC016 A - Shrinking

入力例 1 の serval の各文字の数値から挙動を考える。

• s: serval → serva → serv → ser → se → s
• e: serval → eerva → eerv → eer → ee
• r: serval → srrva → rrrv → rrr
• v: serval → sevva → svvv → vvv
• a: serval → seraa → eraa → raa → aa
• l: serval → erval → rval → val → al → l

条件をかんたんにして考える。各文字が一度しか出現しないものとする。ある文字 x を決める。その文字の出現位置よりも右にある文字数分は少なくともかかる。右側の文字を削る間はその文字の出現位置より左側にその複製を増やすことができる。右にある文字数分の回数のあと複製から左側の文字数分がかかる。

文字が複数回出現する条件で考える。右側の文字数と左側の文字数を読み替えると良さそうだ。最も右の出現位置から右にある文字数。すぐ左の同じ文字 'x' または左端との間の文字数。こう読み替えると良い。これを数えるのは O(N) 。

英小文字の 26 回だけ O(N) N <= 100 を繰り返して最小のものを出力する。これは間に合う。

https://atcoder.jp/contests/agc016/submissions/15736928

bouzuya/cookie-storage v6.1.0 をつくった。

SameSite=None を指定できるようにした。ただきちんと書き込めているのかは試していない。

リングフィットアドベンチャー 51 日目 レベル 96 ワールド 11 。

ちょっと良くない感じになっている。