ABC457参加記

はじめに

こんにちは。
初めまして！ShoboiNamaeと申します。今回、入緑を記念して記事を書かせていただけることになりました！（やったね！）
新入部員として、当たり障りのないことを書いていければと思います。

結果サマリ

ABC457
WCPC参加人数: 6人
各問題の最速解答者(ペナルティ無し):

問題	参加者名	タイム	言語
A	nsubaru	0:25	Java
B	nsubaru	1:53	Java
C	ShoboiNamae	9:12	C++
D	ShoboiNamae	39:25	C++
E	nsubaru	97:45	Java
F	-	-	-
G	-	-	-

今週の出題

ABC457-A

問題文を表示

問題文
長さ $N$ の数列 $A = (A_1, A_2, ... , A_N)$ が与えられます。
その後に $1$ 以上 $N$ 以下の整数 $X$ が与えられます。
$A_X$ の値を出力してください。

制約

$1 \le X \le N \le 100$
$1 \le A_i \le 100$
入力される値はすべて整数

入力
$N$
$A_1 \;\; A_2 \;\; ... \;\; A_N$
$X$

出力
$A_X$ の値を出力せよ。

A問題は1次元の配列に入力して、添え字が0から始まることに注意して出力することで解けました。

配列を使わないこともできます！（時間の無駄）

配列を使わないコードはこちら（C++）

ABC457-B

問題文を表示

問題文
$N$ 個の数列 $A_1, A_2,..., A_N$ が与えられます。
数列 $A_i$ の長さは $L_i$ であり $A_i = ( A_{i, 1}, A_{i, 2},..., A_{i, L_i} )$ です。
その後、整数 $X, Y$ が与えられます。 $A_{X, Y}$ の値を出力してください。

制約
$1 \le N \le 2 \times 10^5$
$1 \le L_i$
$L_i$ の総和は $2 \times 10^5$ 以下
$1 \le A_{i, j} \le 1000$
$1 \le X \le N$
$1 \le Y \le L_X$
入力される値はすべて整数

入力
$N$
$L_1 \;\; A_{1, 1} \;\; A_{1, 2} \;\; ... \;\; A_{1, L_1}$
$L_2 \;\; A_{2, 1} \;\; A_{2, 2} \;\; ... \;\; A_{2, L_2}$
$⋮$
$L_N \;\; A_{N, 1} \;\; A_{N, 2} \;\; ... \;\; A_{N, L_N}$
$X \;\; Y$

出力
$A_{X, Y}$ の値を出力せよ。

Aと同様に配列の操作が本質の問題ですが、こちらは2次元配列を使う問題でした。
数列 $A_i$ の長さがそれぞれ違うので入力が複雑になるところが難しかったと思います。

解説を読んでみると、固定長配列を作ろうとした人がWAになるような問題設定にされていたようです。よく考えられてるなあ。

ABC457-C

問題文を表示

問題文
整数 $N, K$ と $N$ 個の整数列 $A_1, A_2,..., A_N$ 、長さ $N$ の整数列 $C = (C_1, C_2,..., C_N)$ が与えられます。整数列 $A_i$ の長さは $L_i$ であり $A_i = (A_{i, 1}, A_{i, 2},..., A_{i, L_i})$ です。また、 $1 \le K \le \sum_{i=1}^N (C_iL_i)$ が保証されます。
$A$ と $C$ から以下の手順で整数列 $B = (B_1, B_2,..., B_{\sum_{i=1}^N (C_iL_i)})$ を構成します。

$B$ を長さ0の整数列とする。
$i = 1, 2,..., N$ $i = 1, 2, ..., N$ の順に以下の操作を行う:
- $B$ の末尾に $A_i$ を連結させる操作を $C_i$ 回行う。

$B_K$ の値を求めてください。

制約

$1 \le N$
$1 \le L_i$
$\sum_{i=1}^N L_i \le 2 \times 10^5$
$1 \le A_\{i, j\} \le 10^9 \;\; (1 \le j \le L_i)$
$1 \le C_i \le 10^9$
$1 \le K \le \sum_{i=1}^N (C_iL_i)$
入力される値はすべて整数

入力
$N \;\; K$
$L_1 \;\; A_{1, 1} \;\; A_{1, 2} \;\; ... \;\; A_{1, L_i}$
$L_2 \;\; A_{2, 1} \;\; A_{2, 2} \;\; ... \;\; A_{2, L_2}$
$⋮$
$L_N \;\; A_{N, 1} \;\; A_{N, 2} \;\; ... \;\; A_{N, L_N}$
$C_1 \;\; C_2 \;\; ... \;\; C_N$

出力
答えを出力せよ。

解説文を表示（長くなったのでたたみました）

この問題は入力や数列のある要素の値を求める点でB問題に似ていますがだいぶ難易度が違います。
愚直に数列

B

を作ると間に合わないorメモリ超過するので数列Bを作らずに解く工夫が必要でした。

まず、「 $B$ の末尾に $A_i$ を連結させる操作を $C_i$ 回行う」という点に着目します。すると、数列 $B$ の中に「 $A_i$ が繰り返されている部分」が、 $i = 1$ から $i = N$ までの $N$ 箇所あることが分かります。
このとき、数列 $B$ の「 $A_i$ が繰り返されている部分」を、数列 $B$ の第 $i$ 群と定義します。数列 $B$ の第 $K$ 項が属する群と、その群における位置を求めます。
問題文から、第 $i$ 群の長さは $C_iL_i$ です。よって、第1群から第 $j$ 群の最後の要素までの項数は、 $(C_1L_1 + C_2L_2 + ... + C_jL_j) = \sum_{i=1}^j (C_iL_i)$ 項です。
このことから、数列 $B$ の第 $K$ 項が属する群を第 $m$ 群とすると、 $\sum_{i=1}^{m-1} (C_iL_i) \lt K \le \sum_{i=1}^m (C_iL_i)$ が成り立ちます。for文などで、 $K \le \sum_{i=1}^m (C_iL_i)$ が満たされる間 $m$ を1から増やしていくことで $m$ を求めることができます。
$m$ が分かってしまえば群の中の第何項目なのかは、 $K - \sum_{i=1}^{m-1} (C_iL_i)$ で簡単に求まります。
肝心の出力すべき要素についても、第 $m$ 群で長さ $L_m$ の数列 $A_m$ が繰り返されていることを考えると、 $K - \sum_{i=1}^{m-1} (C_iL_i)$ を $L_m$ で割ったあまりを考えればよさそうです。
ただし、大抵のプログラミング言語の配列は 0-indexed （添え字が0始まり）なので、添え字を指定するときには注意が必要です。

と、なぜか無駄に解説を書いてしまったのですが、本番中はこんなに考えてません。
私は読解力がとても低いので問題文を読むのに一番苦労しました。あと、最後の添え字もなんとなくでやってしまった。通ったからいいけれども。

あと、全然関係ないんですが、0-indexedって競プロ界隈限定の呼び方なんですかね? 検索しても競プロのサイトばかりヒットするのはなぜだろう…

まとめると、この問題は難しかったということです。

ABC457-D

問題文を表示

問題文
長さ $N$ の数列 $A = (A_1, A_2,..., A_N)$ と整数 $K$ が与えられます。
あなたは次の操作を0回以上 $K$ 回以下行うことができます。

$1 \le i \le N$ を満たす整数 $i$ を1つ選び、 $A_i$ に $i$ を加える。

操作後の数列に対する $\underset{1 \le i \le N}{\min} A_i$ としてありうる最大値を求めてください。

制約

$1 \le N \le 2 \times 10^5$
$1 \le A_i \le 10^{18}$
$1 \le K \le 10^{18}$
入力される値はすべて整数

入力
$N \;\; K$
$A_1 \;\; A_2 \;\; ... \;\; A_N$

出力
答えを出力せよ。

またまた数列が出てきました。今日は数列デーなのか?
私は先週のABCでD問題が解けなかったので何としても解きたいところでした。
まだまだ経験が浅く、コンテスト中は「DはDPのD!」とか言ってDPを考えていましたが、途中で天啓があり、にぶたんだと確信したので爆速でコードを書き、しっかりオーバーフローでWAになって踊りました。
その後、考えるのを放棄し、 __int128_t 型を使うという脳筋プレーでACできました。なので、今回一番面倒だったのは __int128_t の出力関数を作ることでした。
といっても、10で割ってあまり出力して10で割って…を繰り返すだけの関数ですが。

Pythonはいいよなあ。デフォルトが多倍長整数で。

後から聞いた話ですが、最小値の最大化とか、最大値の最小化とか、そういう類の問題は大体にぶたんらしいです。もしにぶたんできなかったら、その後にDPとか貪欲を考えるのがいいそうです。
やっぱり O(log N) は魅力的だー。

ABC457-E

問題文を表示

問題文
$N$ 個のマスが左右一列に並んでいます。左から $i$ 番目 $(1 \le i \le N)$ のマスをマス $i$ と呼びます。

$M$ 枚の布があり、布 $i \;\; (1 \le i \le M)$ を敷くとマス $L_i$ からマス $R_i$ までを覆うことができます。

$Q$ 個のクエリに答えてください。 $q$ 番目 $(1 \le q \le Q)$ のクエリでは整数 $S_q, T_q$ が与えられるので、以下の問題に答えてください。

$M$ $M$ 枚の布の中からちょうど2枚の布を選んで敷くことで、以下の条件を満たすことができるか判定せよ。
- マス $S_q$ からマス $T_q$ までは1枚以上の布で覆われており、それ以外のマスは布で覆われていない。

制約

$1 \le N \le 2 \times 10^5$
$2 \le M \le 2 \times 10^5$
$1 \le L_i \le R_i \le N$
$1 \le Q \lt 2 \times 10^5$
$1 \le S_q \le T_q \le N$
入力される値はすべて整数

入力
$N \;\; M$
$L_1 \;\; R_1$
$L_2 \;\; R_2$
$⋮$
$L_M \;\; R_M$
$Q$
$S_1 \;\; T_1$
$S_2 \;\; T_2$
$⋮$
$S_Q \;\; T_Q$

出力
各クエリに対する答えを改行区切りで出力せよ。
各クエリでは、条件を満たすように2枚の布を選ぶことができる場合は Yes を、できない場合は No を出力せよ。

私はコンテスト中に解けませんでした。ランキングを見てみると、 nsubaru 先輩が解いてる!! さすがすぎる!!
一応私がコンテスト中に考えたことを書いておきます。

実行時間が2.5秒と、少し長かったので重めの計算量を通すと推測し、前処理ですべての覆える範囲を探索するコードを提出しましたがもちろんTLEでした。さすがに O(M^2) は通らない。
全探索じゃないっぽいなー、また二分探索? 今日二分探索デーか? というところまでは考えましたが、どうすればいいのか分からなかったので成す術なく終わりました。

ABC457-F以降

（これ以降の問題は割愛します）

最後に

E問題を解けなかったことが悔しいですが、なんとか入緑できてよかったです。

至らない点もあったかと思いますが、最後まで読んでいただきありがとうございました。