競技プログラミング

東京海上日動　プログラミングコンテスト2020

はじめに

この記事では、東京海上日動　プログラミングコンテスト2020のA~C問題を解説します。

A - Nickname

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_a

1
2
S = input()
print (S[:3])

B - Tag

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_b

AとBの大小関係を意識しなくていいようにA<Bとなるように入れ替えます。入れ替えても答えが変わらないことは明らかです。

1
2
3
4
5
6
7
8
9
a, v= map(int,input().split())
b, w= map(int,input().split())
t = int(input())
if b < a:
    a,b = b,a
if a+v*t >= b+w*t:
    print('YES')
else:
    print('NO')

C - Lamps

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_c

いもす法を用いることで操作をO(N)でできます。

これだと、全体の計算量がO(KN)となり間に合わないように思いますが、実際はK回も操作を行わずとも早い段階で全ての電球の明るさがNとなることがわかります。シミュレーションをしてみると、Nが最大で全ての電球の初期の光の強さを0としても操作は41回で十分です。

この解放でPyPyで提出することでACできます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import itertools
N, K = map(int,input().split())
A = list(map(int,input().split()))
K = min(41,K)
for k in range(K):
    imos = [0] * (N+1)
    for n in range(N):
        a = n - A[n]
        b = n + A[n]
        a = max(0,a)
        b = min(N-1,b)
        imos[a] += 1
        imos[b+1] -= 1
    csum = list(itertools.accumulate(imos))
    A = csum[:-1]
A = [str(a) for a in A]
print (' '.join(A))

関連記事

過去のABC解説記事です。

  • ABC169
    • A-F問題を解いています。
  • ABC168
    • A-E問題を解いています。
  • ABC167
    • A-E問題を解いています。
  • ABC166
    • A-F問題を解いています。
  • ABC165
    • A-F問題を解いています。
  • ABC164
    • A-E問題を解いています。
  • ABC163
    • A-D問題を解いています。
  • ABC162
    • A-E問題を解いています。

記事情報

  • 投稿日：2020年6月13日
  • 最終更新日：2020年6月13日