AtCoder Beginner Contest 265 メモ(A-D)

今回の結果

2AC

今回は調子が悪い。
ハマってしまう問題が多かった。

A - Apple

https://atcoder.jp/contests/abc265/tasks/abc265_a
Difficulty: 18

問題文

果物屋さんでりんごが売られています。
あなたは次の操作を好きな順で好きなだけ繰り返すことができます。

• $X$ 円を払ってりんごを $1$ 個手に入れる。
• $Y$ 円を払ってりんごを $3$ 個手に入れる。

りんごを ちょうど $N$ 個手に入れるには最低何円必要ですか？

制約

• $1 \leq X \leq Y \leq 100$
• $1 \leq N \leq 100$
• 入力される値はすべて整数

入力

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

$X$ $Y$ $N$

出力

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

入出力例

入力例 1

10 25 10

出力例 1

85

入力例 2

10 40 10

出力例 2

100

入力例 3

100 100 2

出力例 3

200

入力例 4

100 100 100

出力例 4

3400

参加中に考えたこと

A問題だからループ使わなくてもできるような気はするが、$X \leq Y \leq 100$ なので、 $X$ と $Y$ とを二重ループで全探索して条件を満たすものを探しつつ、その中で最小になる金額を残すようにすればよい。

考察・感想

B - Explore

https://atcoder.jp/contests/abc265/tasks/abc265_b
Difficulty: 152

問題文

高橋君はゲームの中で洞窟を探索しています。

洞窟は $N$ 個の部屋が一列に並んだ構造であり、入り口から順に部屋 $1,2,\ldots,N$ と番号がついています。

最初、高橋君は部屋 $1$ におり、持ち時間 は $T$ です。
各 $1 \leq i \leq N-1$ について、持ち時間を $A_i$ 消費することで、部屋 $i$ から部屋 $i+1$ へ移動することができます。これ以外に部屋を移動する方法はありません。
また、持ち時間が $0$ 以下になるような移動は行うことができません。

洞窟内には $M$ 個のボーナス部屋があります。$i$ 番目のボーナス部屋は部屋 $X_i$ であり、この部屋に到達すると持ち時間が $Y_i$ 増加します。

高橋君は部屋 $N$ にたどりつくことができますか？

制約

• $2 \leq N \leq 10^5$
• $0 \leq M \leq N-2$
• $1 \leq T \leq 10^9$
• $1 \leq A_i \leq 10^9$
• $1 < X_1 < \ldots < X_M < N$
• $1 \leq Y_i \leq 10^9$
• 入力に含まれる値は全て整数である

入力

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

$N$ $M$ $T$
$A_1$ $A_2$ $\ldots$ $A_{N-1}$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_M$ $Y_M$

出力

高橋君が部屋 $N$ にたどりつくことができるなら Yes を、できないなら No を出力せよ。

入出力例

入力例 1

4 1 10
5 7 5
2 10

出力例 1

Yes

入力例 2

4 1 10
10 7 5
2 10

出力例 2

No

参加中に考えたこと

$T$ が $10^9$以上になるのでint型だと桁あふれする場合がある。
その点だけ気を付けてあとは問題文の通りにシミュレートすればよさそう。
提出するもACできない。
WAのテストケースが多いのは何か根本的に考え間違いをしていそうだが分からないのでスキップ。

考察・感想

コンテストが終わった後に問題文を見直していると、

持ち時間が 0 以下になるような移動は行うことができません。

この部分を読み違えてる。。
$T$ が $0$ になる場合もNGだと気づき、No判定する部分の条件判定のところを <0 から <=0 と = をつけたら追加したらACした。。

問題文の "持ち時間" のところが太字になってるのはなんでだろう。
"0以下" の部分こそ太字にするところなんじゃないかな？

C - Belt Conveyor

https://atcoder.jp/contests/abc265/tasks/abc265_c
Difficulty: 212

問題文

縦 $H$ マス、横 $W$ マスのグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。
$(i,j)$ には文字 $G_{i,j}$ が書きこまれています。ここで $G_{i,j}$ は U, D, L, R のいずれかです。

あなたは $(1,1)$ にいます。あなたは移動することができなくなるまで次の操作を繰り返します。

あなたは現在 $(i,j)$ にいるとする。

$G_{i,j}$ が U であり、かつ $i \neq 1$ ならば $(i-1,j)$ へ移動する。
$G_{i,j}$ が D であり、かつ $i \neq H$ ならば $(i+1,j)$ へ移動する。
$G_{i,j}$ が L であり、かつ $j \neq 1$ ならば $(i,j-1)$ へ移動する。
$G_{i,j}$ が R であり、かつ $j \neq W$ ならば $(i,j+1)$ へ移動する。
それ以外の場合、あなたは移動することができない。

操作を終了した時点であなたがいるマスを出力してください。
ただし、あなたが操作を終了することなく無限に移動し続ける場合は -1 を出力してください。

制約

• $1 \leq H, W \leq 500$
• $G_{i,j}$ は U, D, L, R のいずれかである。
• $H, W$ は整数である。

入力

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

$H$ $W$
$G_{1,1}G_{1,2}\dots G_{1,W}$
$G_{2,1}G_{2,2}\dots G_{2,W}$
$\vdots$
$G_{H,1}G_{H,2}\dots G_{H,W}$

出力

操作を終了した時点であなたが $(i,j)$ にいる場合は次の形式で出力せよ。

$i$ $j$

また、無限に動き続ける場合は -1 を出力せよ。

入出力例

入力例 1

2 3
RDU
LRU

出力例 1

1 3

入力例 2

2 3
RRD
ULL

出力例 2

-1

入力例 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

出力例 3

9 5

参加中に考えたこと

$H, W \leq 500$ しかないので全探索に近い方法でいけそう。
$(1,1)$ から始めて操作を順に進めていって、既に通ったところになったら -1 を、グリッドの端で止まったらその値を出力すればよい。
既に通ったところかどうかは別途二次元配列を持つでもよし、連想配列で持って値があるかを判定する方法でもよし。

考察・感想

このテキストを書いてるときに気づいたけど、入力例3のグリッドの中に ABC265 って描かれてますね。

D - Iroha and Haiku (New ABC Edition)

https://atcoder.jp/contests/abc265/tasks/abc265_d
Difficulty: 727

問題文

長さ $N$ の数列 $A=(A_0,\ldots,A_{N-1})$ があります。
次の条件を全て満たす整数の組 $(x,y,z,w)$ が存在するか判定してください。

• $0 \leq x < y < z < w \leq N$
• $A_x + A_{x+1} + \ldots + A_{y-1} = P$
• $A_y + A_{y+1} + \ldots + A_{z-1} = Q$
• $A_z + A_{z+1} + \ldots + A_{w-1} = R$

制約

• $3 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq P,Q,R \leq 10^{15}$
• 入力に含まれる値は全て整数である

入力

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

$N$ $P$ $Q$ $R$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$

出力

条件を満たす組が存在するなら Yes、存在しないなら No を出力せよ。

入出力例

入力例 1

10 5 7 5
1 3 2 2 2 3 1 4 3 2

出力例 1

Yes

$(x,y,z,w)=(1,3,6,8)$ が条件を満たします。

入力例 2

9 100 101 100
31 41 59 26 53 58 97 93 23

出力例 2

No

入力例 3

7 1 1 1
1 1 1 1 1 1 1

出力例 3

Yes

参加中に考えたこと

明確に方針が見えないが、入力例1 を使って考えてみる。

$(x,y,z,w)=(1,3,6,8)$ が条件を満たします。

とあるので実際に当てはめてみると以下のようになる。

$x=1,y=3 \to A_1 + A_2 = 5 = P$
$y=3,z=6 \to A_3 + A_4 + A_5 = 7 = Q$
$z=6,w=8 \to A_6 + A_7 = 5 = R$

$x,y$ 、 $y,z$ 、 $z,w$ の範囲を求めたくて、毎回その範囲の和を計算すると時間がかかるから、累積和を使うのが良さそうとかなと思った。
入力例1 の累積和の配列を $B$ とすると以下のように表せる。

$i$	0	1	2	3	4	5	6	7	8	9
$A[i]$	1	3	2	2	2	3	1	4	3	2
$B[i]$	1	4	6	8	10	13	14	18	21	23

$B$ を使うと、$(B[2]-B[0], B[5]-B[2], B[7]-B[5]) = (6-1,13-6,18-13) = (5,7,5) = (P,Q,R)$ となって $B$ だけを使って条件を満たす組の有無が探せる。
ただ変数が4つもあるので単純に全探索すると $O(N^4)$ の計算量で間に合わない。
後はここからどうするか。
尺取り法とか使って解くのかとか考えるも方法が分からずにタイムアップ。

考察・感想

結局分からないので解説を見る。
累積和＋二分探索か。確かにこれなら $O(N \space log \space N)$ でいけるか。