naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Regular Contest 097

2完でレートちょい下げ (1723→1699)
パフォーマンス1521... 2回に1回ぐらいでいいから3完したい…
f:id:n4_t:20180512232412p:plain:w400

C - K-th Substring (300)

最初ずっと全然違う問題を自作して解いてた…
(サンプルケース通らないしなんでだろうと)
問題を読み返して気を取り直して
とりあえず、全パターン作ってみる?
→TLE(部分点200)https://beta.atcoder.jp/contests/arc097/submissions/2497269
そりゃそうか

suffix array作るか
qsort()に渡すcmp()関数を書くのに手間取ったりして
ソートした各suffixを、頭から1文字ずつ取って(prefix)、既出でなければ+1
で、K番目のやつを返す
→AC https://beta.atcoder.jp/contests/arc097/submissions/2499750
cmpでstrcmp使ってるけどstrncmpで先頭5文字だけ比べればよかったなこれ

D - Equals (400)

UnionFindで交換できる2点を繋いでいく
島の中だったらどこへでも移動できるので、p[i]=i になるような最大数を島ごとに数えて
→AC https://beta.atcoder.jp/contests/arc097/submissions/2501060

E - Sorted and Sorted (600)

白だけ見てバブルに並べ替えて(影響のある黒も動かして)
黒だけ見てバブルに並べ替えて(影響のある白も動かして)
みたいな嘘解法を終了2分前に投げた
→WA https://beta.atcoder.jp/contests/arc097/submissions/2504150

F - Monochrome Cat (800)

開いてない