KURORO BLOGのロゴ

このエントリーをはてなブックマークに追加
【備考録】AtCoder Beginner Contest 210 A~D問題

【備考録】AtCoder Beginner Contest 210 A~D問題

AtCoder Beginner Contest 210のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。

目次
  1. そもそもAtCoderとは?
  2. 「AtCoder Beginner Contest 210」
    1. コンテスト情報
    2. 配点
    3. ルール
  3. A -> Cabbages
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. Contest中に考えたこと
    6. 解答
  4. B -> Bouzu Mekuri
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. Contest中に考えたこと
    6. 解答
  5. C -> Colorful Candies
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. Contest中に考えたこと
    6. 学んだこと
    7. 解答
  6. D -> National Railway
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. 学んだこと
    6. 解答
  7. 参考文献
目次を開く⬇︎

そもそもAtCoderとは?

AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。

今回は 「AtCoder Beginner Contest 210」のプログラミングコンテストへ参加しました。

「AtCoder Beginner Contest 210」

コンテスト情報

配点

問題点数
A                100                 
B200
C300
D400
E500
F600

ルール

  1. コンテスト中に問題に正解すると点数を獲得できます。
  2. 順位は総合得点で決定します。
  3. 同点の場合は提出時間の早い人が上の順位になります。
  4. 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは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枚の悪いカードが含まれていることが保証されます。)

01からなる文字列Sが与えられます。i = 1, 2, …, Nについて、

  • Sのi文字目が0のとき、山札の上からi番目のカードが良いカードであることを表します。
  • Sのi文字目が1のとき、山札の上からi番目のカードが悪いカードであることを表します。

高橋君が先手でゲームを始めるとき、高橋君と青木君のどちらが負けるかを答えてください。

制約

  • 1 ≤ N ≤ 10の5乗
  • Nは整数
  • Sは01からなる長さ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        break

C -> 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)

参考文献