LoginSignup
4
0

More than 3 years have passed since last update.

@u2dayo

【AtCoder解説】PythonでABC181のA,B,C,D問題を制する！

Last updated at Posted at 2020-11-01

AtCoder Beginner Contest 181のA,B,C,D問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

  • シンプル：余計なことを考えずに済む
  • 実装が楽：ミスやバグが減ってうれしい
  • 時間がかからない：パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントかツイッターまでどうぞ
Twitter: u2dayo

目次

ABC181 まとめ
A問題『Heavy Rotation』
B問題『Trapezoid Sum』
C問題『Collinearity』
D問題『Hachi』

ABC181 まとめ

全提出人数: 6643人

パフォーマンス

パフォ AC 点数 時間 順位(Rated内)
200 AB---- 300 20分 5056(4953)位
400 ABC--- 600 77分 4179(4077)位
600 ABC--- 600 28分 3435(3333)位
800 ABCD-- 1000 95分 2647(2549)位
1000 ABCD-- 1000 60分 1918(1822)位
1200 ABC-E- 1100 87分 1324(1230)位
1400 ABCDE- 1500 83分 873(789)位
1600 ABCDE- 1500 61分 558(476)位
1800 ABCDE- 1500 44分 345(269)位
2000 ABCDEF 2100 103分 197(139)位
2200 ABCDEF 2100 72分 104(66)位
2400 ABCDEF 2100 56分 52(30)位

色別の正解率

色 人数 A B C D E F
灰 2714 99.0 % 84.1 % 43.0 % 18.0 % 1.4 % 0.1 %
茶 1228 99.8 % 99.7 % 85.8 % 61.5 % 4.2 % 0.1 %
緑 972 99.7 % 99.7 % 96.2 % 87.7 % 37.4 % 0.4 %
水 574 99.8 % 99.8 % 98.6 % 95.1 % 86.6 % 7.0 %
青 291 99.7 % 99.7 % 100.0 % 98.6 % 98.3 % 38.5 %
黄 78 97.4 % 97.4 % 98.7 % 98.7 % 88.5 % 55.1 %
橙 22 95.5 % 95.5 % 100.0 % 100.0 % 95.5 % 81.8 %
赤 3 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 100.0 %

※表示レート、灰に初参加者は含めず

簡易解説


A問題 (6568人AC)『Heavy Rotation』

日数が偶数・奇数のどちらなのかで答えが決まります。

B問題 (5936人AC)『Trapezoid Sum』

$A$～$B$まで素直に足す方法は間に合いません。
等差数列であることを利用して、各範囲の和を数式で求めていけばいいです。

C問題 (4329人AC)『Collinearity』

$3$ 重ループですべての点の組み合わせについて判定します。判定の式は高校数学です。私はググりました。

D問題 (3152人AC)『Hachi』

「ある整数が8の倍数」⇔「ある整数の下3桁が8の倍数である」です。
すべてのありうる下3桁候補を作れるか試してみて、どれか1つでも作れればOKです。

E問題 (1344人AC)『Transformable Teacher』[この記事では解説しません]

先生の身長を固定して、生徒に加えた身長の数列を、昇順にソートします。
このとき、$(1, 2), (3, 4), (5, 6), ...$　のように、隣合った人とペアを組むのが最適になります。
全ての先生の身長候補について、二分探索で先生が何番目に入るか求めます。
そのときの差の総和を累積和を使って効率的に計算すれば、解けます。

F問題 (230人AC)『Silver Woods』[この記事では解説しません]

あらかじめ「ある点と上の直線までの距離」「ある点と下の直線までの距離」「2点間の距離」をすべて求めます。
UnionFindを使って、距離が短い順に成分を連結していきます。
上の直線と下の直線が同じ連結成分になったときの距離が答えになります。

私（うにだよ）の結果（参考）

screenshot.308.png

C問題とD問題はググりました。E問題の実装が下手だったっせいでやや手こずりましたが、総合的にはまずまずの結果でした。

A問題『Heavy Rotation』

問題ページ：A - Heavy Rotation
灰コーダー正解率：99.0 %
茶コーダー正解率：99.8 %
緑コーダー正解率：99.7 %

考察

$N$ が奇数なら"Black"で、偶数なら"White"です。$N$ を $2$ で割った余りが $0$ なら偶数で、 $1$ なら奇数です。

コード

N = int(input())

if N % 2 == 1:
    print("Black")
else:
    print("White")

B問題『Trapezoid Sum』

問題ページ：B - Trapezoid Sum
灰コーダー正解率：84.1 %
茶コーダー正解率：99.7 %
緑コーダー正解率：99.7 %

考察

下のコードのように、素直に $A$ から $B$ までの整数を足していく方法ではTLEになります。

N = int(input())

ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    for x in range(a, b + 1):
        ans += x

print(ans)

間に合わせるためには、各範囲の総和を数式で一発で求める必要があります。

数式で求める方法は $2$ つほどありますが、どちらも似たようなものです。

  • $（1 から B までの整数の総和) - (1 から A - 1 までの整数の総和)$ で求める
  • 初項 $A$ 項数 $B-A+1$, 公差 $1$ の等差数列の和の公式 を使う

今回は単純な前者のほうで解説します。

1～xまでの総和の求め方

$S =（1から x までの総和）$は、下の式で求められます。この式は、必ず割り切れて整数になります。

S = \frac{x{(x+1)}}{2}

コードにすると、次のようになります。小数点以下を切り捨てる // （整数除算）を使うことに注意してください。

s = x * (x + 1) // 2

この公式は競プロで非常によく使われます。もし覚えていなかった方は、この機会に覚えておくと必ず役に立ちます。

コード

def calc(x):
# 1からxまでの総和を返す関数
    return x * (x + 1) // 2


N = int(input())

ans = 0

for _ in range(N):
    a, b = map(int, input().split())
    ans += (calc(b) - calc(a - 1))

print(ans)

C問題『Collinearity』

問題ページ：C - Collinearity
灰コーダー正解率：43.0 %
茶コーダー正解率：85.8 %
緑コーダー正解率：96.2 %

考察

点の数は最大で $10^2 = 100$ 個なので、すべての3点の組み合わせについて同一直線上にあるか、$3$ 重ループを使って判定しても間に合います。

$3$ 点が同一直線上にある条件は、以下の等式が成り立つことです。（詳しくは公式解説とGoogle検索におまかせします）

(x_2-x_1)(y_3-y_1) = (x_3-x_1)(y_2-y_1)

コード

def judge():
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                x1, y1 = P[i]
                x2, y2 = P[j]
                x3, y3 = P[k]
                fx, fy = x2 - x1, y2 - y1
                sx, sy = x3 - x1, y3 - y1
                if fx * sy == sx * fy:
                    return True
    return False


N = int(input())
P = []

for _ in range(N):
    x, y = map(int, input().split())
    P.append((x, y))

if judge():
    print("Yes")
else:
    print("No")

D問題『Hachi』

問題ページ：D - Hachi
灰コーダー正解率：18.0 %
茶コーダー正解率：61.5 %
緑コーダー正解率：87.7 %

考察

Sが1桁か2桁の場合

$1$ 桁の場合、並び替えはできないので、そのまま $8$ で割り切れるか判定すればいいです。

$2$ 桁の場合、「そのまま使う」か「ひっくり返す」$2$ パターン、 $8$ で割り切れるか判定すればいいです。

Sが3桁以上の場合

「ある整数が8の倍数」⇔「ある整数の下3桁が8の倍数」です。詳しい説明は他のところに譲りますが、$1000$ が $8$ の倍数であることが理由です。

つまり、$S$ を自由に並び替えて、下 $3$ 桁さえ $8$ の倍数にできれば、$8$ の倍数にできます。

$3$ 桁の $8$ の倍数は $100$ 個強しかありません。よって、「全ての $3$ 桁の $8$ の倍数について、作れるか判定する」ことで解けます。

判定法

例えば下3桁を $112$ にしたい場合、$S$ に $1$ が $2$ 個以上、$2$ が $1$ 個以上あれば作れます。

この判定をするために、あらかじめ$S$ に $1$ ～ $9$ が何個含まれているか数えておけばいいです。

実装

数えるときはCounter

数えるときは、collectionsモジュールのCounterを使うと楽です。

>>> from collections import Counter
>>> S = "181"
>>> cnt_first = Counter(S)
>>> cnt_first
Counter({'1': 2, '8': 1})  # '1'が2個、'8'が1個あります

3桁の8の倍数の作り方

for x in range(104,1000,8):
    # 処理

rangeの引数を次のように指定します。

始点: $3$ 桁の $8$ の倍数で一番小さい $104$
終点: $1000$ (未満)
ステップ: $+8$ ずつ

これで、$104, 112, 120, ..., 984, 992$ と全列挙できます。

コード

from collections import Counter


def judge():
    if len(S) == 1:
        if int(S) % 8 == 0:
            return True
    elif len(S) == 2:
        if int(S) % 8 == 0 or int(S[::-1]) % 8 == 0:
            return True
    else:
        for x in range(104, 1000, 8):
            cnt_current = Counter(str(x))
            ok = True
            for key, val in cnt_current.items():
                if val > cnt_original[key]:
                    ok = False
            if ok:
                return True
    return False


S = input()
cnt_original = Counter(S)  # 1～9の各文字が、Sにいくつ入っているかわかります

if judge():
    print("Yes")
else:
    print("No")

余談

公式解説のほうがCounterの使い方がスマートです。この方法でやってもいいと思います。

Counter同士で引き算して、もし空になれば作れる、ということをしています。

4
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
0