AtCoder Beginner Contest 152の感想

AtCoder

2020.01.192020.04.14

ABC152に参加した。

AtCoder Beginner Contest 152 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – AC or WA

n=mの時のみACになる。

n, m = map(int, input().split())

if n == m:
    print('Yes')
else:
    print('No')

B – Comparing Strings

辞書順で答えるので、aとbの大小を比較する。

a, b = map(int, input().split())

if a <= b:
    print(str(a) * b)
else:
    print(str(b) * a)

C – Low Elements

先頭から順番に値を見ていって、最小値が更新された回数が答え。

答えの最小値は1なので、0から足し込まないよう注意する。

n = int(input())
p = [int(x) for x in input().split()]

ans = 1
base = p[0]

for i in range(1, n):
    if p[i] < base:
        ans += 1
        base = p[i]

print(ans)

D – Handstand 2

二重ループでナイーブな実装をしようとしたが、1≤N≤2×10^5 のため、O(N^2)となり間に合わない。

間に合わないのは分かったが、他の実装が思いつかず、本番中にACできなかった。

1からNまでの値のうち、先頭の数と末尾の数に絞って総当たりで調べ、二重配列に個数を記憶させる。

これはO(N)で計算できるので間に合う。

100ます計算のような表をイメージするとわかりやすいかも？

					先	頭	の	数
		1	2	3	4	5	6	7	8	9	0
	1
	2
	3
末	4
尾	5
の	6
数	7
	8
	9
	0

求める答えは「A の末尾の桁が B の先頭の桁に等しく、 A の先頭の桁が B の末尾の桁に等しい数の個数」なので、上の表の [ i ][ j ] と [ j ][ i ] の要素を掛け算し、総和を求めれば良い。

n = int(input())

table = [[0] * 10 for _ in range(10)]

for i in range(1, n + 1):
    sentou = int(str(i)[0])
    matsubi = int(str(i)[-1])
    table[sentou][matsubi] += 1

ans = 0
for i in range(10):
    for j in range(10):
        ans += table[i][j] * table[j][i]

print(ans)

引き続き茶色を目指して頑張っていく。