AtCoder Beginner Contest 343 - あるぱかのブログ

A - Wrong Answer
B - Adjacency Matrix
C - 343
D - Diversity of Scores
結果

A - Wrong Answer

概要：0～9の整数のうち $A+B$ 以外をどれでもいいので1つ出力してね

そのまんまなので0～9を順番に見ていって $A+B$ ではなかった時点で出力して終了です。

#ABC343 A - Wrong Answer
A, B = map(int, input().split())
for i in range(10):
    if i != A+B:
        print(i)
        break

提出リンク：提出 #50769083 - AtCoder Beginner Contest 343

B - Adjacency Matrix

リンク：B - Adjacency Matrix (atcoder.jp)

概要： $N$ 個の頂点があり配列 $A$ の要素 $A_{ij}=1$ の時頂点 $i$ と $j$ は接続されています。頂点 $i$ とつながっている頂点の番号を出力してね

問題文で無向グラフとか頂点とか辺とか言われているので何も考えずグラフ作って順番に出力しました。

#ABC343 B - Adjacency Matrix
N = int(input())
G =[[] for i in range(N)]
for i in range(N):
    A = list(map(int, input().split()))
    for j in range(N):
        #A[i][j]が1の場合頂点iの接続先に頂点jを追加する
        if A[j] == 1:
            #1-indexedになるようにjに+1
            G[i].append(j+1)
for i in range(N):
    #グラフの各頂点からつながる頂点の番号を半角スペース区切りで出力
    print(*G[i], sep = ' ')

提出リンク：提出 #50784718 - AtCoder Beginner Contest 343

C - 343

リンク：C - 343 (atcoder.jp)

概要： $N$ 以下の立方数( $x^{3}$ )で回文になっている最大の数 $K$ を出力してね

$N \leq 10^{18}$ の制約です。

$K$ を0から $N$ まで全探索すると当然TLEになるので $x$ について全探索します。

$N=10^{18}$ でも $x=10^{6}$ なので十分間に合います。

回文かどうかの判定は $x^{3}$ を文字列として扱うと簡単です。

$s = str(x^{3})$ として、 $s[j] = s[-j-1]$ を $s$ の桁数半分（切り上げ）まで見てやれば判断できます。

探索する $x$ の数は $10^{6}$ 以内、回文の判定試行回数は $N$ の桁数半分の高々9回程度なので十分間に合います。

#ABC343 C - 343
N = int(input())
#探索範囲はNの3乗根切り上げから0まで
for i in range(int(N**(1/3))+2, 0, -1):
    if i**3 <= N:
        #iの3乗を文字列sとして扱う
        s = str(i**3)
        n = len(s)
        #回文判定のフラグ
        flag = True
        #sの桁数の半分切り上げまで探索する
        for j in range((n+1)//2):
            if s[j] != s[-j-1]:
                #回文ではない場合にNG判定
                flag = False
                break
        #NG判定なくループを越えたらiの3乗=Kを出力して終了
        if flag == True:
            print(i**3)
            break

提出リンク：提出 #50811831 - AtCoder Beginner Contest 343

D - Diversity of Scores

リンク：D - Diversity of Scores (atcoder.jp)

概要： $N$ 人が何らかの競技をしていて $T$ 秒時に $A_i$ さんが $B_i$ 点獲得しました。この時点で点数が何種類になっているか出力してね

$N \leq 2 \times 10^{5}$ 、 $T \leq 2 \times 10^{5}$ なので $O(NT)$ だとTLEになります。

制約を気にせず簡単に書くと次のようになります（当然TLEします）。

#ABC343 D - Diversity of Scores
N, T = map(int, input().split())
ans = [0] * N
for i in range(T):
    a, b = map(int, input().split())
    ans[a-1] += b
    print(len(set(ans)))

提出リンク：提出 #50817856 - AtCoder Beginner Contest 343

原因は配列 $ans$ のsetをとるときに $O(N)$ かかるためです。

なのでお気持ちとしてはlistのsetを毎回とるのではなくて最初からsetやdictを使いたい。

$B_i$ をsetに加えていくだけでは入力例1のように10点を2回とって20点になる場合と20点を1回とる場合を分離できない。

dictでその点数になっている人数を管理するにも誰が何点かを管理するいい方法が思いつかない。

本番中1時間くらい考えて思いつきませんでした。

順位表みたらA問題提出した人数の半分くらい解けてるので茶diff下位か高くても中位くらいかな？是非ともACしたかった・・・

解説見ると得点を管理するlistと度数分布を管理するdictの合わせ技みたいですね。dictの追加と削除は使ったことがなかったので大変勉強になりました。

Counterで都度度数分布を作ると毎回 $O(N)$ ですがdictの追加と削除はどちらも $O(1)$ なので間に合うというわけですね。

解説ACしたものが以下になります。

#ABC343 D - Diversity of Scores
#解説
from collections import defaultdict
N, T = map(int, input().split())
now = [0] * N
#dictを0で初期化
ans = defaultdict(int)
#keyを点数、ans[key]に人数を格納していく
#初期条件は0点がN人
ans[0] = N
for i in range(T):
    a, b = map(int, input().split())
    #今からaさん(0-indexed)の点数が変動するので度数分布から-1する
    ans[now[a-1]] -= 1
    #もし0人になったらkeyを削除
    if ans[now[a-1]] == 0:
        del ans[now[a-1]]
    #点数を管理するリストでaさんの点数にb点を足す
    now[a-1] += b
    #点数変動したので度数分布更新
    ans[now[a-1]] += 1
    print(len(ans))

提出リンク：提出 #50845459 - AtCoder Beginner Contest 343

結果

3完36min+1WAでした。

（C問題で探索範囲をミスった）

今回のD問題はACしておきたかった・・・