36か月前公開・36か月前更新・0 pv・6 min read

茶色コーダーがABC233の解けたところまで（A~D）

AtCoder競技プログラミングアルゴリズム

https://picsum.photos/seed/52eaf45715a84cce9dcafb545619e0a6/1200/630

AtCoder Beginner Contest 233

ABC233の問題を、Dまでの解説です。

Dは本番AC成らず、でしたがなんとかEが解けたので、2021年は緑で終わることが出来ました。
来年も頑張りましょう。

A - 10yen Stamp

Difficulty: 9

問題文

サンタさんに手紙を出したい高橋くんは、

X

円切手が

1

枚だけ貼られた封筒を用意しました。
サンタさんに手紙を届けるためには、貼られている切手の総額が

Y

円以上である必要があります。
高橋くんは、この封筒に

10

円切手を何枚か貼り足すことで、貼られている切手の総額を

Y

円以上にしたいです。
高橋くんはこの封筒に、最小で何枚の

10

円切手を貼り足す必要がありますか?

制約

$X,Y$ は整数
$1 \leq X,Y \leq 1000$

考察

ループでも条件分けでも

制約より、今貼られている切手の金額が最小＝1円、必要な切手の総額が最大＝1000円の時でも10円切手ならば高々100回のループで間に合う
条件分岐ならば、足りていない切手を10で割って、小数点以下を切り上げる

注意すべきポイント

$Y \leq X$ の時（＝既に金額が条件を満たしている）、貼る切手の枚数は0枚で良い点に注意
- 入力例2がそのケースですね

パターン1：ループでシミュレーション

# X,Yを整数で受け取り
X, Y = map(int, input().split())


diff = Y - X # 不足額
add_stamp = 0 # 追加した切手の金額

# 0~99まで、最大100枚の切手を貼るつもりで
for i in range(100):
    add_stamp = 10*i # 追加した切手の金額＝10円 * i枚
    
    # もし、追加した切手の金額が不足分以上＝封筒に貼られた金額たY円に届いた！
    if diff <= add_stamp:
        print(i) # 追加した切手の枚数を出力して終了
        exit()

パターン2：条件分岐（本番はこれを提出）

# X,Yを整数で受け取り
X, Y = map(int, input().split())

# 不足額
diff = Y - X

# もし既に金額が足りている＝不足していない場合、0を出力して終了
if X > Y:
    print(0)
    exit()
# もし不足額が10の倍数なら、不足額を10で割った答えが切手の枚数
if diff % 10 == 0:
    print(diff // 10)
# もし10の倍数ではない（＝あまりが出る）なら、1枚余分に切手が必要
else:
    print((diff // 10) + 1)

B - A Reverse

Difficulty: 23

問題文

整数

L,R

と、英小文字のみからなる文字列

S

が与えられます。

S

の

L

文字目から

R

文字目までの部分を反転した(すなわち、

L

文字目から

R

文字目までの文字の並びを逆にした)文字列を出力してください。

制約

$S$ は英小文字のみからなる。
$1 \leq |S| \leq 10^5$ ( $|S|$ は $S$ の長さ)
$L,R$ は整数
$1 \leq L \leq R \leq |S|$

考察

文字列操作はとりあえず入出力例を見てみる

何文字目〜、とか、どの部分を反転した〜、とか、具体例がぱっと掴めるので良いと思います
L=3,R=7の時、「abcdefgh」　→　「ab gfedc h」になってる
3文字目から7文字目を取り出して、そこだけリバースしてあげて、その後で前後の反転しない部分を引っ付けたら良さそうですね

# 入力を受け取り
L, R = map(int, input().split())
S = input()

# 文字列左側の部分、L文字目からR文字目までの反転が必要な部分、文字列右側の部分を個別に準備して…
S_L = S[:L - 1]
rev = S[L - 1:R]
S_R = S[R:]

# 結合する時点で中央部分を反転。reversed()でも良いと思います。
ans = S_L + rev[::-1] + S_R
print(ans)

C - Product

Difficulty: 604

問題文

N

個の袋があります。
袋

i

には

L_i

個のボールが入っていて、袋

i

の

j(1 \leq j \leq L_i)

番目のボールには正の整数

a_{i,j}

が書かれています。

それぞれの袋から

1

つずつボールを取り出します。
取り出したボールに書かれた数の総積が

X

になるような取り出し方は何通りありますか？

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

制約

$N \geq 2$
$L_i \geq 2$
袋に入っているボールの個数の総積は $10^5$ を超えない。すなわち、 $\prod_{i=1}^{N} \leq 10^5$
$1 \leq a_{i,j} \leq 10^9$
$1 \leq X \leq 10^18$
入力に含まれる値は全て整数である。

考察

方針…？何でも行けそうでどれも難しそう…

DFSでも行ける、らしい…
DPでも行ける、らしい…
- そもそも、「袋に入っているボールの個数の総積は $10^5$ を超えない。」
  この制約より、全パターンを全探索したとしても、 $10^5$ パターンで済むことが保証されている

じゃあ全部探索するとして…素直にforでループ組むのも実装大変そう…

そこで便利なライブラリ。itertools
- (逃げとも言う）
直積（デカルト積）なるものが求められます
- 参考：wiki
- 参考：note.nkmk.me

from itertools import product

# 入力
N,X = map(int,input().split())
L = []
for i in range(N):
    tmp_L = list(map(int, input().split()))
    L.append(tmp_L[1:]) # L(袋の中にあるボールの数)は不要なので捨てます
ans = 0

# デカルト積生成！!!
p = product(*L)

# パターン毎にループして…
for elem in p:
    tmp = 1
    # パターン毎に総積を求めて…
    for i in elem:
        tmp *= i
    
    # 総積 = Xならansをインクリメント
    if tmp == X:
        ans += 1

print(ans)

D - Count Interval

Difficulty: 726

問題文

長さ

N

の数列

A=(A_1,A_2,\dots,A_N)

と、整数

K

が与えられます。

A

の連続部分列のうち、要素の和が

K

になるものはいくつありますか？すなわち、以下の条件を全て満たす整数の組

(l,r)

はいくつありますか？

$1\leq l\leq r \leq N$
$\sum_{i=l}^r A_i=K$

制約

$1 \leq N \leq 2 \times 10^5$
$|A_i| \leq 10^9$
$|K| \leq 10^15$

考察

とりあえず初手：累積和

区間和や連続部分の要素の和が欲しいなら、前準備に $O(N)$ 、それ以降 $O(1)$ で区間の総和が求められる、累積和を準備するのが正着っぽいイメージ

全探索しようとすると…

数列の長さが最大で $2 \times 10^5$ なので、lとrをそれぞれ全探索していくと、 $O(N^2)$ となり確実にTLE。
ここからどう減らすかが焦点。

片方を固定するイメージ

数列Aから作った累積和、Sに対して、 $r$ を $S_1,S_2,\dots$ のように1つずつ動かしていく
$r=S_3$ の時、lは $S_1,S_2,S_3$ の中にしか存在しない
- この中で、 $r(=S_3) - K$ となる $l$ が高速で探せたら嬉しい（具体的には $O(N)$ 未満)
- $r$ が1つ右にずれるたび、 $l$ が存在する範囲が1つ増える
  - dictで要素数をそれぞれ管理してあげれば、 $r-K$ の数は一発で引けそう

じつはド典型

有名YouTuberのかつっぱ氏も言われてました
- 数列Aに対して特定の条件を満たす整数の組を求めたりしたいけど、愚直に全探索するとTLEになる問題
- 類題：agc023 - A
累積和を、どこまで使いこなせてるかが測られちゃいますね。私は本番でダメでした…。反省。

# 入力
N,K = map(int,input().split())
L = list(map(int, input().split()))

# 0始まりの累積和を作るよ
accum_d = defaultdict(int)
accum_L = [0]
for a in L:
    tmp = accum_L[-1] + a
    accum_L.append(tmp)

ans = 0

# r-Kの値がいくつあるかを、1つずつ足しながら数えていくよ
for i in range(1,N+1):
    accum_d[accum_L[i-1]] += 1
    ans += accum_d[accum_L[i]-K]

print(ans)