Ruteのプログラミング日記

競技プログラミング(AtCoder)の問題の解説や、過去問を解いた感想、また解けない過去問について共有したいと思ってます。

AtCoder Beginner Contest 167 解説 (A ~ C)

AtCoder Beginner Contest 167の解説(A ~ C)です。

今回私は都合によりバーチャル参加をすることになりました。

時間内にABしか解けず2完でした(参考パフォーマンス559)

が、Cも解くことが出来たのでその解説もしたいと思います。

(D問題以降の解説は公式の解説動画を参照して下さい)

A問題 A - Registration

https://atcoder.jp/contests/abc167/tasks/abc167_a

問題概要:

文字列 $S$ , $T$ が与えられるので

文字列 $T$ が以下の条件を満たすか判定して下さい。

$T$ は $S$ の末尾に1文字追加した文字列である

制約が $|T| = |S|+1$ であることから、これは単純な条件分岐で済みそうです

Pythonの場合は T[0:len(S)]がSと同じ文字列かを判定すればよいでしょう。

(応用例制約が1≦|S|≦|T|≦10で、以下のような問題)

文字列 $S$ , $T$ が与えられるので

文字列 $T$ が以下の条件を満たすか判定して下さい。

$T$ は $S$ の末尾に1文字のみ追加した文字列である

コード: https://atcoder.jp/contests/abc167/submissions/13106673

B問題 B -

https://atcoder.jp/contests/abc167/tasks/abc167_b

問題概要:

1が書かれたカードが $A$ 枚、0が書かれたカードが $B$ 枚、-1が書かれたカードが $C$ 枚あります。

これらのカードから、ちょうど $K$ 枚を選んで取るとき、取ったカードに書かれた数の和の最大値はいくつになるかを求めよ。

$K≦A$ の時、1が書かれたカードのみを取るので、最大値は $K$ になります。
$A$ < $K$ ≦ $A+B$ の時、1が書かれたカードを $A$ 枚、残りの枚数を0が書かれたカードで取るので、最大値は $A$ になります。
$A+B$ < $K$ ≦ $A+B+C$ の時、1が書かれたカード全て、0が書かれたカード全て、そして $K-(A+B)$ 枚の-1が書かれたカードを取ることになります。
よって、求める最大値は $A-(K-(A+B))$ になります。

コード:(嘘解法?) https://atcoder.jp/contests/abc167/submissions/13106718

コード:(実際の解法)https://atcoder.jp/contests/abc167/submissions/13128516

C問題 C - Skill Up

https://atcoder.jp/contests/abc167/tasks/abc167_c

問題概要:

以下の条件が与えられます。

参考書の数 $N$ と、学びたいアルゴリズムの数 $M$ ,目標の理解度 $X$
$i (1≦i≦N)$ 冊目の参考書の金額 $C_i$ と、 $j (1≦j≦M)$ 番目のアルゴリズムの理解度の上昇幅 $C_{i,j}$ が記されたリスト( $N$ 行)

この条件を元に、 $M$ 個全てのアルゴリズムの理解度が全て $X$ 以上となる参考書の買い方の組み合わせの内、必要な金額の最小になるときの金額を計算しなさい。

制約

$1≦N,M≦12$
$1≦X≦10^5$
$1≦C_i≦10^5$
$0≦A_i,j≦10^5$

制約の $N,M$ が非常に小さいです。この場合組み合わせはせいぜい $2^{12} = 4096$ 通りなので全探索を用いると良いでしょう。

といいたいところですが、今回は組み合わせの全探索なのでせっかくなので

「Bit全探索」を利用してみましょう。

まずは、 $i (1≦i≦N)$ 番目の商品の値段 $C_i$ と、 $j(1≦j≦M)$ 番目のアルゴリズムの理解度の上昇幅を $N$ 行入力します。

その後、全ての組み合わせにおいてbit全探索を行ってアルゴリズムの理解度の最小値が $X$ 以上となる組み合わせで、本を買ったときの合計金額をリストansに入れます。

最後に、リストansの最小値を出力すれば良いです。(ソート,ans[0]でもOK)

計算量はbit全探索で $O(N 2^N)$ であるため、制約上では十分速いです。

Bit全探索は、組み合わせなどを考察するときに非常に役立つアルゴリズムなのでこの機会に覚えておきましょう。

コード: https://atcoder.jp/contests/abc167/submissions/13123166

以上、 AtCoder Beginner Contest 167 A ~ C問題の解説でした。

次回は体調を整えて参加出来るようにしようと思います。