AtCoder Beginner Contest (ABC) 229 Pythonで参戦しました。 A,B,C問題解説あり。
前回のやつ
こんにちは。メリーです。
最近はFPSやらずにマーダーミステリーや、ボードゲームアリーナで楽しく遊んでます。
マダミス面白いですね。逆転裁判とかダンガンロンパっぽくて好きです。
あと、最近Steamでオータムセールやってますね。
steins;gateがセールしてるので買っちゃいました。
2作合わせて2,000円ちょっとだったので、めっちゃお得でした。
そんなわけで、NECプログラミングコンテスト2021 (ABC 229)参戦しました!!
結果はABC三完で、パフォーマンス610でした!!もうちょっとで茶色いけそう!!
というわけで、A、B、C問題の解説もしていきます。
言語はPython、提出はPyPyです。
目次
A問題 First Grid
First Grid
問題文
2×2の空間が与えられます。この空間の各マスは黒か白です。
2つの異なる黒マスが隣接している場合、直接行き来できます。
全ての黒マス同士が行き来できるかどうかを判別してください。
という問題です。
この問題で具体的に当てはめて考えてみると、黒マスが3つ以上の場合は行き来できます。
※黒マスが3つの場合、2つの黒マスに隣接している黒マスが存在するので、それ経由ですべての黒マスに行ける。
で、問題は黒マスが2つの場合です。
黒マスが2つでなおかつ、黒マスが対角線上にある場合のみ行き来できません。
※2つの黒マスに隣接しているマスが全て白なので、移動ができません。
というわけで方針は、
1. 入力
2. 黒マスの合計を数える
3. 黒マスが2つでかつ対角線上にある場合は「No」を出力。
4. それ以外の場合は「Yes」を出力。
という感じです。
コード ↓
s1 = input() s2 = input() sha = 0 for i in range(2): if s1[i] == "#": sha += 1 if s2[i] == "#": sha += 1 if s1[0] == "#" and s2[1] == "#" and sha == 2: print("No") elif s1[1] == "#" and s2[0] == "#" and sha == 2: print("No") else: print("Yes")
解説してきます。
for i in range(2): if s1[i] == "#": sha += 1 if s2[i] == "#": sha += 1
この部分では、シャープの数を数えています。
s1[i],s2[i]
をチェックして、「#」であればsha
を増やします。
if s1[0] == "#" and s2[1] == "#" and sha == 2: print("No") elif s1[1] == "#" and s2[0] == "#" and sha == 2: print("No") else: print("Yes")
この部分では、対角線上にあるか否かのチェックをしています。
対角線上にある場合は、
黒白 白黒 白黒 黒白
の2通りです。
この2通りの場合は「No」を、それ以外は「Yes」を出力して終わりです。
B問題 Hard Calculation
Hard Calculation
問題文
整数A、Bが与えられます。
A+Bを計算する時、繰上りが発生するなら「Hard」それ以外なら「Easy」を出力せよ。
という問題。
繰上りが発生しない = 全てのiにおいて、Aのi桁目とBのi桁目を足した場合に9を超えない
ということです。
なので、愚直に各桁を足していって、10以上になったら打ち切って「Hard」を、
全ての桁で10以上にならなかったら「Easy」を出力して終わりです。
というわけで、まとめた方針を。
1. 入力
2. 入力を逆順にする。
3. 各桁を足していき、10以上になったら打ち切る。
4. 打ち切った場合は「Hard」、それ以外は「Easy」を出力。
コード ↓
a,b = input().split() a = a[::-1] b = b[::-1] for i in range(min(len(a),len(b))): if int(a[i]) + int(b[i]) >= 10: print("Hard") break else: print("Easy")
解説してきます。
a = a[::-1] b = b[::-1]
この部分で、入力したものを逆順にしています。
例 a = 123 a[::-1] = 321
こうすることで、のちのfor文でreverse
を使わなくてよくなるので、コードが見やすくなります。
for i in range(min(len(a),len(b))): if int(a[i]) + int(b[i]) >= 10: print("Hard") break else: print("Easy")
この部分で、各桁の繰り上げチェックをしています。
range
の上限がmin(len(a),len(b))
なのは、a,bで桁が違う場合に備えてです。
桁が違う場合は短い方に合わせれば十分なので。
この部分の前で、入力したa,bを逆順にしたので、一の位から順番にチェックできるようになってます。
逆順にしなかった場合、 a = 1234 b = 345 a[0] = 1, b[0] = 3 一番左の数字が足されてしまう。
そして、
ループが正常に終わる = break
されない
場合、else
が実行されます。
C問題 Cheese
Cheese
問題文
N種類のチーズがあります。
i番目のチーズのおいしさはAiでBiグラムあります。
乗せられるチーズの重さの限界はWです。
実現可能な範囲で、おいしさの最大値はいくつですか。
という問題。
この問題の肝は、一番おいしいものを多く乗せるとおいしくなる、ということです。
なので、おいしい順にチーズを限界まで載せていけばよいのです。
方針
1. 入力
2. おいしい順にソート
3. おいしい順に限界までチーズをのせていき、おいしさを足していく。
4. 足したおいしさを出力して終了。
コード ↓
n,w = map(int,input().split()) cheese = [] for _ in range(n): a,b = map(int,input().split()) cheese.append([a,b]) cheese.sort(reverse=True) ans = 0 omosa = 0 for i in range(n): if cheese[i][1] + omosa <= w: ans += cheese[i][0] * cheese[i][1] omosa += cheese[i][1] else: ans += (w - omosa)*cheese[i][0] omosa += (w - omosa) if omosa >= w: break print(ans)
解説してきます。
cheese.sort(reverse=True)
で、大きい順にソートしてます。これで、おいしい順にソートできました。
for i in range(n): if cheese[i][1] + omosa <= w: ans += cheese[i][0] * cheese[i][1] omosa += cheese[i][1] else: ans += (w - omosa)*cheese[i][0] omosa += (w - omosa) if omosa >= w: break print(ans)
ここが根幹部分です。
ソートした順に、最大限チーズをのせていきます。
i番目のチーズを全部のせられる場合と、一部分だけのせられる場合があります。
全部のせられる場合は、cheese[i][1] + omosa <= w
の場合です。
omosa
はこれまでのせたチーズの重さの合計です。
この場合は、チーズのおいしさ×重さをans
に足して、omosa
にチーズの重さ(cheese[i][1]
)を足します。
一部分だけのせられる場合は、cheese[i][1] + omosa > w
の場合です。
全部のせられないので、限界までのせます。
のせれるチーズの限界の重さは(w - omosa)
で表せます。
なので、おいしさは、(w - omosa)*cheese[i][0]
となり、重さは(w - omosa)
となります。
そして、各ループの最後で重さが限界値を超えてないかチェックします。
こえてたら終わりです。
最後においしさを出力して終了です。
この調子で茶色コーダーまで駆け抜けたいと思います!!!
それでは!