mery's Notes

めりーがプログラミングしたりします。

MENU

AtCoder Beginner Contest (ABC) 229 Pythonで参戦しました。 A,B,C問題解説あり。

前回のやつ

mery-kirokudayo.hateblo.jp

f:id:mery_poke:20211128121229p:plain

こんにちは。メリーです。

最近はFPSやらずにマーダーミステリーや、ボードゲームアリーナで楽しく遊んでます。
マダミス面白いですね。逆転裁判とかダンガンロンパっぽくて好きです。

あと、最近Steamでオータムセールやってますね。
steins;gateがセールしてるので買っちゃいました。
2作合わせて2,000円ちょっとだったので、めっちゃお得でした。

そんなわけで、NECプログラミングコンテスト2021 (ABC 229)参戦しました!!
結果はABC三完で、パフォーマンス610でした!!もうちょっとで茶色いけそう!!
というわけで、A、B、C問題の解説もしていきます。

言語はPython、提出はPyPyです。

目次

A問題 First Grid

First Grid

問題文

A - 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

問題文

B - 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

問題文

C - 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)となります

そして、各ループの最後で重さが限界値を超えてないかチェックします。
こえてたら終わりです。

最後においしさを出力して終了です。

この調子で茶色コーダーまで駆け抜けたいと思います!!!

それでは!