3/14 コメントを元に修正しました。ありがとうございます。
競プロ全くの初心者がAtcoderへの参加を始めたので、勉強のために記事を書きます。
参加したコンテストはこちら↓。
AtCoder Beginner Contest 158
言語はPythonでいきます。
目的は復習なので、自分が実際に出した解ではありません。解説やら他の解答やらいろいろみて書いてます。
A - Station and Bus
駅の情報として文字列が与えられて、その中にA会社とB会社の二種類の駅が含まれているでしょうか？という問題です。
実際の提出では、正直に文字列をforで回して違う駅が含まれているかを調べました。この場合与えられる文字列は三つだけなので、単純に比較すればいいだけですね。
s = input()
if s[0] == s[1] or s[1] == s[2]: print('No')
else: print('Yes')
B - Count Balls
青と赤のボールを決まった数ずつ置いていくと、特定の地点までに青は何個含まれているでしょうか？という問題です。
これも正直にforで回そうとしたところ、計算時間オーバーになりました。ここでようやくそういうゲームではないことに気づきます。以下よりずっと汚いコードで提出しました。
N, A, B = map(int, input().split())
out = N // (A + B) * A
rem = min(N % (A + B), A)
print(out + rem)
残ってる数を求めるときは剰余計算が便利なんだなあと解説を見て思いました。
C - Tax Increase
軽減税率を適用してA円、適用しないでB円となる単価はあるでしょうか？という問題です。
計算する範囲を絞るために、最初にAの条件を満たす最小値と最大値を設定、その範囲でBの条件を満たすか調べます。この範囲指定が厄介で、やることは算数レベルなのに頭がこんがらがってめっちゃ詰まりました。
import math
A, B = map(int, input().split())
minV = math.ceil(A / 0.08)
maxV = (A + 1) // 0.08
for i in range(minV, maxV):
if int(i * 0.1) == B:
print(i)
exit()
print(-1)
ただし、この問題では$1 \leq A, B \leq 100$という狭い範囲の設定が最初から明言されているので素直に1から探していってよかったようです。計算量はO(n)なので余計なことして詰まるよりよっぽどいい。
A, B = map(int, input().split())
maxV = 1010 # これ以上の値は絶対に条件Bを満たさない。
for i in range(1, maxV):
if int(i * 0.08) == A and int(i * 0.1) == B:
print(i)
exit()
print(-1)
D - String Formation
与えられるコマンドに従って文字列を変化させていく問題です。
素直に書いたのが以下の書き方です。このような回答を提出して計算時間がオーバーしました。
s = input()
n = int(input())
for i in range(n):
Q = input().split()
if Q[0] == '1':
s = s[::-1]
else:
if Q[1] == '1':
s = Q[2] + s
else:
s = s + Q[2]
print(s)
解説によると、文字列を反転させる操作のたびに時間がかかってしまうようです。実際に反転させるのではなく、反転しているかどうかの情報を保持するべき。また、「配列の先頭に加える処理」には時間がかかるため、「配列の最後に加える処理」をする必要があるらしいです。
というわけで「反転しているかどうか」を示す変数isReverseを追加。必ず文字列の「末尾に追加する処理」になるように先頭の情報を格納する変数topを追加。
s = input()
top = ''
n = int(input())
isReverse = False
for i in range(n):
Q = input().split()
if(Q[0] == '1'):
isReverse = not isReverse
else:
if Q[1] == '1':
if isReverse: s += Q[2]
else: top += Q[2]
else:
if isReverse: top += Q[2]
else: s += Q[2]
if isReverse: s = s[::-1] + top
else: s = top[::-1] + s
print(s)
これで時間内に実行できました。
E - Divisible Substring
与えられた数列の中に$p$で割り切れる区間が何個あるか、という問題です。
提出したのはこんな感じ。順列を全部調べて$O(n^2)$の計算量、もちろん時間オーバーしました。
n, p = map(int,input().split())
s = input()
count = 0
for i in range(n):
for j in range(1, n - i + 1):
num = int(s[i: i + j])
if num % p == 0:
count += 1
print(count)
これは数学的なテクニックが必要になるようです。解説の文章だけではつらかったので、解説動画を見ました。
まず、与えられた文字列に右から番号を振っていきます。
$$ D = [d_N, d_{N - 1}, \cdots, d_1, d_0] $$
それぞれの値を$10^i$倍したものが実際に扱いたい数値となります。
$$ D' = [d_N\times 10^N, d_{N - 1}\times 10^{N- 1}, \cdots, d_1\times 10, d_0]$$
それぞれの桁数ごとに$p$を割った余りを考えます。ただし「2で割る場合」「5で割る場合」では10の乗数に干渉してしまうため除外します。よって場合分けを行います。
(i)
$p\neq 2, 5$の場合
$$ M = [(d_N\times 10^N)\% p, (d_{N - 1}\times 10^{N- 1})\% p, \cdots, (d_1\times 10)\% p, (d_0)\% p]$$
求めた剰余項を$m_i$と表しておきましょう。
$$ M = [m_N, m_{N - 1}, \cdots, m_1, m_0]$$
0からi番目の桁数までの数値を合計した値$V_i$は
$$ V_i = \sum^i_{k = 0} d_i \times 10^i $$
で求まります。その数値をpで割った余り$s_i$は
$$ s_i = (\sum^i_{k = 0} m_i) \% p $$
で求まります。 これを数列で表記してみましょう。
$$ S = [s_N, s_{N - 1}, \cdots, s_1, s_0]$$
この$s_i$が一致する区間を切り出せば、それは$p$で割れる値になります。というわけでその組み合わせの数を数えればよいことになります。また$s_i=0$を満たす桁はそのまま割り切れる数値なので、その数も数えます。
(ii)
$p = 2, 5$の場合
2で割り切れる数、5で割り切れる数というのは最後の桁だけ見れば判定できます。条件を満たす数字を1の桁にする場合に存在しうる組み合わせ(その数字が左からn桁目ならn通り)を全て合計すれば求まります。
という理屈ですが、これをさらに高速化するために剰余計算の分配法則
$$ ab \mod c = (a \mod c)(b\mod c)\mod c $$
を使って$10^i$にも剰余計算をかけています。これに気が付かなくて(というか剰余計算の法則を知らなかったので)他の人の解答例を見ながらでもTLEが頻発しました。
n, p = map(int,input().split())
D = input()
out = 0
if 10 % p == 0:
for i in range(n):
if int(D[i]) % p == 0:
out += i + 1
else:
mod = 0
count = [0] * p
ten = 1
count[mod] += 1
for i in range(n):
mod = (mod + int(D[n-i-1]) * ten) % p
ten = ten * 10 % p
count[mod] += 1
for c in count:
out += (c * (c - 1)) // 2
print(out)
とりあえずここまでで記事を締めます。時間があればF問についても追記したい。