AtCoder Beginner Contest 167
ABCの3完。Dがバグって無限に時間を溶かした。EFは読んでない。
A - Registration
tの最後の一文字を除いたものとsを比較。substring()に入れる添字に注意。
B - Easy Linear Programming
1はなるべく取るほうが大きくなるし-1はなるべく取らないほうが大きくなるのでa > b > cの順番で取っていく。
nがaとa+bと比較してどの場所にあるかで場合分けして答える。
C - Skill Up
N <= 12なのでそれぞれの本を買う/買わないでbit全探索しても全然間に合う。
あとはすべての言語の理解度がXを超えている中で金額が最小になるものを選ぶ。
D - Teleporter
N個の頂点に対してN本の辺があるので絶対に循環が存在する。このグラフに対してフロイドの循環検出法を用いて、1からその循環に入るまでの辺の数λと循環の大きさμ、1から進めて最初に循環に入る場所mを算出する。 k < λのときは閉路にたどり着く前に数え終わるので普通に1から進んでいく。λ < NなのでこっちでTLEすることはない。
λ <= kのときは、まずmまでλ回進める。のこりk - λ回。循環はmから初めてμ回でmに戻ってくるので、k - λをμで割った余りの回数だけmから進めればいい。こっちもN回以下しか進まないのでTLEはしない。
前者を忘れていてWAが取れなくて時間切れ。