TTPC2015 C. おおおかやま 講評

問題

https://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_c

解説

https://bitbucket.org/ttpc2014/ttpc2015/overview

想定解法

実装問題です.考察すると,ある長さの良い文字列は必ずある答えになることが分かります.長さを$100$から$3$まで動かして、$S$中に含まれるものをまとめて変えるととても楽に実装ができます.$O(|S|^{2})$でできます.

提出者の解法

問題文通りにやっている人がほとんどでした.予想通りです.賢くやっている人もそれなりにいたので結構嬉しいです.

感想

面倒なやるだけ問題として解くか,考察を続けて楽な$O(|S^{2}|)$解で解くかという二択の問題になっています.実装が得意な人は前者で解いて大丈夫だと思いますが,不安な人はもう少し考察を続けても良かったと思います.個人的には面白いバランスの問題になっていると思っていて結構気に入っています.

テストケースは若干弱かったようです.こういう問題のテストケースを作るときは境界っぽいところはちゃんと作らなくてはダメですね.