Ccmmutty logo
Commutty IT
6 min read

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

https://picsum.photos/seed/52eaf45715a84cce9dcafb545619e0a6/600/800

AtCoder Beginner Contest 233

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

A - 10yen Stamp

Difficulty: 9

問題文

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

制約

  • X,YX,Y は整数
  • 1X,Y10001 \leq X,Y \leq 1000

考察

ループでも条件分けでも
  • 制約より、今貼られている切手の金額が最小=1円、必要な切手の総額が最大=1000円の時でも10円切手ならば高々100回のループで間に合う
  • 条件分岐ならば、足りていない切手を10で割って、小数点以下を切り上げる
注意すべきポイント
  • YXY \leq Xの時(=既に金額が条件を満たしている)、貼る切手の枚数は0枚で良い点に注意
    • 入力例2がそのケースですね

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

python
# 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:条件分岐(本番はこれを提出)

python
# 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,RL,R と、英小文字のみからなる文字列 SS が与えられます。
SSLL 文字目から RR 文字目までの部分を反転した(すなわち、 LL 文字目から RR 文字目までの文字の並びを逆にした)文字列を出力してください。

制約

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

考察

文字列操作はとりあえず入出力例を見てみる
  • 何文字目〜、とか、どの部分を反転した〜、とか、具体例がぱっと掴めるので良いと思います
  • L=3,R=7の時、「abcdefgh」 → 「ab gfedc h」になってる
  • 3文字目から7文字目を取り出して、そこだけリバースしてあげて、その後で前後の反転しない部分を引っ付けたら良さそうですね
python
# 入力を受け取り
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

問題文

NN 個の袋があります。
ii には LiL_i個のボールが入っていて、袋 iij(1jLi)j(1 \leq j \leq L_i)番目のボールには正の整数 ai,ja_{i,j}が書かれています。
それぞれの袋から 11 つずつボールを取り出します。
取り出したボールに書かれた数の総積が XX になるような取り出し方は何通りありますか?
ただし、書かれた数が同じであっても全てのボールは区別します。

制約

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

考察

方針…?何でも行けそうでどれも難しそう…
  • DFSでも行ける、らしい…
  • DPでも行ける、らしい…
    • そもそも、「袋に入っているボールの個数の総積は10510^5を超えない。」
      この制約より、全パターンを全探索したとしても、10510^5パターンで済むことが保証されている
じゃあ全部探索するとして…素直にforでループ組むのも実装大変そう…
  • そこで便利なライブラリ。itertools
    • (逃げとも言う)
  • 直積(デカルト積)なるものが求められます
python
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

問題文

長さ NN の数列 A=(A1,A2,,AN)A=(A_1,A_2,\dots,A_N)と、整数 KK が与えられます。
AA の連続部分列のうち、要素の和が KK になるものはいくつありますか? すなわち、以下の条件を全て満たす整数の組 (l,r)(l,r) はいくつありますか?
  • 1lrN1\leq l\leq r \leq N
  • i=lrAi=K\sum_{i=l}^r A_i=K

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • Ai109|A_i| \leq 10^9
  • K1015|K| \leq 10^15

考察

とりあえず初手:累積和
  • 区間和や連続部分の要素の和が欲しいなら、前準備にO(N)O(N)、それ以降O(1)O(1)で区間の総和が求められる、累積和を準備するのが正着っぽいイメージ
全探索しようとすると…
  • 数列の長さが最大で2×1052 \times 10^5なので、lとrをそれぞれ全探索していくと、O(N2)O(N^2)となり確実にTLE。
  • ここからどう減らすかが焦点。
片方を固定するイメージ
  • 数列Aから作った累積和、Sに対して、rrS1,S2,S_1,S_2,\dotsのように1つずつ動かしていく
  • r=S3r=S_3の時、lはS1,S2,S3S_1,S_2,S_3の中にしか存在しない
    • この中で、r(=S3)Kr(=S_3) - Kとなるllが高速で探せたら嬉しい(具体的にはO(N)O(N)未満)
    • rrが1つ右にずれるたび、llが存在する範囲が1つ増える
      • dictで要素数をそれぞれ管理してあげれば、rKr-Kの数は一発で引けそう
じつはド典型
  • 有名YouTuberのかつっぱ氏も言われてました
    • 数列Aに対して特定の条件を満たす整数の組を求めたりしたいけど、愚直に全探索するとTLEになる問題
    • 類題:agc023 - A
  • 累積和を、どこまで使いこなせてるかが測られちゃいますね。私は本番でダメでした…。反省。
python
# 入力
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)

Discussion

コメントにはログインが必要です。