17
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

posted at

updated at

【AtCoder解説】PythonでABC207のA,B,C問題を制する!

ABC207A,B,C問題を、Python3でなるべく丁寧に解説していきます。

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

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

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

よかったらLGTMしていただけると、私のやる気がでます!

目次

ABC207 まとめ
A問題『Repression』
B問題『Hydrate』
C問題『Many Segments』

アプリ AtCoderFacts を開発しています

コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。

- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス

今後も機能を追加していく予定です。使ってくれると喜びます。

ABC207 まとめ

全提出人数: 8401人

パフォーマンス

パフォ AC 点数 時間 順位(Rated内)
200 AB---- 300 64分 6115(5893)位
400 AB---- 300 20分 4970(4748)位
600 ABC--- 600 94分 4052(3833)位
800 ABC--- 600 60分 3133(2917)位
1000 ABC--- 600 41分 2305(2091)位
1200 ABC--- 600 30分 1631(1425)位
1400 ABC--- 600 21分 1126(925)位
1600 ABC--- 600 13分 752(570)位
1800 ABC-E- 1100 103分 479(328)位
2000 ABC-E- 1100 63分 311(176)位
2200 ABC-E- 1100 35分 211(89)位
2400 ABCDE- 1500 68分 122(43)位

色別の正解率

人数 A B C D E F
3832 98.1 % 65.0 % 27.6 % 0.1 % 0.4 % 0.1 %
1538 99.9 % 94.4 % 73.4 % 0.7 % 1.0 % 0.2 %
1090 99.5 % 97.9 % 90.5 % 2.8 % 3.5 % 0.4 %
712 99.4 % 98.0 % 95.7 % 11.2 % 18.1 % 1.4 %
308 99.7 % 98.7 % 98.4 % 17.5 % 52.9 % 6.8 %
171 94.7 % 94.2 % 93.0 % 39.2 % 59.1 % 24.0 %
41 97.6 % 97.6 % 97.6 % 73.2 % 85.4 % 68.3 %
14 100.0 % 100.0 % 100.0 % 78.6 % 92.9 % 85.7 %

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

私(うにだよ)の結果

screenshot.54.png

B問題に時間をかけすぎました。

A問題『Repression』

問題ページA - Repression
コーダー正解率:98.1 %
コーダー正解率:99.9 %
コーダー正解率:99.5 %

実装

3通りの選び方の最大値を出力するコード

2枚のカードの選び方は、$A+B$, $B+C$, $C+A$ の 3通りあります。これらの最大値を出力すればいいです。

3枚の合計から最小値を引くコード

3枚のうちいらないカードは、一番小さい数字が書いてあるカードです。

つまり、$A + B + C$ から、$A,\,B,\,C$ の最小値を引けば答えになります。

リストで受け取ってソートするコード

入力をリストLとして受け取ってソートします。それから L[1] + L[2]を出力すればいいです。

コード

3通りの選び方の最大値を出力するコード

def main():
    A, B, C = map(int, input().split())
    print(max(A + B, B + C, C + A))


if __name__ == '__main__':
    main()

3枚の合計から最小値を引くコード

def main():
    A, B, C = map(int, input().split())
    S = A + B + C
    print(S - min(A, B, C))


if __name__ == '__main__':
    main()

リストで受け取ってソートするコード

def main():
    L = map(int, input().split())
    L.sort() # 小さい順にソートされるので、L[1] と L[2] が必要なカードです
    print(L[1] + L[2])


if __name__ == '__main__':
    main()

B問題『Hydrate』

問題ページB - Hydrate
コーダー正解率:65.0 %
コーダー正解率:94.4 %
コーダー正解率:97.9 %

問題の意味

考察

forループで全探索する場合

「ABCのB問題で、制約も$A,B,C,D\le{10^5}$ とそれほど大きくないので、もしも目標が達成可能であるとすれば、それほど操作回数は大きくならないだろう」と予想をして、forループでTLEにならない程度にできる限り多くの回数シミュレーションします。条件を満たした瞬間ループを打ち切って答えを出力ます。forループを抜けるまで見つからなければ達成不可能と考えて-1を出力します。

実際、この方法でACを取ることができます。

公式解説に、目標が達成可能な場合必要な操作回数の最小値は $A$ 以下になることが示されています。

不等式を立てて解く場合

$x$ 回 操作を行ったとき、各色のボールの数は以下の式で表されます。

水色のボールの数:$A + Bx$ 個
赤色のボールの数:$Cx$ 個

「『水色のボールの個数』が『赤色のボールの個数』の $D$ 倍以下になる」を不等式で表すと、以下の式になります。

$A + Bx\le{D}\times{Cx}$

この式を式変形します。

$A\le{D\times{Cx}} - Bx$
$A\le{(D\times{C} - B)x}$

ここで制約より、$A\ge{1}$ 、操作回数 $x\ge{0}$ であることを考えると、$D\times{C} - B\le{0}$ の場合、この不等式は解を持ちません。つまり、目標を達成することは不可能ですから、-1 を出力して終了します。

そうでない場合、すなわち $D\times{C} - B\gt{0}$ で解がある場合を考えます。両辺を $D\times{C} - B$ で割ります。(負や $0$ にはなりませんから、不等式を負の値で割るときに不等号を反転させたり、$0$ 除算のことを考える必要はありません)

$\frac{A}{D\times{C}-B}\le{x}$

この不等式を満たす、最小の非負整数 $x$ は、$A$ を $D\times{C} - B$ で割って、小数点以下を切り上げた値になります。天井関数を使って書くと、$\lceil{\frac{A}{D\times{C}-B}}\rceil$です。

コード

forループで解く場合

ループ回数を1000万回に設定すると、Python 3.8.2で1440ms、PyPy3 (7.3.0)で85msでACできます。

def main():
    def solve():
        Const = 10 ** 7 + 5  # TLEにならない程度に、できる限り大きな値にします
        for x in range(Const):
            cyan = A + B * x
            red = C * x
            if cyan <= D * red:
                return x
        return -1  # 解が見つかりませんでした

    A, B, C, D = map(int, input().split())

    print(solve())


if __name__ == '__main__':
    main()

不等式を立てて解く場合

def main():
    def solve():
        t = C * D - B
        if t <= 0:
            # 不可能な場合です
            return -1
        return - (-A // t)  # Pythonでは、こう書くと切り上げができます

    A, B, C, D = map(int, input().split())

    print(solve())


if __name__ == '__main__':
    main()

C問題『Many Segments』

問題ページC - Many Segments
コーダー正解率:27.6 %
コーダー正解率:73.4 %
コーダー正解率:90.5 %

考察

全探索する

制約が$N\le{2000}$ と小さいので、二重ループで $i\lt{j}$ である $(i,j)$ の組を全探索し、共通部分を持つ組の数を数えあげることを考えます。($N=2000$ のとき、$(i,j)$ の組は $\frac{2000\times{(2000 - 1)}}{2} = 1,999,000$ 組しかありません。)

閉区間・開区間の扱い

閉区間・開区間の説明は、親切にも問題文の折りたたみ部分に書いてあります。 それを読むとわかりやすいです。

さて、入力がすべて整数であることに着目すると、開区間をすべて閉区間に置き換えることができます。

具体的には、以下のように置き換えれば良いです。

$[l, r]$ を $[l,r]$
$[l,r)$ を $[l,r-0.5]$
$(l,r]$ を $[l+0.5, r]$
$(l,r)$ を $[l + 0.5, r-0.5]$

共通部分を持つかの判定:反対を考えよう

『共通部分を持つか?』を直接判定するのは面倒です。しかし、反対の『共通部分を持たないか?』を判定するのは比較的容易です。

閉区間 $[A,B]$ と、閉区間 $[C,D]$ が共通部分を持たないのは以下の2パターンあります。(画像参照、$[A,B]$ を固定して考えてみましょう)

  1. 閉区間$[A,B]$ の右端 $B$ よりも、閉区間 $[C,D]$ の左端 $C$ が右側にある
  2. 閉区間$[A,B]$ の左端 $A$ よりも、閉区間 $[C,D]$ の右端 $D$ が左側にある

abl_b.png

条件式で表すと

$B<C$ または $D<A$

となります。この条件式をnotで反転すれば、『共通部分を持つか?』を判定できます。

実装

コードを読んだほうが詳細な実装を理解しやすいと思うので、簡単な流れだけを説明します。

  1. 入力を受けとる際に、開区間を閉区間に変換する**
  2. 二重ループで、すべての$(i,j)$の組を全探索する
  3. 関数judge(a, b, c, d)で、共通区間を持つか判定する

コード

def main():
    def func(t, l, r):
        """
        開区間を閉区間に変換します
        """
        if t == 1:
            # [l, r]
            return l, r
        if t == 2:
            # [l, r)
            return l, r - 0.5
        if t == 3:
            # (l, r]
            return l + 0.5, r
        if t == 4:
            # (l, r)
            return l + 0.5, r - 0.5

    def judge(a, b, c, d):
        b1 = b < c
        b2 = d < a
        if not (b1 or b2):
            # 共通区間がある
            return 1
        else:
            # 共通区間がない
            return 0

    N = int(input())
    L = [-1] * N
    R = [-1] * N

    for i in range(N):
        t, l, r = map(int, input().split())
        l, r = func(t, l, r)  # tに応じて、与えられた区間を閉区間に変換します
        L[i], R[i] = l, r

    ans = 0
    for i in range(N):
        a, b = L[i], R[i]
        for j in range(i + 1, N):
            c, d = L[j], R[j]
            ans += judge(a, b, c, d)

    print(ans)


if __name__ == '__main__':
    main()
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
17
Help us understand the problem. What are the problem?