AtCoder Beginner Contest 167 備忘録

AtCoder Beginner Contest 167の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 167 - AtCoder

今回はABCD4完でした。

・A問題:Registration

文字列 s と文字列 t が与えられ、t の末尾を1文字削除したものと s が同じか判定する。

解答例(Python)
https://atcoder.jp/contests/abc167/submissions/13088808

・B問題:Easy Linear Programming

1が書かれたカードが A 枚、0が書かれたカードが B 枚、-1が書かれたカードが C 枚あり、そこから K 枚選んだ時の書かれた数の和の最大値を求める。
最大化したいので 1→0→-1 の順で使うのが良い為、K から A ・B・Cの順で引いていき、K が0になる時の使ったカードの和を出力する。

解答例(Python)
https://atcoder.jp/contests/abc167/submissions/13090439

・C問題:Skill Up

N 冊の参考書がありそれぞれ Ci 円で売られていて、それを読むことで M 種類のアルゴリズムの理解度が Aij 上がる。
M 種類のアルゴリズムの理解度を X 以上にする事が可能ならば必要な金額の最小値を出力し、不可能ならば-1を出力する。
制約から N≦12 と小さいので全探索で求める事が可能。N 冊の参考書をそれぞれ買う・買わないで選択していき、買った場合の必要な金額と、各アルゴリズムの理解度を配列で持ち最終的に全て X 以上であればそれまでの金額とより小さい方を求めていく。もし理解度が X に満たないものがあれば金額の比較はせず処理を進め、探索が終了した時点での金額を出力する。
最終的な金額が ans の初期値と同じ場合、全てのアルゴリズムの理解度を X 以上にすることは不可能なので-1を出力する。

解答例(Python)
https://atcoder.jp/contests/abc167/submissions/13091514

・D問題:Teleporter

1~N までの番号が割り振られた町があり、それぞれの町にテレポーターが1台ずつ設置されていて、転送先は Ai である。
町1から出発してちょうど K 回テレポーターを使用した時にどの町に到着するか求める。
制約から K≦10^18 と非常に大きいので愚直に追って行っては間に合わない。しかし町の数は N≦2*10^5 程度なので、まずテレポートするルートを求めておく。すると必ずループする部分が出てくるので、K からループしない部分の回数を引いてからループする部分の長さで割った剰りが最後のループ内の移動回数になる。

解答例(Python)
https://atcoder.jp/contests/abc167/submissions/13092013