TIL blog

技術ネタ, その他学んだことのアウトプット用

Atcoder Beginers Contest 123 の解法ふりかえり

競プロ atcoder python

最近 アルゴリズムとデータ構造 の重要性を業務で意識させられることがあって, ちょこちょこ Atcoder Beginners Contestの過去問を解いている。
生のコンテストも出たいなと思いつつ時間がなかなか合わなかったのだが, 今回はタイミングあったので出場した。

atcoder.jp

結果

利用言語は Python3
A, B, C は解けた, Dはゴリ押し解法でサンプル一個目だけ通せたが時間制限に間に合わず。。。 以下, それぞれの問題について振り返ったあと, 全体の感想述べていく。

問題振り返り

A

考えたこと

  • 入力の時点で sort されているので, 最大の差分は 先頭の要素と末尾の要素の差分
  • 直接回答書き始めたら for の後の : 書きそこねてて RE くらった. 最低限の local debug はしましょう...

  • 最近 Python 以外書くことが多かったから, 3項演算子 の書き方忘れててググった, ドキュメントの該当箇所は以下

  • 最初は 配列初期化 + append で入力作っていたが, 内包表記 で書ける

解説での学び

  • Aは想定通りだったので, 特になかった

AC 回答

  • before
a = []

for i in range(5):
    a.append(int(input()))

f = a[-1] - a[0] <= int(input())

print("Yay!" if f else ":(")
  • after
a = [int(input()) for i in range(5)]
d = a[-1] - a[0] <= int(input())
print("Yay!" if d else ":(")

B

考えたこと

  • Bは 全探索 で間に合うパターンが多いのは過去問見てて思ってたいので最初考えたが, 下一桁が0以外のもので最小のものを探せば良いことに気づいた。
  • 下一桁が0以外のもので最小のものを探す 関数を map, filter 使って作ったが, テストケースで最後のものだけ RE
  • RE の原因気づくのに時間がかかったが, すべての入力の下一桁が 0のとき min([]) するような関数を作っていたからだった。
  • python の map or filterで 無名関数 使いたいとき lambda の文字列タイプするのはやや面倒
RE回答
a = []

for i in range(5):
    a.append(int(input()))


def ceil10(n):
    if n % 10 == 0:
        return n
    else:
        return ((n // 10) + 1) * 10


def min_1(a):
    a2 = list(filter(lambda a: a > 0, (map(lambda e: e % 10, a))))

    return min(a2)


ans = sum(map(ceil10, a)) - 10 + min_1(a)
print(ans)

解説での学び

  • 切り上げの実装は, 下一桁が0 のケースで場合分けする方法もあるが, 9を足して ((n + 9) // 10) * 10 のようにする方法もある。
  • わざわざmap, filter使わなくても, loopで書けるしその方が読みやすい(解説がC++だからというのはあるかもしれない)

AC 回答

  • before
a = []

for i in range(5):
    a.append(int(input()))


def ceil10(n):
    if n % 10 == 0:
        return n
    else:
        return ((n // 10) + 1) * 10


def min_1(a):
    a2 = list(filter(lambda a: a > 0, list(map(lambda e: e % 10, a))))

    if len(a2) == 0:
        return 10

    return min(a2)


ans = sum(map(ceil10, a)) - 10 + min_1(a)
print(ans)
  • after
a = [int(input()) for i in range(5)]

def ceil10(n):
    return ((n + 9) // 10) * 10

ans = 999 # > 123 * 5

for i in range(5):
    t = 0

    for j in range(5):
        if j == i:
            t += a[j]
        else:
            t += ceil10(a[j])
    ans = min(ans, t)

print(ans)

C

考えたこと

解説での学び

AC 回答

n = int(input())
a = [int(input()) for i in range(5)]

ans = n // min(a) + 4 + (1 if n % min(a) != 0 else 0)
print(ans)

D

考えたこと

  • 愚直な 全探索 は (10 ** 10) ** 3 なので間に合わない
  • 出力が大きい順なので, 入力は sort desc しておいたほうが効率が良い.
    • 10 ** 10 の sort の O(NlogN) はセーフ
  • 出力はuniqueなので, 今まで計算した値は cache しておきたい
  • 和を考えるため, 各配列の最大の要素を比較して, 最大のものから取り出して行けば大きい順に出力が構成される
  • それぞれの値は A なら Y * Z 回使われる, B,Cについても循環的に考えて同様, 利用回数も cache

=== この辺りでコンテスト終了

解説での学び

  • 回答を見て, 出力の制限 (K<3000) にも着目するべきだった点に気づいた.
  • 回答には4種類の解法があったが, まだ解法1しか見ていないので後ほど それぞれ 確認, 実装する予定

AC回答

解法#1 O(k2 log k) 制限2000ms に対して max 1945ms かかっていたのでギリギリ

from itertools import product

x, y, z, k = list(map(int, input().split()))
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ab = [ai + bi for (ai, bi) in product(a[:k], b[:k])]
ab.sort(reverse=True)
abc = [abi + ci for (abi, ci) in product(ab[: min(k, x * y * z)], c[:k])]
abc.sort(reverse=True)

for abci in abc[: min(k, x * y * z)]:
    print(abci)

他の人の回答を見て

  • コード長が短いコード を見て, パット見でに気になったものは以下

  • c_r_5 さんの回答 より

a,*_,e,k=eval('int(input()),'*6);print(':('*(e-a>k)or'Yay!')
  • eval で 文字列として 'int(input())' と 書ける
  • if-else ではなくて or で表現できる

終了後の雑多な感想

  • 参加者 が過去最大規模(約4000人!) だったらしく, コンテスト開始直後アクセスちょっと重かった
  • 最近資格試験など受けたりもしていないので, 時間制約付きで問題を解く機会がなかなかなかったので楽しかった
  • 入力だけでなく, 出力の制約 にも着目して解法考えるの大事

  • Python が比較的慣れているから, 書きやすいが map, filter辺り使い始めると method chaining ないのが辛い。この辺り書きやすい言語は模索してみる。 script 言語で時間問題なさそうなら Rubyとかかな? Dで時間, メモリ的にだめなら Julia, Kotlin あたりが候補

  • 以下のpodcast で聞いてデバッガちゃんと使おうという気持ちになったので, pdb をちゃんと使ってみた。今まで IDE debuggerに慣れてたけどこれは便利。 anchor.fm

  • GCJ は出そびれたのでまた来年...

  • データ構造については, Open Data Structure の邦訳がありがたいことに無料公開されているので, そちらで勉強中
    • 一人でやるとダレそうなので, お互い進捗報告しあうやつやりたい

sites.google.com