はじめに
この記事では、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 | import math |
B - Homework
https://atcoder.jp/contests/abc163/tasks/abc163_b
この問題も簡単ですね。リストA
のsum
を考えれば良いだけです。
1 | N, M = map(int,input().split()) |
C - management
https://atcoder.jp/contests/abc163/tasks/abc163_c
リストの特定の要素へのアクセスはO(1)
ですから、愚直に実装すれば問題なく間に合います。
v
社員番号は1
から始まるので、0-オリジン
の言語の場合はインデックスのずれに気をつけましょう。
1 | N = int(input()) |
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 | N = 9 |
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+4+7 = 13 |
のように、いずれかの数を1増やすことで和を1増やせるためです。
これができない状況は、和が最大となる時
1 | {7, 8, 9} |
であることが分かります。
この作ることができる和は連続する値になっているという性質を使うと、組み合わせの数は
1 | 和の最大値 - 和の最小値 + 1 |
で求められると分かります。
和の最大値
は
1 | 7 + 8 + 9 |
和の最小値
は
1 | 0 + 1 + 2 |
なので、
和の最大値 - 和の最小値
は
1 | (7 + 8 + 9) |
となります。一般的にはi * (N+1-i)
となります。
この計算はO(1)
なので、
問題全体としては(i
をK
からN+1
までループ回すので)、O(N)
で解くことができます。
なお、さらにシグマ計算をすることでループを回す必要すらなくなりO(1)
で解けます。
1 | N, K = map(int,input().split()) |
記事情報
- 投稿日:2020年4月20日
- 最終更新日:2020年4月20日