競技プログラミング

ABC163

はじめに

この記事では、AtCoder Beginer Contest 163のA~D問題を解説します。

前回のコンテスト(ABC162)から、使用可能言語が変更となりました。
Pythonのバージョンは3.8.2に変更されました。

これでようやく、gcd（最大公約数）のインポートのストレス（Python競プロでやりがちなミス）から解放されました。

前回の解説はこちら

A - Circle Pond

https://atcoder.jp/contests/abc163/tasks/abc163_a

特に解説はいらないと思います。

1
2 * 半径 * 円周率

を計算すれば良いです。円周率は標準ライブラリmathを使うと良いでしょう。

1
2
3
import math
r = int(input())
print (2*math.pi*r)

B - Homework

https://atcoder.jp/contests/abc163/tasks/abc163_b

この問題も簡単ですね。リストAのsumを考えれば良いだけです。

1
2
3
4
5
6
7
N, M = map(int,input().split())
A = list(map(int,input().split()))
ans = N-sum(A)
if ans < 0:
    print (-1)
else:
    print (ans)

C - management

https://atcoder.jp/contests/abc163/tasks/abc163_c

リストの特定の要素へのアクセスはO(1)ですから、愚直に実装すれば問題なく間に合います。
v
社員番号は1から始まるので、0-オリジンの言語の場合はインデックスのずれに気をつけましょう。

1
2
3
4
5
6
7
N = int(input())
A = list( map(int,input().split()))
cnt = [0] * N
for a in A:
    cnt[a-1]+=1
for n in range(N):
    print (cnt[n])

D - Sum of Large Numbers

https://atcoder.jp/contests/abc163/tasks/abc163_d

iの値が異なるパターン同士は和が必ず異なる

N+1個の数のうちi個を選び和を計算する状況を想定しましょう。この時10^100が十分に大きいためiの値が異なるパターン同士は和が必ず異なります。

10^100を無視

そしてこの点だけ考慮できれば、10^100の部分は全く無視してよく、10^100+aをaと読み替えられます。

部分問題に分解

iの値が異なるパターン同士は和が必ず異なるので、iは固定して部分問題を解き、iをKからN+1までループを回せば良いです。

さて、iを固定した時の部分問題について考えます。

具体例を考える

1
2
N = 9
i = 3

N=9なので、選択可能な数は以下のようになります。

1
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

i=3なので、この中から

1
{1, 4, 7}

のように数字を3つ選び組み合わせを考えます。

さて、全ての組み合わせを考えた際に和は何通りあるでしょうか。

全ての和は列挙すると以下のようになります。

1
[3, 4, 5,..., 23, 24]

実は、作ることができる和は連続する値になっています。これは

1
1+4+7 = 12

となっているときに

1
2
3
2+4+7 = 13
1+5+7 = 13 
1+4+8 = 13

のように、いずれかの数を1増やすことで和を1増やせるためです。

これができない状況は、和が最大となる時

1
{7, 8, 9}

であることが分かります。

この作ることができる和は連続する値になっているという性質を使うと、組み合わせの数は

1
和の最大値 - 和の最小値 + 1

で求められると分かります。

和の最大値は

1
7 + 8 + 9

和の最小値は

1
0 + 1 + 2

なので、

和の最大値 - 和の最小値は

1
2
3
4
  (7 + 8 + 9)
- (0 + 1 + 2)
--------------
   7 + 7 + 7

となります。一般的には
i * (N+1-i)となります。

この計算はO(1)なので、
問題全体としては（iをKからN+1までループ回すので）、O(N)で解くことができます。

なお、さらにシグマ計算をすることでループを回す必要すらなくなりO(1)で解けます。

1
2
3
4
5
6
7
8
N, K = map(int,input().split())
ans = 0
MOD = 10**9 + 7
for i in range(K,N+2):
    x = (N+1-i) * i + 1
    ans += x
    ans %= MOD
print (ans)

記事情報

  • 投稿日：2020年4月20日
  • 最終更新日：2020年4月20日