MENU

[全探索:全列挙を抑える] pythonで競プロ 過去問精選 100 問

Qiitaで紹介されていた初中級者が解くべき過去問精選 100 問をpython解いてみようという試みです。めちゃくちゃ競プロ慣れしている人種ではないので、初学者にもわかりやすいコードになっていると思います。良かったら読んでみてください。

第1弾として、「全探索:全列挙」の項の問題を解いてみます。

目次

第1問:How many ways?

問題文

1 から n までの数の中から、重複無しで3つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja

制約条件

• 3 < n < 100
• 0 < x < 300

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja

解答

説明

3つの数の組み合わせを全列挙して、合計数がxと一致するものをカウントする方針です。

i,j,kは以下のように定義しています。

  • 1 ≤ i,j,k ≤ n
  • i < j < k

三重ループを作り、各階層で前の階層の数字より大きい数字を検索することによって、重複なく3つの数の組み合わせを全探索できます。

pythonのrange(x)は、1~xではなく、0~(x-1)を返すので注意が必要です。

ネストアレルギーを持っている人向けに、内包表現を用いた別解も載せておきます。

別解(内包表現)

第2問:105

問題文

105 という数は, 非常に特殊な性質を持つ – 奇数なのに, 約数が 8 個もある.

さて, 1 以上 N 以下の奇数のうち, 正の約数を ちょうど8 個持つようなものの個数を求めよ.

https://atcoder.jp/contests/abc106/tasks/abc106_b

制約条件

N は 1 以上 200 以下の整数

https://atcoder.jp/contests/abc106/tasks/abc106_b

解答

説明

1~Nまでの奇数をrangeによって生成し、各値に対して約数のカウントを行っています。

range(1, n + 1, 2)に関して、rangeは第三引数としてstepを与えることが出来ます。これによって、1から2ずつ+した値を生成されることになるので、結果として奇数のみをみることが出来ます。

また、if condition:のcondition部分に整数値が与えられた時、0であればFalse、それ以外であればTrueと判定されます。つまり、「if not x % i」は「xをiで割った余りが0以外でなければTrue」となり、約数であれば条件を満たすことになります(notは真偽値を反転させます)。

第3問:ATCoder

問題文

英大文字からなる文字列 S が与えられます。S の部分文字列 (注記を参照) であるような最も長い ACGT 文字列 の長さを求めてください。

ここで、ACGT 文字列とは ACGT 以外の文字を含まない文字列です。

https://atcoder.jp/contests/abc122/tasks/abc122_b

制約条件

S は長さ 1 以上 10 以下の文字列である。
S の各文字は英大文字である。

https://atcoder.jp/contests/abc106/tasks/abc106_b

解答

説明

ACGTの文字が連続した場合にカウントを行い、連続が途切れた場合はカウントを0に戻します。そして、カウントが過去の最大値よりも大きい場合は答えを更新します。

小技ですが、2値を比較して大きい方に更新する処理は、if文を使わなくてもmax関数によって代用出来ます。

第4問:カラオケ

問題文

1,2,…,N と番号づけられている N 人の生徒から成るグループが,「全国統一カラオケコンテスト」に出場することとなりました.
このコンテストで歌える曲は,曲 1,曲 2,…,曲 M の M 曲あります.また,番号 i の生徒が曲 j を歌うと,必ず A_i,j点を取ります.
さて,コンテストのルールは,以下のようになります.

• M曲の中から 2 つの曲を選ぶ.(それぞれ T_1とT_2とする.)
• それぞれの生徒が,曲 T_1と曲T_2の両方を歌う.
• 各生徒の得点は,その生徒が歌った 2 つの曲の点数のうち高い方となる.
• グループの得点は,生徒 1,2,…,N の得点の合計となる.

そのとき,グループの得点として考えられる最大の値を求めてください.

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c

制約条件

1≤N≤100
2≤M≤100
0≤Ai,j​≤100 000 000
• 入力はすべて整数

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c

解答

説明

2次元配列を用いているが、全探索の仕方としては第1問と同じです。

2曲の組み合わせを全探索で選択し、生徒ごとに点数の高い曲の点数を合計して最も点数が高い2曲の点数を出力の流れです。

感想

色々と解き方が違い、上手く問題がチョイスされている気がするので、完走出来れば力が付きそうな気がいます。

ただ、この後の問題に叩きのめされ力尽きていました。。。モチベが戻ってきたので、リベンジして行こうかなと思っています。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

この記事を書いた人

コメント

コメントする

目次