Codeforces Round #579 (Div. 3)
参加しました。
A. Circle of Students
問題：長さｎの順列を環状に並べたとき、ソート済みになるかを調べよ
考察：
これめっちゃ時間かかっちゃいました。
色々解法あると思うんですけど、なんにせよ場合分けある程度しなきゃいけなくてしんどいですね。
1の位置を探して前後が2かどうか、1ずつ移動させて比較ってやりました。
%nではみ出した部分に対応できるのは典型っぽい。
B. Equal Rectangles
問題：辺が4n本与えられる。n個の長方形を作り、全ての面積が等しくすることはできるか
考察：
まず対面する辺をペアにします。
最大の辺と最小の辺で長方形を作り、その面積に他の物をそろえるべきです。
簡単に証明すると、最小のもの*最大じゃないものでマッチさせるとします。このとき、最大のものとどれをマッチさせても上記の長方形の面積を超えます
考察パートはすぐ終わったんですけど実装に時間をかけてしまいましたね…
シンプルに昇順に並べて、前と後ろから順に見てもよかったです。
C. Common Divisors
問題：N個の整数の公約数の個数を求めよ
考察：
問題に解法が書いてあるので実装するだけです
ユークリッドの互除法を使って最大公約数を求めて、その約数の個数を求めましょう
計算量はO(max(a)*0.5)です
D1. Remove the Substring (easy version)
問題：文字列ｓとｔが与えられる。ｔから連続する部分列を１個削除する。これを文字列ｓの部分列にしたい。削除してもよい最長の長さを求めよ
考察：
D１は制約が小さいので愚直にしてOKです。
ｓの[i,j]を削除などとして全探索しましょう
D2. Remove the Substring (hard version)
制約が大きいです。
前からk個削除、後ろからk個削除、間をk個削除の3通りにわかれます。本質的に同じなので、最後の間を削除する場合を考えます。
[i,j]を削除したとします。このとき[0,i)がｔの接頭辞と一致する長さ、(j,|s|)がｔの接尾辞と一致する長さの和は|t|を超えます。
あらかじめ両者を計算しておきます。前半を全探索し、それに対して後半を二分探索で|t|を超える最も端に近いindexを求めます
これでO(|s|log|s|)で解けました。
前計算する一致部分ですが、累積和のように計算できます
frt[i]:s[i]までに一致するｔの接頭辞の長さ
frt[i+1]=frt[i] if s[i+1]!=t[frt[i]+1]
frt[i+1]=frt[i] else
こんな感じで更新していけます。O(|s|)で求まるためボトルネックにはなりえません。
E. Boxers
問題：N個の整数aiが与えられる。整数1つにつき1回以下、-1か+1をできる。ただし全ての整数が0以下にはできない。distinctにできる最大の個数を求めよ
考察：
貪欲です。ソートして前から見ます
もし1つ前より+2以上なら-1してよいのでします。
1つ前と等しいなら+1します。
厳密な証明は省きますが、この方法で最適になります。
イメージは後ろがどんなパターンでも、この方法以外<=この方法の回数を示します
F1. Complete the Projects (easy version)
問題：タスクがN個与えられる。必要な能力がai、得られる能力変化がbiである。全てのタスクをこなせるか判定せよ。ただし全体を通して能力が負になってはならない。
考察：
まず正のbiを持つタスクは後回しにする理由がないです。
またaiを昇順にやればよいです。もしaiが小さいタスクを後回しにしてもできなくなることはないからです。(bi>=0のものに限り）
bi<0のタスクを考えればよくなりました。
F1でのみ使える解法：
ai降順にこなします。
もしaiが大きいものを後回しにしても、そのタスクをこなせるタイミングは来ません。
したがってこの方法で答えが求まります。
F2. Complete the Projects (hard version)
問題：こなせるタスクを最大化せよ
考察：
bi>=0のものはF1と同じです
bi<0のものには工夫が必要です。
dp[i]：i個こなしたときの能力の最大値、こなしたタスクの集合
遷移はn^2で状態はnなのでO(n^3)で解くことができます
能力を高く保つか、タスクを増やすかが最適行動で、前者がiが小さいもの、後者がiが大きいもので持つことができています。
厳密な証明ができてないです。嘘解法かも
感想
全完でした！うれしい！
難易度はABCと同じくらいでしょうか
問題数多いことと、前半から実装重めでABCより大変でした。
考察パートはABCより軽いので個人差出そうですね。
遅めの全完でしたがバチャの人除けば48位くらいでした。まあunratedなので自分自身unofficialですが。
cfで2桁順位は初めてなので結構嬉しかったです。
もうちょっとで院試が終わるので、たくさん精進したいです。いまも結構してるけど
