KURORO BLOGのロゴ

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

【備忘録】AtCoder Beginner Contest 233 A~D問題

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

目次
  1. そもそもAtCoderとは?
  2. 「AtCoder Beginner Contest 233」
    1. コンテスト情報
    2. 配点
    3. ルール
  3. A -> 10yen Stamp
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. Contest中に考えたこと
    6. 解答
  4. B -> A Reverse
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. Contest中に考えたこと
    6. 解答
  5. C -> Product
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. Contest中に考えたこと
    6. 解答
  6. D -> Count Interval
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. 解答
  7. 参考文献
目次を開く⬇︎

執筆者 - おすすめの記事3選

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 233」

コンテスト情報

配点

問題点数
A                100                 
B200
C300
D400
E500
F500
G600
H600

ルール

  1. コンテスト中に問題に正解すると点数を獲得できます。
  2. 順位は総合得点で決定します。
  3. 同点の場合は提出時間の早い人が上の順位になります。
  4. 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)

このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。

A -> 10yen Stamp

問題文

サンタさんに手紙を出したい高橋くんは、 X円切手が1枚だけ貼られた封筒を用意しました。サンタさんに手紙を届けるためには、貼られている切手の総額がY円以上である必要があります。高橋くんは、この封筒に10円切手を何枚か貼り足すことで、貼られている切手の総額をY円以上にしたいです。

高橋くんはこの封筒に、最小で何枚の10円切手を貼り足す必要がありますか?

制約

  • X, Yは整数
  • 1 ≤ X, Y ≤ 1000

入力

入力は以下の形式で標準入力から与えられる。

1X Y

出力

答えを整数として出力せよ。

本問題は、AtCoder株式会社で作成された、A - 10yen Stamp問題を参照しております。

Contest中に考えたこと

  • 10円切手をY円を超えるまで足していく。
  • 10円切手を使った個数を出力する。

解答

1# 標準入力を受け付ける。
2X, Y = map(int, input().split())
3
4cnt = 0
5while X < Y:
6    cnt += 1
7    # 10円切手をY円を超えるまで足していく。
8    X += 10
9
10# 10円切手を使った個数を出力する。
11print(cnt)

B -> A Reverse

問題文

整数L, Rと、英小文字のみからなる文字列Sが与えられます。SのL文字目からR文字目までの部分を反転した(すなわち、 L文字目からR文字目までの文字の並びを逆にした)文字列を出力してください。

制約

  • Sは英小文字のみからなる。
  • 1 ≤ ∣S∣ ≤ 10の5乗(∣S∣はSの長さ)
  • L, Rは整数
  • 1 ≤ L ≤ R ≤ ∣S∣

入力

入力は以下の形式で標準入力から与えられる。

1L R
2S

出力

問題文の指示通り出力せよ。

本問題は、AtCoder株式会社で作成された、B - A Reverse問題を参照しております。

Contest中に考えたこと

  • L ~ Rの文字列を切り出して、反転する。
  • L ~ Rの文字列を切り出して、反転した文字列をL ~ R以外の文字列と連結する。

解答

1# 標準入力を受け付ける。
2L, R = map(int, input().split())
3s = input()
4
5# L ~ Rの間の文字列を反転する。
6# L - 1としているのは、配列のインデックスの始まりが0からだから。
7# 参考 : https://note.nkmk.me/python-str-extract/
8center = s[L - 1:R]
9# 参考 : https://note.nkmk.me/python-reverse-reversed/
10center = ''.join(list(reversed(center)))
11
12value = ''
13flag = False
14for i in range(len(s)):
15    # L ~ Rの間だけ、反転処理を行う。
16    # L - 1, R - 1としているのは、配列のインデックスの始まりが0からだから。
17    if L - 1 <= i and i <= R - 1:
18        if flag:
19            continue
20
21        flag = True
22
23        # 一度だけ反転した文字列の値を格納する。
24        value = value + center
25
26        continue
27    # それ以外の場合は反転処理を行わない。
28    value = value + s[i]
29
30print(value)

C -> Product

問題文

N個の袋があります。袋iにはLi個のボールが入っていて、袋iのj(1 ≤ j ≤ Li)番目のボールには正の整数ai, jが書かれています。

それぞれの袋から1つずつボールを取り出します。取り出したボールに書かれた数の総積がXになるような取り出し方は何通りありますか?

ただし、書かれた数が同じであっても全てのボールは区別します。

制約

  • N ≥ 2
  • Li ≥ 2
  • 袋に入っているボールの個数の総積は10の5乗を超えない。
  • 1 ≤ ai, j ≤ 10の9乗
  • 1≤ X ≤ 10の18乗
  • 入力に含まれる値は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

1N X
2L1 a1,1 a1,2 … a1,L1
3​L2 a2,1 a2,2 … a2,L2
45LN aN,1 aN,2 … aN,LN

出力

答えを出力せよ。

本問題は、AtCoder株式会社で作成された、C - Product問題を参照しております。

Contest中に考えたこと

  • 問題文を誤読していた。。
  • Xになる数 = 素因数分解して作られる値だと思う。素因数分解を行う。
  • 素因数分解した値からXになる組み合わせの数字(Xが40の場合、(4, 10), (2, 20)など)を洗い出す。
  • 組み合わせの数字に該当する袋内のボールがどれくらい存在するのか(Xが40の場合、(4, 10)の組み合わせの数字を持つ袋内のボールが(1, 2)存在する、(2, 20)の組み合わせの数字を持つ袋内のボールが(0, 1)存在するなど)確認する。
  • 洗い出した、組み合わせの数字に該当する袋内のボールの数を掛け合わせて、合計する。
  • ここで終了しました。。

解答

1import itertools
2# 袋に入っているボールの個数の総積は10の5乗を超えない。 ⏩ 袋の中からボールを1つずつ選ぶ組み合わせは10の5乗を超えないを意味する。 ⏩ 普通に全通り検証して問題ない。
3
4# 標準入力を受け付ける。
5N, X = map(int, input().split())
6
7# 袋の中に入っている、ボール情報を格納する。
8baggages = []
9
10for _ in range(N):
11    tmp = list(map(int, input().split()))
12    baggages.append(tmp[1:])
13
14# 参考 : https://note.nkmk.me/python-itertools-product/
15product_list = itertools.product(*baggages)
16ans = 0
17for product in product_list:
18    value = 1
19    for p in product:
20        if value > X:
21            break
22        value *= p
23
24    if X == value:
25        ans += 1
26
27print(ans)

D -> Count Interval

問題文

長さNの数列A=(A1, A2, …, AN)と、整数Kが与えられます。Aの連続部分列のうち、要素の和がKになるものはいくつありますか?

制約

  • 1 ≤ N ≤ 2 × 10の5乗
  • ∣Ai∣ ≤ 10の9乗
  • ∣K∣ ≤ 10の15乗
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

1N K
2A1 A2 … AN

出力

答えを出力せよ。

本問題は、AtCoder株式会社で作成された、D - Count Interval問題を参照しております。

解答

1################################
2# <方針>
3# 連続部分列 ⏩ 連続部分列の一番左のインデックスをl, 連続部分列の一番右のインデックスをrとした場合に、0インデックス~rの数列の総和 - 0インデックス~lの数列の総和 = Kになるか確かめることになる。
4# r - l = kになればいいので、l = r - kになるlの位置がどれくらいあるのか探せば良い。
5################################
6
7from collections import Counter
8
9# 標準入力を受け付ける。
10N, K = map(int, input().split())
11
12A = list(map(int, input().split()))
13
14cnt = Counter([0])
15ans = 0
16r = 0
17for a in A:
18    r += a
19    ans += cnt[r - K]
20    cnt[r] += 1
21
22print(ans)

2021年12月25日時点のレート画像

プロフィールを確認する

参考文献

記事に関するお問い合わせ