EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC200をpythonで問題を解いてみた

Atcoder 競技プログラミング

目的

  • Atcoderで上を目指すべく頑張っている中でABC200を解いたので、解説してみる
    • pypy7.3を使って解いている

A問題

atcoder.jp

考察

  • Nが100で割り切れる場合とそうでない場合がポイントになりそう
    • 100で割り切れる場合は、そのまま出力する
    • そうでない場合は、100で切り捨て除算した値に1を足す
      • ex. N=2021 の場合、20になるが、実際は21世紀なので1を足す

実装

N = int(input())

if N % 100 == 0:
    print(N//100)
else:
    print(N//100+1)

結果

B問題

atcoder.jp

考察

  • K<=20 なので問題文通りに実装し、全探索すれば良さそう
    • pythonの場合、文字列200を後ろに付け加える部分は、一時的にstrで計算したのちに、intに直せばよさそう

実装

N, K = map(int, input().split())

for _ in range(K):
    if N % 200 == 0:
        N = N//200
    else:
        N = int(str(N) + "200")

print(N)

結果

C問題

atcoder.jp

考察

  • N<=2*105 なので、全ての組みを探索するとTLE(実行時間超え)になりそう
    • i, j に対して2重ループ書くことになり、計算量が 1010 程度になるため
  • 入力例を見て行ったときに、200で割った余りが同じもの同士を用いて、組み合わせを用いることで、数え上げられそうと気づく
    • ex1. 123, 223, 123, 523, 200, 2000
      • 200で割った余りはそれぞれ、 123, 23, 123, 123, 0, 0
      • 同じ余りのグループを作ると、(1, 3, 4) (5, 6) という集合ができる
      • 上記グループよりそれぞれ2つ取り出す組み合わせが答えになる
        • (1 ,3), (1, 4), (3, 4), (5, 6) が答えになる
      • 今回は具体の組み合わせは不要で、何通りあるか出せば良いので 3C2+2C2 = 4 となる
  • 200の余りが0~199になるため、配列を用意し、与えられる数列Aの要素の余りを計算し、特定の余りを持つ要素の数を数え上げ、組み合わせを用いてそれぞれ足し合わせていけばよさそう

実装

import math

N = int(input())
A = list(map(int, input().split()))

q = [0] * 200
ans = 0


def comb(n, r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))


for a in A:
    idx = a % 200
    q[idx] += 1

for i in q:
    if i >= 2:
        ans += comb(i, 2)

print(ans)

結果

D問題

atcoder.jp

方針を誤り、時間内に解くことができなかった

考察

  • N<=200 のため、全ての場合の和を数え上げることも、bit探索で数え上げることも、時間内には不可能

    • そのため、最初は累積和を求めて、累積和同士の差分を求めることで数え上げようとした
      • この場合 20000回程度の計算量に収まり、解くことができると考えた
    • ただ、この場合は連続した数列部分のみを探索することになり、例えば 1, 2, 5 と並ぶような数列はこのパターンから外れるため、答えとして No が必要以上に出てしまうことになる
    • ここから方針転換し、どうやって解こうと思って考えてて時間切れしてしまった・・・

  • 今回は「鳩の巣原理」を用いて考えればよかったそう(解説を見て理解したw)

鳩ノ巣原理：
n, mを自然数 n > mとする
n個のものをm組にわけるとき、少なくともひとつの組は2個以上のものを含む

www.mathlion.jp

  • 今回の問題に当てはめて利用する場合は、「200で割った余りは、200通りなので、201通り以上の範囲を調べれば少なくとも1つの組は2個以上含むことになり、B, Cが見つかることになる。」となる

    • 28=256 なので、bit探索で与えられた数列の頭8番目までの要素を全探索することで1組見つけることができる
      • 最悪のケースは頭8個の数列の部分数列の総和は、全て違う値になることだが、201通り以上探せば同じものは見つかる
      • 数列内に同じ数字がある場合は、総和が同じになり普通に同じ余りになる数列が見つかる

  • 存在する場合はひとつ出力してください = 「少なくとも1つ以上存在する」のため、全部を丁寧に探す必要はないと言うヒントのため、見逃さないようにしたい

    • 1つでも見つかればいいので、探索する範囲を適切に制限することで解ける！場合が多そう(もちろん、効率よく全探索する場合もあるのだろうが)

実装

N = int(input())
n = min(N, 8)
A = list(map(int, input().split()))[0:n]
q_list = [[] for _ in range(200)]


def solve():
    for i in range(1, 2 ** n):
        bit = bin(i)[2:].rjust(n, "0")
        s, l = 0, []
        for i, b in enumerate(list(bit)):
            if b != "1":
                continue
            s += A[i]
            l.append(i+1)
        idx = s % 200
        q_list[idx].append(l)
        if len(q_list[idx]) >= 2:
            return idx
    return None


ans = solve()
if ans is None:
    print("No")
else:
    print("Yes")
    x, y = q_list[ans][1], q_list[ans][0]
    print(*([len(x)]+x))
    print(*([len(y)]+y))

結果

振り返り

  • A, B ,C をもっと安定し解けるようになり、かつ20分以内に解けるようになりたい
  • 今回のD問題のように、「あとちょっとでAC」になった際にDebugしてしっかり解き切れるようになるための力をつけたい
    • 下記とかが参考になりそう

qiita.com

  • E問題はDPで、DP勉強してといてみるのもアリだが、当分はA, B, Cの早解をしてrateをあげるのが良さそう