AtCoder Beginner Contest 257 メモ(A-C)

今回の結果

2AC

C問題は落ち着いて解けばACできる問題だったかな。
Difficulty 600台がまだコンテスト中にACできない。

A - A to Z String 2

https://atcoder.jp/contests/abc257/tasks/abc257_a

Difficulty: 22

問題文

A を $N$ 個、B を $N$ 個、$\dots$、Z を $N$ 個この順に繋げて得られる文字列の先頭から $X$ 番目の文字を求めてください。

制約

• $1≤N≤100$
• $1≤N≤N×26$
• 入力はすべて整数

入力

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

$N$ $X$

出力

答えを出力せよ。

入出力例

入力例 1

1 3

出力例 1

C

入力例 2

2 12

出力例 2

F

参加中に考えたこと

計算で出来るだろうと思ってやったらWA出してしまった。xを-1するところが間違えててそこを見直してもいいけど、別の方法を考えた。
文字列の最大長が2600文字しかないし、実際に文字列作って配列の番号を指定して出力される方法のほうが確実かと思い、その方法に書き換えてACした。

B - 1D Pawn

https://atcoder.jp/contests/abc257/tasks/abc257_b

Difficulty: 91

問題文

$N$ 個のマスが左右一列に並んでおり、左から順にマス 1、マス 2、$\dots$、マス $N$ と番号づけられています。
また、$K$ 個のコマがあり、最初左から $i$ 番目のコマはマス $A_i$ に置かれています。
これらに対して、$Q$ 回の操作を行います。 $i$ 回目の操作では次の操作を行います。

左から $L_i$ 番目のコマが一番右のマスにあるならば何も行わない。
そうでない時、左から $L_i$ 番目のコマがあるマスの $1$ つ右のマスにコマが無いならば、左から $L_i$ 番目のコマを $1$ つ右のマスに移動させる。 $1$ つ右のマスにコマがあるならば、何も行わない。
$Q$ 回の操作が終了した後の状態について、$i=1,2,…,K$ に対して左から $i$ 番目のコマがあるマスの番号を出力してください。

制約

• $1≤K≤N≤200$
• $1≤A_1<A_2<\cdots<A_K≤N$
• $1≤Q≤1000$
• $1≤L_i≤K$
• 入力はすべて整数

入力

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

$N$ $K$ $Q$
$A_1$ $A_2$ ​$\cdots$ $A_K$
$L_1$ $L_2$ ​$\cdots$ $L_Q$

出力

$K$ 個の整数を空白区切りで一行に出力せよ。 ここで、$i$ 個目の整数は、 $Q$ 回の操作が終了した後の状態について、左から $i$ 番目のコマの番号を表す。

入出力例

入力例 1

5 3 5
1 3 4
3 3 1 1 2

出力例 1

2 4 5

入力例 2

2 2 2
1 2
1 2

出力例 2

1 2

入力例 3

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

出力例 3

2 5 6 7 9 10

参加中に考えたこと

問題文にある説明の通りの動きをするコードを書いて終わり。

C - Robot Takahashi

https://atcoder.jp/contests/abc257/tasks/abc257_c

Difficulty: 678

問題文

子供と大人があわせて $N$ 人います。$i$ 番目の人の体重は $W_i$ です。
それぞれの人が子供か大人かは、0 と 1 からなる長さ $N$ の文字列 $S$ によって表され、$S$ の $i$ 文字目が 0 であるとき $i$ 番目の人が子供であることを、1 であるとき $i$ 番目の人が大人であることをさします。

ロボットである高橋君に対して実数 $X$ を設定すると、 高橋君はそれぞれの人に対して、体重が $X$ 未満なら子供、$X$ 以上なら大人と判定します。
実数 $X$ に対して$f(X)$ を、高橋君に $X$ を設定したときに $N$ 人のうち子供か大人かを正しく判定できる人数で定めます。

$X$ が実数全体を動くとき、$f(X)$ の最大値を求めてください。

制約

• $1≤N≤2×10^5$
• $S$ は 0 と 1 からなる長さ $N$ の文字列
• $1≤W_i ≤10^9$
• $N,W_i$ は整数

入力

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

$N$
$S$
$W_1$ $W_2$ $\cdots$ $W_N$

出力

$f(X)$ の最大値を整数で一行に出力せよ。

入出力例

入力例 1

5
10101
60 45 30 40 80

出力例 1

4

入力例 2

3
000
1 2 3

出力例 2

3

入力例 3

5
10101
60 50 50 50 60

出力例 3

4

参加中に考えたこと

$X$ が実数全体を動くとあり、入力例１において $f(x)$ の最大値が4となるxの範囲は $45 < x \leq 80$ である。
ただ、$f(x)$ の値が変わるのは $w_i$ を跨ぐときだけなので、各 $w_i$ と $min(w_i)$ の左側、 $max(w_i)$ の右側についてだけ計算すればよい。
あとこの類の問題はソートをするのが定石に見えたのでmapにデータを入れておいた。

単純に $N$ の各要素について順番に正しく判定できる人数を計算すると、計算量は $O(N^2)$ でTLEする。
そこでソート済であることを利用して、左から順番に見ていくことを考えた。
ある $x$ において、 $x$ より左側にある大人の数と子供の数、$x$ 以上の大人の数と子供の数が分かれば $O(N)$ の計算量でできそう。

ここで悩んだのが、データをどう持たせるかという点。
大人と子供を別々の配列に持つ方法と、pairで持たせる方法とでどっちが楽にできそうか？
配列を2つ持つほうで進めていったが、バグが直せずタイムアップ。

考察・感想

方針は恐らくあっていると思うので、実装の仕方を考えなおしてACできた。
2つの配列を同時に見るのところのコードがややこしくなってたので、大人・子供の配列とは別に、ループで使う用の配列を持つことにした。

例１では以下のようなデータを作る。
配列１：大人の体重データ
　[30,1], [60,1], [80,1]
配列２：子供の体重データ
　[40,1], [45,1]
配列３：ループ処理用
　[0,30,40,45,60,80]
　※0を入れないと、全員大人の場合に正しい答えが出ない

これと、大人の人数、子供の人数、ループ処理中に数えるための大人の人数、子供の人数の４つの変数を持っておく。
配列3を使って次の値に進む度に、その値にある大人の人数と子供の人数を追加していくことで、簡単な計算で正しく判定できる人数を計算できる。

計算量はソートしているので $O(N log N)$ でしたね。