srm452
とても久しぶりに参加。
div1:250 NotTwo
最大1000*1000の盤面に、ユークリッド距離が丁度2になるような石のペアが存在しないように可能な限り石を置いた時に最大でいくつ置けるか。
整数座標でユークリッド距離が丁度2になるのは上下左右に2マス離れた場合だけ。
なので石を一つ置くと、置けないという制約がかかった場所が新たに最大4つできる。
制約がかかった場所を最小にしたいが、共有出来る制約が最大4である事は明らか。
そのような置き方は、盤面が無限に広がっている場合「斜めにジグザクに置く」「2*2の石を出来るだけ敷き詰める」という二つの置き方が考えられる。
盤面が2*2とかの時を特別扱いしなくて済むので後者でやると楽。
というのは終わってから気づいた話で、system test中とてもひやひやしてました。
passed system test 174.04
div1:500 IOIString
I,O,?の三文字のみからなる最大長さ2500の文字列が与えられる。
?をIまたはOと置き換えると、
I...(n文字)...O...(n文字)...I
のような部分文字列を含む文字列(IOI string)はいくつ出来るか。
IOI stringでない文字列の数はそれほど多くないので、そっちを引くのかなぁと思った程度。
compiled(challengeする事もあろうかと思って)
div1:1000
読んでません。
opened
結果は250で得た174.04のみで、レーティングは1413 -> 1427と微増。
良いなー黄色良いなー。