Vercel LogoMagicode
2

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

6 min read

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:ループでシミュレーション

[ ]

パターン2:条件分岐(本番はこれを提出)

[ ]

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文字目を取り出して、そこだけリバースしてあげて、その後で前後の反転しない部分を引っ付けたら良さそうですね
[ ]

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
    • (逃げとも言う)
  • 直積(デカルト積)なるものが求められます
[ ]

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
  • 累積和を、どこまで使いこなせてるかが測られちゃいますね。私は本番でダメでした…。反省。
[ ]

Discussion

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