2022-09-13

AtCoder 黄色になりました

ReiVindicatio(@RVindicatio)です. 　先日のABC268でやっと黄色になれたので, 自分語りをしようと思います.

プログラミングをはじめて1年9ヶ月, 青色から1年2ヶ月でした.

解いた問題数

これに Codechef や LeetCode などの solved を足すので、大体 4300 問くらいだと思います。青達成時が 1800 問程度だったので、新たに 2500 問くらい解いたということですね。さすがに黄色達成までに解いた問題数ではかなり上位の方だと思います。

やったこと

解き直しとかは全くやってません。

ABC　〜黄色埋め

ABC の黄色 diff までの問題を全て埋めました。やったのは 1 年前とかなので、正直よく覚えていません。効果はあった気がします。AtCoderは特に日本語解説が豊富なので、詰まることなく進められるのが良い点ですね。

Codeforces Div3 全埋め

おすすめ１。Codeforces の Div3 にある問題を全て埋めました。

Div3 の問題は難しいデータ構造やアルゴリズムを必要とする問題が存在せず、使ってもせいぜいセグ木、SCC、dsu くらいまでです。それよりかは様々な小問題の実装を何度もやらされることになるので、細かな実装速度の向上や考察ステップの省略が行えるようになります。「考えれば実装できるけどいちいち時間がかかってしまう」みたいな場面によく遭遇する人には強くお勧めします。Div3 自体比較的新しいため、カスみたいな問題は少ない印象です。

解説ブログも書いていましたが、普通に飽きたのと、解説書いてるより問題を解いた方が面白いことに気づいたので途中でやめました。

Codeforces ECR 無限バチャ

おすすめ２。ECRのバチャをたくさんやりました(80 回くらい？)。

ECR はその名の通り Educational な問題が多い気がします。特に~ECR50 くらいまではそれが顕著で、中難易度典型アルゴリズムの練習になります。知ってるんだけどまだ慣れてないアルゴリズム(自分の場合だと、行列累乗、二重頂点連結成分分解、マージテク、フロー、遅延セグ木、畳み込み、Mo、区間をsetで管理するやつなど)に慣れておく、といった使い方ができます。

ECRをしばらくやった後は、ABCのFまでで「知識が足りなくて解けなかった」みたいなことがなくなった気がします。

Codeforce Div2 無限バチャ

Div2のバチャをたくさんやりました(30回くらい？)。

もし ABC を主眼に置いているなら、Div2 よりも ECR や Div3 のバチャを優先するべきだと思います。どちらかというと ARC に問題は近く、Div2 をしばらくやると ARC で大負けしなくなりました。

わからん問題の公式解説がよくわからんとき、解説ブログを検索しても中国語のブログしか出てこないような場面に何度も出会したので、精進はなかなかしんどかったです。

出れるコンテストには基本全部でる

AtCoder だけではなく、Codeforces、Codechef、TopCoder、LeetCode など予定が合うコンテストは全て出ました。上位勢は僕以上に出ているので、どうやって時間を捻出しているのか不思議でたまりません。

ABC 皆勤

実は AtCoder を始めた ABC185 から ABC268 までの 84 回の ABC に全て rated で出ています。それだけ人生における優先度が高かったわけですね(クリスマスですらABCのために予定を断りました)。個人的には、今日はなんとなく unrated にしておこうとか、実力が上がるまでは一旦コンテストに出ないでおこうみたいな考え方は、成長に全く寄与しないと思っています。

黄色になるには

4300 問解いてください。

2022-03-25

Codeforces Round #598 (Div. 3)　F. Equalizing Two Strings

問題概要

長さ $n$ の文字列 $s, t$ が与えられる. ある長さ $len$ を選び, 長さ $len$ の部分列を反転させる操作を $s, t$ の双方に行う( index はそれぞれで選んで良いが, 必ず同じ長さを反転させる必要がある).

$s, t$ を一致させることができるか？

問題へのリンク

制約

$1 \le n \le 2 \times 10^5$

解法

まず, 構成している文字が違う場合は明らかに NO なので, そのような場合は最初に除きます.

$s$ を $t$ に一致できるか？という問題を解く代わりに, $s, t$ 双方に操作をすることによって両方を同じ文字列にできるか？という問題を考えましょう.

操作の性質上隣接要素についての swap が可能なので, $s, t$ のどちらかはソートすることができます. もし, $s$ (及び $t$ )が重複する文字を持っていれば, 隣接 swap を偶数回・奇数回のどちらを行うことでも文字列をソートできるので, 必然的に答えは YES になります.

逆に重複する文字がない場合, ソートするために必要な swap 回数の偶奇は文字列の転倒数の偶奇に一致することを思い出せば, $s, t$ の転倒数の偶奇が一致しているかどうかが YES と NO を分けることがわかります.

実装

転倒数は BIT などを用いることにより効率的に計算することができますが, この問題においては転倒数を計算する必要がある文字列の長さは最大でも $26$ なので, 愚直に計算すれば良いです.

Submission #147843509 - Codeforces

2022-03-07

Codeforces Round #598 (Div. 3)E. Yet Another Division Into Teams

問題概要

$n$ 人の人がおり, $i$ 番目の人の能力は $a_i$ である. ここから任意の個数のチームを作成するが, 各チームの人数は $3$ 人以上でなければならない.

チームの多様さをそのチームに属する人間の能力の最大値と最小値の差とする時, 全てのチームの多様さの和を最小にするにはどのように割り振れば良いか？

問題へのリンク

制約

$3 \le n \le 2\times 10^5$
$1 \le a_i \le 10^9$

解法

まず, 人間の能力でソートしましょう. 能力が小さい方からチームをまとめていく時, 実はチームの大きさは最大でも $5$ 人になることがわかります. この事実を簡単に以下に示します.

$a_1, a_2, a_3, a_4, a_5, a_6$ の $6$ 人でチームを組むことを考えます. なお, $a_i$ は広義単調増加です. このチームを $a_1, a_2, a_3$ と $a_4, a_5, a_6$ の二つのチームに分割する時, 分割する前と後で多様さは $a_6 - a_1$ から $a_6 - a_4 + a_3 - a_1$ に変化します. $a_i$ の単調性から, $- a_4 + a_3 \ge 0$ が成り立ちます. よって, 可能な限りチームを分割するのが最適です.

これに基づけば, $n$ が $3$ の倍数の時は全て $3$ 人チームにして仕舞えば良いです. $3$ の倍数ではない時は面倒なので, dp をしましょう. $dp[i] :=$ ( $i$ 人めまででチームを作った時の多様さの合計の最小値)とすれば, 自分が属しうるチームは定数個しかないので遷移も定数個しかないです.

実装

復元パート、いる？

Submission #147742980 - Codeforces

2022-03-01

Codeforces Round #590 (Div. 3)E. Special Permutations

問題概要

$p_i(n)$ を次の順列で定義する : $p_i(n) = \{i, 1, 2, \cdots, i-1, i+1, \cdots, n\}$ ( $i$ 番目を先頭に移動しただけ)

$pos(p_i(n), j)$ を, $p_i(n)$ における $j$ の index 番号とする. このとき, 長さ $m$ の数列 $x$ に対して $f$ を

$f(p_i(n)) = \sum_{j=1}^{m-1} |pos(p_i(n), x_j) - pos(p_i(n), x_{j+1})|$

と定義する. $f(p_1(n)), f(p_2(n)), \cdots, f(p_n(n))$ をすべて求めよ.

問題へのリンク

制約

$1 \le n, m \le 2\times 10^5$
$1 \le x_i \le m$

解法

$pos(p_i(n), j)$ がどのような値をとるかを考えましょう. これは, $i=j$ のとき $1$ , $i \lt j$ のとき $j$ , $i \gt j$ のとき $j+1$ です. よって, 各 $x_i$ に対して $pos(p_j(n), x_i)$ がとる値は $3$ 種類しかないので, 答えの配列に対応する区間の値を足しこめばいいです. imos 法で何とかします.

実装

Submission #147560038 - Codeforces

2022-02-28

Codeforces Round #560 (Div. 3)F2. Microtransactions (hard version)

問題概要

$n$ 個の商品があり, 各商品の値段は基本 $2$ 円である. 長さ $n$ の数列 $k$ が与えられ, これは $i$ 番目の商品を $k_i$ 個だけ購入する必要があることを示している.

上記とは別に, $m$ 個のセール情報 $d, t$ が与えられる. $j$ 番目のセール情報は, $d_j$ 日目に $t_j$ 番目の商品が $1$ 円で購入できることを示している.

$1$ 日の始まりに $1$ 円だけ入手することができる. 1日に何個でも商品を購入できるとき, $k$ の条件をすべて満たすには最低何日かかるか？

問題へのリンク

制約

$1 \le n, m \le 2\times 10^5$
$0 \le k_i \le 2\times 10^5$
$k_i$ の総和は $1$ 以上 $2\times 10^5$ 以下
$1\le d_j \le 2\times 10^5, 1 \le t_j \le n$

解法

明らかに二分探索です. $T$ 日で条件を満たせるか？という判定問題を考えましょう.

各商品のセールのうち, その商品の一番最後のセールで商品を買い, それより前のセールでは商品を買わないのが最適です(後にまわすことによるデメリットがありません). よって, 全ての商品につき一番最後のセールで買えるだけ買うのを繰り返し, 最終日に残金で帳尻合わせをします. ここで条件を満たせるなら Yes, 満たせないなら No をすればいいです.

実装

Submission #147408396 - Codeforces

2022-02-28

Codeforces Round #555 (Div. 3)F. Maximum Balanced Circle

問題概要

長さ $n$ の数列 $a$ が与えられる. この中から任意の個数の数を取り出し, 自由に並び変えたうえで円環状に配置する. このとき, 隣り合う数の絶対値の差が $1$ 以下になるようにしたい.

このような並べ方のうち, 最大のものは何か？

問題へのリンク

制約

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 2\times 10^5$

解法

耳 dp 感ないですか？ないですね...

絶対値の差が $1$ 以下なので, $0$ でもいいことに着目します. このことから, 同じところを往復する意味がないです. ( $1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \cdots$ とできるなら, $1 \rightarrow 1 \rightarrow 2 \rightarrow 2 \rightarrow 1 \cdots$ とすればいいです. )

よって, 使用する数字の最小値, 最大値をそれぞれ $l, r$ とすれば, ありうる数字の並びのパターンは以下の通りになることがわかります :

$l$ から出発し, $l \rightarrow l+1 \rightarrow \cdots \rightarrow r \rightarrow r-1 \rightarrow \cdots \rightarrow l+1$ と移動
$i~(l \lt i \lt r)$ から出発し, $i \rightarrow i+1 \rightarrow \cdots \rightarrow r \rightarrow r-1 \rightarrow \cdots \rightarrow l \rightarrow l+1 \rightarrow \cdots \rightarrow i-1$ と移動
$r$ から出発し, $r \rightarrow r-1 \rightarrow \cdots \rightarrow l \rightarrow l+1 \rightarrow \cdots \rightarrow r-1$ と移動

ここで, 数字を連続させていいことを思い出せば, 2. と 3. は1. に帰着できることがわかります. よって, 1. のパターンだけ考えればいいです.

1. のパターンはどのように構築できるでしょうか. 区間 $l, r$ で1. が構築できる条件は, $l, r$ が $1$ 個以上存在し, $l \lt j \lt r$ を満たす $j$ が $2$ 個以上存在していればいいです(間の区間は往復しなければならないことに注意します). よって, $l$ を固定すれば, 自分より大きく, 最初に個数が $1$ 個以下になる数字 $r$ が高速に得られれば, その間の数字はすべて使うことができるのでできる円環の大きさを累積和を用いて計算できます. 自分より大きく最初に個数が $1$ 個以下になる数は, $a_i$ が十分小さいことから前計算で累積的に計算しておきます.