AtCoder Beginner Contest 260 参加記

ooooox--

A問題. 場合分けを極力避けた実装をした. 各文字が何回出現したかを管理.

B問題. 実装量が大変なことに. std::sort に投げる比較関数を3つも書いた.

C問題. 再帰関数で書こうかとも思ったが, 冷静になるとレベルが $1$ 減ると石がどのくらい増えるかが分かる. 赤, 青の宝石の数を $A,B$ とするとレベルが $1$ 減るごとに $(A,B)\longmapsto (A(X+1)+B,AXY+BY)$ となる.

D問題. std::set を用いて山の先頭をシュミレーション. atcoder::dsu を用いて山の中身とサイズが管理できる. ちょっと前にstd::set の lower_bound を履修したので簡単に書けた. 山のサイズが $K$ になったら ans[dsu::leader(p[i])]=i などとして, 最後に rep(i,n)ans[i]=ans[dsu::leader(i)] などとすればよい.

E問題. 条件を満たす区間の右端を伸ばしてもやはり条件を満たす. よって左端を固定したとき条件を満たす最も左の右端を見つけたい. 素直に左端を昇順に動かしていく. はじめは最も左の右端は $\max _i(A_i)$ であるが, 左端が $A_i$ を超えた $i$ については $\max _i(B_i)$ を計算する必要がある. コンテスト中は思考を停止してセグメント木を用いたが本当に素直に処理すれば良い.

F問題. $T$ が小さいことに注目して $\Theta(T^2)$ の解法を考えたが分からず. ひとつ見つけさえすればいいので鳩の巣原理に思いを馳せるも $V_2$ 側の要素を固定した全探索が頭から離れずいい案が思い浮かばなかった. upsolve で冷静になると, $T^2$ はループ側ではなく鳩の巣側にすれば良いことに気づく. つまり, $V_2$ の中から $2$ 点選ぶ方法は高々 $T^2$ 回なので, $T^2+1$ 回 $V_2$ の中の $2$ 点を見ると必ず既に見たことがある $2$ 点が出てくる. よって, $V_1$ の頂点を順に見て, その頂点に接続する $V_2$ の頂点のうち任意の $2$ 点を見れば良い. 見たことがあるかを管理する配列には $V_1$ のどの頂点に見られたかを記録すれば良い.

G問題. コンテスト中はほとんど見ていないし考察も全くしていない. 変な imos法と呼ばれているらしい. 階段状の領域への加算を斜め方向に累積和を考えてimos法と同じように処理すれば良い. 累積和をとる回数に対して線形 ($2$ 倍)の点への加算をすれば良いので大変有用だと思う. 今回は $3$ 方向に累積和を取るので $6$ 点に加算をした.

Ex問題. 見ていません.