JOI 2015/2016 本選（オープンコンテスト） C問題
前回、C問題がMLE…と言っていましたが、ばとんさん(@goodbaton)さんから範囲外参照だとご指摘を頂きました。
確認してみると、こんなケースで誤作動するようです。
辺が値上がりしないと、outがINT_MAXのままになってしまうので、範囲外となります。
ということで、1行加えたら無事ACしました。REだったようです。
https://github.com/HyogaGlacier/Other-Programing-Contest/blob/master/2016-ho-t3.cpp
しかし、「発想はあっているのに、実装でつまらないバグを埋め込む」っていうのを何とかしたい…
DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C:アメージングな文字列は、きみが作る！
やはり文字列操作は苦手なようです。
問題概要
文字列sが与えられる。K回の以下の操作が可能である。
- ある文字を削除する
- ある文字を置換する
- 文字を1文字任意の位置に挿入する
K回の操作後に辞書順最小となる文字列は何か。
discovery2016-qual.contest.atcoder.jp
解説
取り敢えず置換と挿入は全てaで行います。
まず、s中にaが何文字あるか確認します。K回の操作でsを全てaにすることが出来る場合、a以外の文字を全て削除し、その後余った手数で文字列の文字数を出来る限り削れば答えが得られます。
K回の操作でsをaのみの文字列に出来ない時、文字列の初めをaの羅列にすることで辞書順最小になります。ただし、この時ただ文字を置換するだけでなく、挿入する方がいい場合があります。
その例がs="abc",k=1のパターンです。
まず、元々aの部分は置換する必要がないので、それを考慮した上で何文字目まで置換でaの羅列に出来るかを求めます。
i文字目までaにすることが出来るとすると、最後のi文字目を置換ではなく、文字列の最初にaを挿入することでもaの羅列の数は同じです。同様にaの羅列の数が変わらない範囲（＝iから戻って行き、最初のaにぶつかるまで）ならaを同数文字列の初めに持っていけます。
そうしたら後はそれらの中での辞書順最小が分かれば正解が分かります。
接尾辞配列を用いて範囲内でrankが最小のものを探せば上手く行きます。
Submission #637830 - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 | AtCoder
感想
接尾辞配列初めて使いました。ローリングハッシュでも通るらしいですが、これも使ったことないですね…
yukicoder No.202 1円玉投げ
久々に問題を解いた。JOI本選（オンライン参加ですが）も近いので、ある程度はやっておこう。
問題概要
N個の半径10の円形コインを投げる。投げた時にコインが重なるようであればそれを取り除く。
N個のコインの中心座標が与えられるので、N回投げた後いくつコインがあるか求めよ。
続きを読むDISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選（A,B)
２完＋部分点１０点でした。
続きを読む