12 min readAtCoder
【備考録】AtCoder Beginner Contest 210 A~D問題
AtCoder Beginner Contest 210のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。
- そもそもAtCoderとは?
- 「AtCoder Beginner Contest 210」
- A -> Cabbages
- B -> Bouzu Mekuri
- C -> Colorful Candies
- D -> National Railway
- 参考文献
執筆者 - おすすめの記事3選
そもそもAtCoderとは?
AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。
今回は 「AtCoder Beginner Contest 210」のプログラミングコンテストへ参加しました。
「AtCoder Beginner Contest 210」
コンテスト情報
- コンテスト時間 : 100分
- レーティング更新対象 : 0 - 1999
配点
| 問題 | 点数 |
|---|---|
| A | 100 |
| B | 200 |
| C | 300 |
| D | 400 |
| E | 500 |
| F | 600 |
ルール
- コンテスト中に問題に正解すると点数を獲得できます。
- 順位は総合得点で決定します。
- 同点の場合は提出時間の早い人が上の順位になります。
- 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)
このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。
A -> Cabbages
問題文
高橋君はキャベツ屋さんにやってきました。
キャベツ屋さんでは、キャベツを1個X円で買うことができます。
ただし、キャベツをA個よりも多く買う場合、A + 1個目以降に買うキャベツについては1個Y円で買うことができます。（ここで、Y < Xが保証されます。）
高橋君がキャベツをN個買うために必要な金額を出力してください。
制約
- 1 ≤ N ≤ 10の5乗
- 1 ≤ A ≤ 10の5乗
- 1 ≤ Y < X ≤ 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
1N A X Y出力
高橋君がN個のキャベツを買うために必要な金額を出力せよ。
本問題は、AtCoder株式会社で作成された、A - Cabbages問題を参照しております。
Contest中に考えたこと
- N - Aを実行してY円で購入するキャベツの数を洗い出す。
- N - A > 0の時、A個のキャベツをX円で買い、A + 1以降のキャベツをY円で買う。
- N - A <= 0の時、全てのキャベツをX円で買う。
解答
1# 標準入力を受け付ける。
2N, A, x, y = map(int, input().split())
3
4# N - Aを実行してY円で購入するキャベツの数を洗い出す。
5nokori = N - A
6
7# N - A > 0の時、A個のキャベツをX円で買い、A + 1以降のキャベツをY円で買う。
8if nokori > 0:
9 print(nokori * y + A * x)
10# N - A <= 0の時、全てのキャベツをX円で買う。
11else:
12 print(N * x)B -> Bouzu Mekuri
問題文
N枚のカードからなる山札があります。
それぞれのカードは、「良いカード」か「悪いカード」かのどちらかです。
高橋君と青木君は、この山札を使って対戦ゲームをします。
このゲームでは、2人は交互に山札の一番上のカードを引いて、そのカードを食べます。
先に悪いカードを食べたプレイヤーの負けです。（ここで、山札には少なくとも1枚の悪いカードが含まれていることが保証されます。）
0と1からなる文字列Sが与えられます。i = 1, 2, …, Nについて、
- Sのi文字目が
0のとき、山札の上からi番目のカードが良いカードであることを表します。 - Sのi文字目が
1のとき、山札の上からi番目のカードが悪いカードであることを表します。
高橋君が先手でゲームを始めるとき、高橋君と青木君のどちらが負けるかを答えてください。
制約
- 1 ≤ N ≤ 10の5乗
- Nは整数
- Sは
0と1からなる長さNの文字列 - Sは少なくとも1個の
1を含む。
入力
入力は以下の形式で標準入力から与えられる。
1N
2S
出力
高橋君が先手でゲームを始めるとき、高橋君と青木君のどちらが負けるかを答えよ。高橋君が負けるならばTakahashi、青木君が負けるならばAokiと出力せよ。
本問題は、AtCoder株式会社で作成された、B - Bouzu Mekuri問題を参照しております。
Contest中に考えたこと
- 文字列Sをリスト型にする。
- 初めてSi(iは0から始める)の値が
1の場合のみを考える。 - iの値が偶数の場合
Takahashi, 奇数の場合Aokiを出力する。
解答
1# 標準入力を受け付ける。
2N = int(input())
3# 文字列Sをリスト型にする。
4s = list(input())
5
6for i in range(0, len(s)):
7 # 初めてSi(iは0から始める)の値が`1`の場合のみを考える。
8 if s[i] == '1':
9 # iの値が偶数の場合`Takahashi`, 奇数の場合`Aoki`を出力する。
10 if i % 2 == 0:
11 print('Takahashi')
12 else:
13 print('Aoki')
14 breakC -> Colorful Candies
問題文
N個のキャンディが左右一列に並んでいます。それぞれのキャンディは、色1、色2、…、色10の9乗の、10の9乗種類の色のうちいずれかの色をしています。
i = 1, 2, …, Nについて、左からi番目のキャンディの色は色ciです。
高橋君は並んでいるキャンディのうち、連続して並んだK個のキャンディをもらうことができます。すなわち、1 ≤ i ≤ N − K + 1を満たす整数iを選んで、 左からi番目、i + 1番目、i + 2番目、…、i + K − 1番目のキャンディをもらうことができます。
高橋君はいろいろな色のキャンディを食べたいので、 もらうキャンディに含まれる色の種類数が多いほどうれしい気持ちになります。
高橋君がもらうキャンディに含まれる色の種類数の最大値を出力してください。
制約
- 1 ≤ K ≤ N ≤ 3 × 10の5乗
- 1 ≤ ci ≤ 10の9乗
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
1N K
2c1 c2 … cN
出力
高橋君がもらうキャンディに含まれる色の種類数の最大値を出力せよ。
本問題は、AtCoder株式会社で作成された、C - Colorful Candies問題を参照しております。
Contest中に考えたこと
- Cnの整数列を分解してリストに入れる。
- 連続するK個のキャンディを全通り探索して、最大値を求める。 ⏩ 時間内(3 × 10の5乗)に間に合わない。
- 良い解法が浮かばずここで終了。
学んだこと
- 連続するK個の探し方 = i番目の要素を削除し、K + i番目の要素の追加を繰り返すことを意味する。
解答
1# 標準入力を受け付ける。
2N, K = map(int, input().split())
3C = list(map(int, input().split()))
4
5# キャンディの種類数情報
6kinds = {}
7# 先頭から連続するK個を取得して、種類数を求める。
8for i in range(0, K):
9 # 参考 : https://note.nkmk.me/python-dict-get/
10 if kinds.get(C[i]) is None:
11 kinds[C[i]] = 1
12 else:
13 kinds[C[i]] += 1
14
15# 要素数 = 種類数
16ans = len(kinds)
17
18# 連続するK個の探し方 = i番目の要素を削除し、K + i番目の要素の追加を繰り返すことを意味する。
19for i in range(0, N - K):
20 # 種類として外す処理
21 # 参考 : https://note.nkmk.me/python-dict-clear-pop-popitem-del/
22 kinds[C[i]] -= 1
23 if kinds[C[i]] == 0:
24 kinds.pop(C[i])
25
26 # 種類として追加する処理
27 if kinds.get(C[i + K]) is None:
28 kinds[C[i + K]] = 1
29 else:
30 kinds[C[i + K]] += 1
31
32 # 種類数の確認処理
33 ans = max(ans, len(kinds))
34
35print(ans)D -> National Railway
問題文
高橋王国はH行W列のグリッドで表されます。北からi行目、西からj列目のマスを(i, j)で表します。
このたび、高橋王国の国民から交通の利便性のために鉄道の建設を求める声が多数寄せられ、国王の高橋君は鉄道を建設しなければならなくなりました。
鉄道建設は以下の2つのステップからなります。
- まず、2つの異なるマスを選び、それぞれに駅を建設する。マス(i, j)に駅を建設するとAi, j円の費用がかかる。
- その後、建設した2つの駅を結ぶ線路を建設する。2つの駅がマス(i, j)とマス (i′, j′)にあるとき、これらを結ぶ線路の建設をするとC × (| i−i′ | + | j − j′ |)円の費用がかかる。（ここで、| x |はxの絶対値を表す。）
高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています。
鉄道建設にかかる費用として考えられる最小値を出力してください。
制約
- 2 ≤ H, W ≤ 1000
- 1 ≤ C ≤ 10の9乗
- 1 ≤ Ai j ≤ 10の9乗
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
1H W C
2A1,1 A1,2 ⋯ A1,W
3⋮
4AH,1 AH,2 ⋯ AH,W出力
鉄道建設にかかる費用として考えられる最小値を出力せよ。
本問題は、AtCoder株式会社で作成された、D - National Railway問題を参照しております。
学んだこと
- ひと駅を建設するための最小コストを求めておく。
- 駅から駅の距離を1ずつ拡張する。
- A[i][j]とひと駅を建設するための最小コスト、距離を元に、距離単位における最小の総コストを演算する。
- 上記の演算により、距離単位における最小の総コストが演算できたので、それ以内の距離の場合に最小の総コストになる場合がないのか探索する。
- 探索する際に配列外のindexを指定したらbreakする。
A[0][0]を固定して探索する場合
A[0][1]を固定して探索する場合
A[2][1]を固定して探索する場合
解答
1# 標準入力を受け付ける。
2H, W, C = map(int, input().split())
3
4A = []
5m = 10 ** 20
6result = 10 ** 20
7for i in range(0, H):
8 inp = list(map(int, input().split()))
9 A.append(inp)
10
11 # ひと駅を建設するための最小コストを求めておく。
12 m = min(m, min(inp))
13
14for i in range(0, H):
15 for j in range(0, W):
16 a = A[i][j]
17
18 # 10の6乗なのは、H, Wの上限が1000であるため。
19 # 駅から駅の距離を1ずつ拡張する。
20 for d in range(1, 10 ** 6):
21 # A[i][j]とひと駅を建設するための最小コスト、距離を元に、距離単位における最小の総コストを演算する。
22 if a + m + C * d > result:
23 break
24 for k in range(0, d + 1):
25 # 探索する際に配列外のindexを指定したらbreakする。
26 if i + k >= H:
27 break
28
29 l = d - k
30
31 # 上記の演算により、距離単位における最小の総コストが演算できたので、それ以内の距離の場合に最小の総コストになる場合がないのか探索する。
32 if j + l < W:
33 result = min(result, a + A[i + k][j + l] + C * d)
34
35 # 上記の演算により、距離単位における最小の総コストが演算できたので、それ以内の距離の場合に最小の総コストになる場合がないのか探索する。
36 if j - l >= 0:
37 result = min(result, a + A[i + k][j - l] + C * d)
38
39print(result)
