AtCoder Beginner Contest 165(ABC165) A~Cの復習
おひさしです。生きてます。
知らんうちにはてなダイアリーが終了してて、
知らんうちにはてなブログに移行されてました。たすかる。
最近は夢も希望もないので、AtCoderで競技プログラミングをかじるやつをやっています。
昨日(2020/5/3)開催されたAtCoder Beginner Contest 165 に参加したので、
参加時の自分のお気持ちみたいなやつを書きます。
A - We Love Golf
A ≦ nK ≦ Bなるnが存在するかどうかを調べました。
A,Bは1~1000なので、全部調べれば良いです。
K = int(input()) A,B = map(int,input().split()) is_OK = False for i in range(A,B+1) : if (i % K == 0) : is_OK = True break if (is_OK) : print("OK") else : print("NG")
発想や書き方が冗長な気がしてきますが、
WAになっておどりたくないのでコンテスト中はこれで良いと思ってます。
B - 1%
100円預けていて、1%の利子が付きます。
1年後には101円になります。
翌年は101円に対して利子が付きます。
単利と複利ってなんだっけとか、
複利計算ってなんかlogを習ったときにやった気がするけど
なんだっけみたいな気持ちが急に湧いてきましたが、
とりあえず書いてみてサンプルを流し込めば
その辺は拾えそうだなという慢心をしました。
X = int(input()) years = 0 money = 100 while(True) : years += 1 money += int(money * 0.01) if (X <= money) : break print(years)
while文とか普段書かないので、条件間違えてバグらせたくないなという思いで
無限ループ+breakみたいな形にしました。
ここまでで5:22です。
C - Many Requirements
※コンテスト中には解けませんでした
問題文はちょっと小難しい印象。
制約を見ると、N,Mが10以下でQが50以下なので、
全探索か、+αでちょっと工夫すればできるタイプの問題と予想。
コンテスト時の発想は以下の感じでした。
- 各条件に採用/不採用でoxつけたパターン一覧を列挙する。
- それぞれのケースで仮に生成した数列Aのリストを用意する。
- 数列Aのリストができたら、得点を全部計算して最大を取ればよさそう。
これを実装しようとして、採用/不採用列挙しても中には破綻してるやつあるよねとか
そもそもどうやって仮のAを生成していくかみたいなところがわからずに悩んで終了してしまいました。
解法の一つとしては、あり得る数列Aのリストを先に生成して、
それぞれの得点計算をして最大を取れば良いようです。
(解説PDFの仕切りとボールのくだりはピンと来てないので、まだまだ精進が必要なようです……)
ACまで至らないにしても、ここまでは気づきたかったところです。
広義単調増加(あってます?)のリストを生成したかったのですが、
いい感じに書く方法が思いつかなかったので
10重ループにしました。
コンテスト中はそれでいいと思っていますが、
復習するときはこういうのはちゃんとしたいところです。
得点計算のタイミングで数列Aができてればいいので、
10重ループの最奥で得点計算することにしました。
N,M,Q = map(int,input().split()) cond_list = [] for i in range(Q) : cond_list.append(list(map(int,input().split()))) # len(A) < 10でも、10個数えていいはず。 # 条件に出てこないだけ。 max_score = 0 # 開始値を上位ループの値にすれば単調増加にできる for A1 in range(1,M+1) : for A2 in range(A1, M+1) : for A3 in range(A2, M+1) : for A4 in range(A3, M+1) : for A5 in range(A4, M+1) : for A6 in range(A5, M+1) : for A7 in range(A6, M+1) : for A8 in range(A7, M+1) : for A9 in range(A8, M+1) : for A10 in range(A9, M+1) : tmpA = [A1,A2,A3,A4,A5,A6,A7,A8,A9,A10] tmp_score = 0 for a,b,c,d in cond_list : if (tmpA[b-1] - tmpA[a-1] == c) : tmp_score += d if (max_score < tmp_score) : max_score = tmp_score print(max_score)
ヴォエ!!!!!!!!!!!!!!!!!!!!!!!
結果
6104位、パフォ577でレートが+10され495になりました。
Highestが517で、その後406まで落ちてからのこれなのでまあ順調ということにします。
これからもゆるくやっていきます。
Pythonの書き方だれかおしえてください。