AtCoder Grand Contest 028 (AGC028)に参加しました!
AtCoder Grand Contest 028 旧版
AtCoder Grand Contest 028 beta版
解けた問題だけ解説をしていきますー
要項
AtCoder Grand Contest 028
rated
10/13(土) 21:00 ~ 23:30 (150分)
300-600-700-900-1400-2500(1000) (6問)
ペナルティ: 5分
方針
もうレート落ちなきゃ良いわ(次の日が秋季博麗神社例大祭の為)、300-700解いて終わらせる
A - Two Abbreviations
まず、条件1より最小のの候補は
です。
この時、任意のに対して
の
番目と
の
番目は同じ位置になる為、この文字が同じである必要があります。
ところで、全てのの候補は
の定数倍ですが、何倍にしても同じ位置になる文字は同一です。
よって、のみを愚直に調べれば良いので、計算量は
です。
ちなみに、は最大で
になるため、オーバーフローには注意しましょう。
B - Removing Blocks
全てのコストの合計……のような、全通りの合計を行った場合は左→右と右→左の両方が含まれるので、順番を考慮しなくていいことに注目します。
まず、そのままだと分かり辛いので仮に左端の1個についてコストを計算するものとしましょう。
この時、まず自分自身とは必ず連結しているので、自分自身は回のコストが足されます。
次に、隣のブロックと計算する場合、自分が先に選ばれた場合のみコストが足されるのでとなります。
同様に個離れたブロックについては、全
個のブロックの中で自分が最初に選ばれた時のみコスト計算するので
回となります。
ということは、左から番目のブロックのコストは
回計算されるので、この値に
を掛ければ良いです。
この計算は、累積和を用いてを予め求めておけば
で出せるので、後は全ての
に対して計算すれば
で求めることができます。
C - Min Cost Cycle
まず、制約より丁度個の重みの総和が答えになることが分かります。
理想は重みが小さいもの個のみで構成することですが、それは可能でしょうか?
まず、各頂点について重みの計算は次の4通りが考えられます。
と
のどちらも使われない
が使われ、
が使われない
が使われ、
が使われない
と
のどちらも使われる
さて、今重みの小さいもの個を仮に取った場合を考えましょう。
この時、接続可能な遷移はどれでしょうか?
列挙すると、、
、
、
、
、
、
、
の8通りあります。
ここで、鳩の巣原理より必ず1のパターンと4のパターンは同数個あることに着目すると、と繰り返すことで1及び4の個数は任意に減らすことができます。
また、、あるいはその逆を行うことで1か4のパターンが存在すれば2と3の個数も任意に減らすことができるので、もし両方が使われる場合はその瞬間に最小の重み
個を選べば良いことになります。
後は2と3のみが存在するパターンを考えます。
まず、遷移を見れば分かるように2のみ、3のみの場合は問題なく解けます。
逆に、そうでない場合はどうやら最小の重み個では解けないようです。
そこで、この場合は仕方ないので第番目の重みのものを追加し、第
番目のものを除外することで解けます。
……と、第番目と第
番目が同じi番目の辺だと意味がないので、この場合は第
番目を外して
番目の重みの頂点に変更するか第
番目を外して
番目の頂点に変更するか、好きな方(というかより小さい方)を選びましょう。
計算量はソートしてから貪欲なのでです。
結果
o-x--- 1完(200点) 88:06(1WA) / 93:06
1195位 パフォーマンス: 953
レート: 1684→ 1628(-56)
感想
うにゅあー!?
大爆死じゃん!何やってんの!
えー、証明はちゃんとやってから解きましょう()