ABC343 A-D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、競技プログラミングコンテストのことです。

A-D問題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC343

A – Wrong Answer

問題

A問題

0以上9以下の整数A, Bに対し、0以上9以下の整数であってA + Bと等しくないものをいずれかひとつ出力する問題です。

思考の筋道

0から順にA + Bと等しいか調べます。等しくないものが現れれば、出力してその時点でプログラム終了すれば良いでしょう。

コード

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

for i in range(10):
    if i != A + B:
        print(i)
        exit()

B – Adjacency Matrix

問題

B問題

N頂点の単純無向グラフとその隣接行列が与えられます。頂点 i と直接結ばれている頂点の番号を昇順に出力する問題です。

思考の筋道

問題文は一見複雑ですが、例1を見れば分かりやすいですね。2次元配列を全探索して、値が1かどうかを一つずつ調べていきましょう。

コード

from sys import stdin
N = int(input())
A = [list(map(int, stdin.readline().split())) for _ in range(N)]

for row in A:
    l = []
    for i in range(N):
        if row[i] == 1:
            l.append(i + 1)
    print(*l)

C – 343

問題

C問題

N以下の正整数であって回文立方数であるものの最大値を求める問題です。

回文立方数とは、回文数であり、立方数でもある数のことです。なお、回文数とは、前から読んでも後ろから読んでも同じである数のことであり、立方数とは、ある正整数の3乗である数のことです。

思考の筋道

Nには10^18以下という制約があります。そのため、3乗根は10^6以下であることが保証されています。10^6個であれば、その3乗が回文数になっているかを一つずつ調べることが可能です。求めたいのは最大値のため、大きい方から調べていけばよいでしょう。

以上が大筋、ここからは気をつけるべき話です。

Nの3乗根を求める際に誤差が発生することがあります。例えば、1030301は101の3乗なのですが、3乗根を調べると100.99999999999997となります。これを切り捨てると100となります。100以下の数を調べるのでは、101が対象から漏れてしまいます。これではいけないので、3乗根を整数値にする際は、切り捨てではなく切り上げを行いましょう。その結果、3乗した数がNを超える可能性がありますが、それは条件分岐で除けばよいです。

コード

import math
N = int(input())

n = math.ceil(N ** (1 / 3))
for i in reversed(range(1, n + 1)):
    word = str(i ** 3)
    if i ** 3 <= N and word == word[::-1]:
        print(i ** 3)
        exit()

D – Diversity of Scores

問題

D問題

N人の選手のそれぞれの時刻における得点に何種類の値が現れるかを求める問題です。

例えば、ある時点における選手たちの得点がそれぞれ10, 20, 30, 20点であった場合、この時点での選手たちの得点には3種類の値が現れています。

思考の筋道

素直に1人1人の得点を追っていてはTLEになってしまいます。知りたいことは得点が何種類かですので、1人1人の得点ではなく、各得点の人が何人いるかを管理するので十分です。

はじめの段階では 0点の人がN人です。1人が10点を得たとすると、0点の人がN-1人となり、10点の人が1人になります。このように人数の変動を管理していきましょう。管理には、辞書（keyが点数、valueがその点数の人数）を使えばよいです。

コード

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

P = [0] * N
d = {0: N}

for _ in range(T):
    A, B = map(int, input().split())

    d[P[A - 1]] -= 1
    if d[P[A - 1]] == 0:
        del d[P[A - 1]]

    P[A - 1] += B

    if P[A - 1] not in d.keys():
        d[P[A - 1]] = 1
    else:
        d[P[A - 1]] += 1

    print(len(d.keys()))