ABC260の振り返り(A, B, C, D)

初めて緑パフォが出ました！
という訳で振り返りです。

def test_all(f): for i, data in enumerate(eval(f"test_data{f.__name__[0]}")): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}")

A - A Unique Letter

やってみよう！

A関数を完成させて「Run」ボタンをクリックしよう！
(テストケース省略)

def A(S): pass A("pop") A("abc") A("xxx")

自由欄

try

こんな感じ。for文のelse節はbreakが呼ばれなかった場合のみ実行されます。
(参照：8. 複合文 (compound statement) — Python 3.10.4 ドキュメント)

def A(S): s = set(S) for s in S: if S.count(s) == 1: print(s) break else: print(-1) A("pop") A("abc") A("xxx")

結果：提出 #33294563 - AtCoder Beginner Contest 260

自由欄

B - Better Students Are Needed!

B - Better Students Are Needed\!

やってみよう！

B関数を完成させて「Run」ボタンをクリックしよう！

test_dataB = [ { "in": [6, 1, 0, 2, [80, 60, 80, 60, 70, 70], [40, 20, 50, 90, 90, 80]], "out": """1 4 5""", }, { "in": [5, 2, 1, 2, [0, 100, 0, 100, 0], [0, 0, 100, 100, 0]], "out": """1 2 3 4 5""", }, { "in": [ 15, 4, 3, 2, [30, 65, 20, 95, 100, 45, 70, 85, 20, 35, 95, 50, 40, 15, 85], [0, 25, 45, 35, 65, 70, 80, 90, 40, 55, 20, 20, 45, 75, 100], ], "out": """2 4 5 6 7 8 11 14 15""", }, ] def B(N, X, Y, Z, A, B): pass test_all(B)

自由欄

try

設問に従って素直に実装するとこんな感じ。
特に難しいことはありません。が、結構時間掛かってしまった…

ポイントとしては使用する言語で以下の点を把握していることでしょうか。

keyを指定したソート
安定ソート

参照：ソート HOW TO — Python 3.10.4 ドキュメント

from operator import itemgetter as ig def B(N, X, Y, Z, A, B): ans = [] (*data,) = zip(range(1, N + 1), A, B) # 数学 data.sort(key=ig(1), reverse=True) n, *_ = zip(*data) ans.extend(n[:X]) data = data[X:] # 英語 data.sort(key=ig(0)) data.sort(key=ig(2), reverse=True) n, *_ = zip(*data) ans.extend(n[:Y]) data = data[Y:] # 合計 data = [(n, a + b) for n, a, b in data] data.sort(key=ig(0)) data.sort(key=ig(1), reverse=True) n, *_ = zip(*data) ans.extend(n[:Z]) return "\n".join(map(str, sorted(ans))) test_all(B)

結果：提出 #33305130 - AtCoder Beginner Contest 260

自由欄

pythonのソートについて補足

listのsortメソッドやsorted関数は、"リストのリスト"などで特にkeyを指定せずとも動作します。
では、リスト同士の比較はどのように判断するのかというと、ちゃんとドキュメントに記載されています。

# リスト同士の比較演算子の例 ["aaa"] < ["aaa", 0] < ["aaa", 1] < ["aab", -1]

なので、[[得点, 出席番号]]のようなlistを「得点の昇順、同点の場合は出席番号の昇順」で並べ替えたいときは一発で実現できてしまいます。

data = [[7, 4], [5, 6], [3, 5], [5, 2], [9, 1]] sorted(data)

他の人のコードを見てみる

実行時間もコード長も短い回答を適当にピックアップしました。

下記はeugaltさんの提出を参考。すごいスッキリしてます。
(-得点, 番号)とすることで「得点の降順、同点の場合は番号の昇順」での並べ替えを実現しています。

from operator import add, itemgetter def B(N, X, Y, Z, A, B): def f(points, n): v = sorted((-p, i) for i, p in enumerate(points, 1) if i not in ans) ans.extend(map(itemgetter(1), v[:n])) ans = [] f(A, X) f(B, Y) f(map(add, A, B), Z) return "\n".join(map(str, sorted(ans))) test_all(B)

結果：提出 #33339060 - AtCoder Beginner Contest 260

C - Changing Jewels

やってみよう！

C関数を完成させて「Run」ボタンをクリックしよう！

test_dataC = [ {"in": [2, 3, 4], "out": 12}, {"in": [1, 5, 5], "out": 0}, {"in": [10, 5, 5], "out": 3942349900}, ] def C(N, X, Y): pass test_all(C)

自由欄

try

これも設問通りに実装すればいいだけです。手順が少ない分B問題より簡単ですね。

def C(N, X, Y): r = [0] * 11 b = [0] * 11 r[N] = 1 while sum(r[2:]) > 0: for i in range(10, 1, -1): if r[i]: r[i - 1] += r[i] b[i] = r[i] * X r[i] = 0 for i in range(10, 1, -1): if b[i]: r[i - 1] += b[i] b[i - 1] += b[i] * Y b[i] = 0 return b[1] test_all(C)

結果：提出 #33309558 - AtCoder Beginner Contest 260

try2

上がコンテスト中の提出なんですが、見返すと無駄にループ回してます…

ので以下推敲。

def C(N, X, Y): r = [0] * (N + 1) b = [0] * (N + 1) r[N] = 1 for i in range(N, 1, -1): r[i - 1] += r[i] b[i] += r[i] * X r[i - 1] += b[i] b[i - 1] += b[i] * Y return b[1] test_all(C)

結果：提出 #33339952 - AtCoder Beginner Contest 260

ちゃんと設問を理解すればスッキリしたコードに落とし込める、という好例ですね。

「よく理解してないけどいつか答え出るやろ笑」みたいな手抜きコーディングはやめよう…

自由欄

D - Draw Your Cards

やってみよう！

D関数を完成させて「Run」ボタンをクリックしよう！

test_dataD = [ { "in": [5, 2, [3, 5, 2, 1, 4]], "out": """4 3 3 -1 4""", }, { "in": [5, 1, [1, 2, 3, 4, 5]], "out": """1 2 3 4 5""", }, { "in": [15, 3, [3, 14, 15, 9, 2, 6, 5, 13, 1, 7, 10, 11, 8, 12, 4]], "out": """9 9 9 15 15 6 -1 -1 6 -1 -1 -1 -1 6 15""", }, ] def D(N, K, P): pass test_all(D)

自由欄

try1

この問題も、アルゴリズムというより実装力が求められるかと思います。
以下のコードでWA, TLEとなりコンテスト終了となりました。

恥ずかしいので先に言っておくと、WAの原因は6～9行目のアホみたいな分岐です(後述)。

from bisect import bisect from operator import itemgetter as ig def D(N, K, P): if K == 1: return "\n".join(map(str, P)) if K == N and P == sorted(P): return "\n".join(str(N) * N) ans = [-1] * (N + 1) ba = [] for i, v in enumerate(P, start=1): idx = bisect(list(map(ig(0), ba)), v) if idx == len(ba): ba.append([v]) else: if len(ba[idx]) == K - 1: for c in ba[idx]: ans[c] = i ans[v] = i ba.remove(ba[idx]) else: ba[idx].insert(0, v) return "\n".join(map(str, ans[1:])) test_all(D)

サンプルではpassするが…

結果：提出 #33315198 - AtCoder Beginner Contest 260

try2

WAはとりあえず置いておいて、TLEをなんとかしたいです。

と言っても短いコードで処理も単純なので、怪しいのは15行目の「場に出ているカードの山から一番上に重ねられた数を取り出す」処理でしょう。

map(ig(0), ba)

解説では連想配列(dict)でなんだかんだと言っていて、確かにC++だとスッキリしたコーディングになっていますが、pythonのdictにはC++のmoveのようなメソッドありません。
無理やりdictで実装しようも、削除・追加で順序が崩れて面倒くさそう… (参照)
ていうか解説のpythonの実装例、なんだこれ…

どうしたもんかと他の人の回答(例えば提出 #33328762)を見て目から鱗が落ちました。

場に出てるカードの情報と一番上のカードの情報、別々でいいやん！

という訳で実装したのが以下。(参照した提出とほとんど同じになった…)

from bisect import bisect from operator import itemgetter as ig def D(N, K, P): if K == 1: return "\n".join(map(str, P)) if K == N and P == sorted(P): return "\n".join(str(N) * N) ans = [-1] * (N + 1) ba = [] top = [] for i, v in enumerate(P, start=1): idx = bisect(top, v) if idx == len(ba): ba.append([v]) top.append(v) else: yama = ba[idx] yama.append(v) top[idx] = v if len(yama) == K: for c in yama: ans[c] = i ba.pop(idx) top.pop(idx) return "\n".join(map(str, ans[1:])) test_all(D)

結果：提出 #33331799 - AtCoder Beginner Contest 260

try3

無事TLEが解消されたところでWAを修正します。
前述の通り6～9行目が原因なんですが、もう投げやり感が否めません😩

自力でTLEを解消できなかったので同じ結果とはいえ、C問題の手抜きコーディングに引き続いて「ちゃんとしようね」と諭したくなります。ちゃんとしようね。

一応言語化しておくと、8,9行目は不要です。6,7行目のKが1の場合は、[引いたカードの数]と[ターン数]の組をカードの数で並べ替えて出力する必要があります。

という訳で以下。

from bisect import bisect from operator import itemgetter as ig def D(N, K, P): if K == 1: ans, _ = zip(*sorted(zip(range(1, N + 1), P), key=ig(1))) return "\n".join(map(str, ans)) ans = [-1] * (N + 1) ba = [] top = [] for i, v in enumerate(P, start=1): idx = bisect(top, v) if idx == len(ba): ba.append([v]) top.append(v) else: yama = ba[idx] yama.append(v) top[idx] = v if len(yama) == K: for c in yama: ans[c] = i ba.pop(idx) top.pop(idx) return "\n".join(map(str, ans[1:])) test_all(D)

結果：提出 #33332745 - AtCoder Beginner Contest 260

無事ACとなりました。

なお、if K==1を丸々削除し、25～29行目のif文のインデントを一段上げても同様にACとなります。(むしろこっちのほうがスッキリする)

from bisect import bisect from operator import itemgetter as ig def D(N, K, P): ans = [-1] * (N + 1) ba = [] top = [] for i, v in enumerate(P, start=1): idx = bisect(top, v) if idx == len(ba): yama = [v] ba.append(yama) top.append(v) else: yama = ba[idx] yama.append(v) top[idx] = v if len(yama) == K: for c in yama: ans[c] = i ba.pop(idx) top.pop(idx) return "\n".join(map(str, ans[1:])) test_all(D)

結果：提出 #33332482 - AtCoder Beginner Contest 260

まとめ

ちゃんとしよ。