AtCoder Beginner Contest 261 メモ(A-E)

今回の結果

4AC

A問題に時間かけすぎた。
今回はC問題がかなり簡単でD問題も易しめだったので、D問題が解けたことで自分のパフォーマンスが出せたかな。

A - Intersection

https://atcoder.jp/contests/abc261/tasks/abc261_a

Difficulty: 51

問題文

数直線があり、高橋君はこれを赤色と青色で次のように塗りました。

• $X=L_1$ ​から $X=R_1$ までをすべて赤色で塗る。
• $X=L_2$ から $X=R_2$ までをすべて青色で塗る。

数直線のうち、赤色と青色の両方で塗られている部分の長さを求めてください。

制約

• $0≤L_1<R_1≤100$

• $0≤L_2<R_2≤100$

• 入力はすべて整数

入力

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

$L_1$ $R_1$ $L_2$ $R_2$
​

出力

両方の色で塗られている部分の長さを整数で出力せよ。

入出力例

入力例 1

0 3 1 5

出力例 1

2

入力例 2

0 1 4 5

出力例 2

0

入力例 3

0 3 3 7

出力例 3

0

参加中に考えたこと

数直線は苦手。L1,R1,L2,R2の4つの位置関係をif文で分岐させて解くんだけろうけど、パターンが漏れていてWAしてしまった。。
パターンが多くて洗い出すのが大変。
赤と青を入れ替えて必ず赤が左に来るようにすればパターンは半分には減らせるけども、それでも3パターン必要になるのか。
いっそ配列作ってシミュレーションして重なっている部分を数え上げようかとも思ったけど結局if文で解いた。
A問題にしてはちょっと難しい？

考察・感想

$max(L1,L2) < X < min(R1,R2)$
この発想が持てなかった。3本以上の共通点を探す場合はif文ではしんどいのでこの方法を使うことになるかな。

B - Tournament Result

https://atcoder.jp/contests/abc261/tasks/abc261_b

Difficulty: 74

問題文

$N$ 人の人が総当り戦の試合をしました。

$N$ 行 $N$ 列からなる試合の結果の表 $A$ が与えられます。$A$ の $i$ 行目 $j$ 列目の要素を $A_{i,j}$ と表します。
$A_{i,j}$ は $i=j$ のとき - であり、それ以外のとき W, L, D のいずれかです。
$A_{i,j}$ が W, L, D であることは、人 $i$ が人 $j$ との試合に勝った、負けた、引き分けたことをそれぞれ表します。

与えられた表に矛盾があるかどうかを判定してください。

次のいずれかが成り立つとき、与えられた表には矛盾があるといいます。

• ある組 $(i,j)$ が存在して、人 $i$ が人 $j$ に勝ったが、人 $j$ が人 $i$ に負けていない
• ある組 $(i,j)$ が存在して、人 $i$ が人 $j$ に負けたが、人 $j$ が人 $i$ に勝っていない
• ある組 $(i,j)$ が存在して、人 $i$ が人 $j$ に引き分けたが、人 $j$ が人 $i$ に引き分けていない

制約

• $2≤N≤1000$
• $A_{i,i}$ は - である
• $i \ne j$ のとき、$A_{i,j}$ は W, L, D のいずれかである

入力

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

$N$ $K$
$A_{1,1}$ $A_{1,2}$ ​$\cdots$ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ ​$\cdots$ $A_{2,N}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ ​$\cdots$ $A_{N,N}$

出力

与えられた表に矛盾がないとき correct、矛盾があるとき incorrect と出力せよ。

入出力例

入力例 1

4
-WWW
L-DD
LD-W
LDW-

出力例 1

incorrect

入力例 2

2
-D
D-

出力例 2

correct

参加中に考えたこと

入力を二次元配列に入れた後、変数 $i,j$ を使って二重ループして、a[i][j]とa[j][i] の関係が正しいかを判定すれば良さそう。
ループは対角線上の片方だけでよく、 $i=j$ は-なので、$j$ のループは $i+1$ から始めれば十分。

C - NewFolder(1)

https://atcoder.jp/contests/abc261/tasks/abc261_c

Difficulty: 179

問題文

$2$ つの文字列 $A,B$ に対して、$A$ の末尾に $B$ を連結した文字列を $A+B$ と表します。
$N$ 個の文字列 $S_1$ $,…,S_N$ が与えられます。$i=1,…,N$ の順に、次の指示に従って加工して出力してください。

• $S_1 ,…,S_{i−1}$ の中に $S_i$ と同じ文字列が存在しないならば、$S_i$ を出力する。
• $S_1 ,…,S_{i−1}$ の中に $S_i$ と同じ文字列が $X$ 個 $(X>0)$ 存在するならば、$X$ を文字列として扱って $S_i +$ ( $+X+$ ) を出力する。

制約

• $1≤N≤2×10^5$
• $S_i$ は英小文字のみからなる長さ $1$ 以上 $10$ 以下の文字列

入力

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

$N$
$S_1$
​$S_2$
$\vdots$​
$S_N$

出力

問題文中の指示にしたがって、$N$ 行出力せよ。

入出力例

入力例 1

5
newfile
newfile
newfolder
newfile
newfolder

出力例 1

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

入力例 2

11
a
a
a
a
a
a
a
a
a
a
a

出力例 2

a
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)

参加中に考えたこと

連想配列を使えばよさそう。
mapで $S_i$ をキーに、$S_i$ の存在する数を値にする。出力したいのは $S_{i-1}$ までの数なので、ループの中で入力、存在する数のカウント、出力までを行えばいいかな。

考察・感想

今回のC問題は易しかった。B問題と同じくらいの時間で解けた。

D - Flipping and Bonus

https://atcoder.jp/contests/abc261/tasks/abc261_d

Difficulty: 801

問題文

高橋君が $N$ 回コイントスを行います。 また、高橋君はカウンタを持っており、最初カウンタの数値は $0$ です。
$i$ 回目のコイントスで表裏のどちらが出たかによって、次のことが起こります。

• 表が出たとき：高橋君はカウンタの数値を $1$ 増やし、$X_i$ 円もらう。
• 裏が出たとき：高橋君はカウンタの数値を $0$ に戻す。お金をもらうことは出来ない。

また、$M$ 種類の連続ボーナスがあり、$i$ 種類目の連続ボーナスではカウンタの数値が $C_i$ になるたびに $Y_i$ 円もらうことができます。

高橋君は最大で何円もらうことができるかを求めてください。

制約

• $1≤M≤N≤5000$
• $1≤X_i ≤10^9$
• $1≤C_i ≤N$
• $1≤Y_i ≤10^9$
• $C_1 ,C_2 ,…,C_M$ はすべて異なる。
• 入力はすべて整数

入力

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

$N$ $M$
$X_1$ $X_2$ $\dots$ $X_N$
$C_1$ $Y_1$
​$C_2$ $Y_2$
$\vdots$
$C_M$ $Y_M$
​

出力

高橋君がもらうことのできる金額の最大値を整数で出力せよ。

入出力例

入力例 1

6 3
2 7 1 8 2 8
2 10
3 1
5 5

出力例 1

48

入力例 2

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

出力例 2

5000000000

参加中に考えたこと

DPかなぁって当たりをつける。
縦軸はコイントスの回数で、横軸はカウンタの数値としてやればうまくいきそう。
基本的なDPの問題によくあるような右下になるほど値が大きくなるようなかたちにはならない。
DPの遷移としては、表が出た時はカウンタは1つ進み、裏が出た時は0に進むというかたちになる。
表が出た時はあわせてボーナスの加算も行うようにする。ここはmap使うと分岐がなくて済む。
裏が出た時は全てカウンタは0になるので、 $dp(i,0) = max(dp(i-1))$ となるようにする。
求める答えも同様に $max(dp(N-1))$ になる。

考察・感想

DPで用意する配列は2次元配列を用意する方法もあるが、1次元配列を2つ用意する方法もある。
この問題の値の更新の仕方としては、

$dp[i][j] = \begin{cases} max(dp(i-1)) &\text{j=0} \\ dp(i-1,j-1) + X_i + C_j &\text{j>0} \end{cases}$

となり、$dp[i]$ 行の値を求めるのに参照する値は $dp[i-1]$ 行だけなので、2行分のデータさえあれば事足りる。

2次元配列の方がプログラムは楽になると思うが、デバッグ時に必要な情報だけが出るのがメリットがあると感じていて自分は1次元配列2つで書いている。提出された回答一覧を見ると、メモリが100,000 KB以上なら2次元配列、3,000 KBとかなら1次元配列2つというのが見て取れる。圧倒的に2次元配列派が多い。

E - Many Operations

https://atcoder.jp/contests/abc261/tasks/abc261_e

Difficulty: 1261

問題文

変数 $X$ と、$X$ の値を変更する $N$ 種類の操作があります。操作 $i$ は整数の組 $(T_i ,A_i​)$ で表され、意味は次の通りです。

• $T_i = 1$ のとき、$X$ の値を $X and A_i$ に置き換える。
• $T_i = 2$ のとき、$X$ の値を $X or A_i$ に置き換える。
• $T_i = 3$ のとき、$X$ の値を $X xor A_i$ に置き換える。

変数 $X$ を値 $C$ で初期化した状態から、以下の処理を順に実行してください。

• 操作 $1$ を行い、操作後の $X$ の値を出力する。
• 続けて、操作 $1,2$ を順に行い、操作後の $X$ の値を出力する。
• 続けて、操作 $1,2,3$ を順に行い、操作後の $X$ の値を出力する。
• $\vdots$
• 続けて、操作 $1,2,…,N$ を順に行い、操作後の $X$ の値を出力する。

制約

• $1≤N≤2×10^5$
• $1≤T_i≤3$
• $0≤A_i<2^{30}$
• $0≤C<2^{30}$
• 入力に含まれる値は全て整数である

入力

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

$N$ $C$
$T_1$ $A_1$
$T_2$ $A_2$
$\vdots$
$T_N$ $A_N$

出力

問題文中の指示に従って $N$ 行出力せよ。

入出力例

入力例 1

3 10
3 3
2 5
1 12

出力例 1

9
15
12

入力例 2

9 12
1 1
2 2
3 3
1 4
2 5
3 6
1 7
2 8
3 9

出力例 2

0
2
1
0
5
3
3
11
2

参加中に考えたこと

論理演算の問題。操作はそのままビット演算するとして、どうやって計算量を抑えるんだ？
$i$ 行目の答えを求めるのに $i-1$ 行目を使うようなことをするのか、論理演算の式をまとめていくのか、指針が分からない。。

考察・感想

解説見てACまでさせた。ポイントとしては２点。

• AND,OR,XORは各ビットの値が変わるだけなので独立して考えられる
• 合成関数 $(f(x)=f_i \circ f_{i-1} \circ \dots f_1)$ を作る

ビットごとに独立して考える方針だと、操作後の値もそのままビットごとになりがちだと思う。
一発で出す方法は分かるとなるほどと思うがコンテスト中に思いつくのは難しそう。