Qiitaで紹介されていた初中級者が解くべき過去問精選 100 問をpython解いてみようという試みです。めちゃくちゃ競プロ慣れしている人種ではないので、初学者にもわかりやすいコードになっていると思います。良かったら読んでみてください。
第1弾として、「全探索：全列挙」の項の問題を解いてみます。
第1問：How many ways?
問題文
1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja
制約条件
• 3 < n < 100
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja
• 0 < x < 300
解答
説明
3つの数の組み合わせを全列挙して、合計数がxと一致するものをカウントする方針です。
i,j,kは以下のように定義しています。
- 1 ≤ i,j,k ≤ n
- i < j < k
三重ループを作り、各階層で前の階層の数字より大きい数字を検索することによって、重複なく３つの数の組み合わせを全探索できます。
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 文字列とは
https://atcoder.jp/contests/abc122/tasks/abc122_bA,C,G,T以外の文字を含まない文字列です。
制約条件
• S は長さ 1 以上 10 以下の文字列である。
https://atcoder.jp/contests/abc106/tasks/abc106_b
• S の各文字は英大文字である。
解答
説明
ACGTの文字が連続した場合にカウントを行い、連続が途切れた場合はカウントを0に戻します。そして、カウントが過去の最大値よりも大きい場合は答えを更新します。
小技ですが、２値を比較して大きい方に更新する処理は、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
https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c
• 2≤M≤100
• 0≤Ai,j≤100 000 000
• 入力はすべて整数
解答
説明
2次元配列を用いているが、全探索の仕方としては第1問と同じです。
2曲の組み合わせを全探索で選択し、生徒ごとに点数の高い曲の点数を合計して最も点数が高い2曲の点数を出力の流れです。
感想
色々と解き方が違い、上手く問題がチョイスされている気がするので、完走出来れば力が付きそうな気がいます。
ただ、この後の問題に叩きのめされ力尽きていました。。。モチベが戻ってきたので、リベンジして行こうかなと思っています。
コメント