AGC029

https://atcoder.jp/contests/agc029/tasks

冷えました…

A
結局はWを動かす操作です。
B
面白い。1,2,3,....2^30のグラフを考えると、明らかに木です。問題のグラフは明らかにこのグラフの部分グラフなので森です。
あとはgreedyに取っていけばいいです。ただし2^nは注意。
C
重めのO(NlogNlogmaxA)書いたら落ちてかなしい。ちゃんとO(NlogmaxA)にしてAC。てか最初からstackで良いことにきづけないの良くない。
D
めっちゃ解かれてて焦ったけど誤読してた。高橋くんは常に動かさないといけなくて、青木くんはブロック上に来たら横移動をやめます。
E
1を根とした木の上に行きたい気分なので、後はsimulationすれば解けるかなあとは思いました。
F
全然つっかえなかったので成長だと思う。うまく問題を分析して妥当な予想を立てながら解けてキモチイ。

頂点vを取る操作はだいたい点集合からvを削除する操作に言い換えられます。(細かい条件はあるが)
全ての点集合について一つ点を削除することができれば成功で、これは二部マッチング問題です。

Codeforces Round #527 (Div. 3)

https://codeforces.com/contest/1092

だいぶ調子良かった。

A
WA on test1やったw
B
sort
C
長さN-1の文字列がほぼ答え。
D1
解いてないけど偶奇は見えた。
D2
一番短いものからやっていって、連結サイズが奇数になったらダメ。
E
これとけたのいいねえ。ある一つの点にすべての木をつなげればいいことがわかります。つなげるのは中心同士です。
F
一応全方位木DPなのか...?

Eが非自明感あったけど解けてよかったね。

2018-2019 Russia Open High School Programming Contest, J: Two Prefixes

https://codeforces.com/contest/1090/problem/J

考察有りライブラリ使いまくりで楽しい。
まず文字数を固定します。するとTを少しずつずらした時何通り同じ文字列があるかみたいな問題になります。
こんな感じです。

Tを1文字shift
S:aadaa   |
T: aaaaaba|
文字列はaaaaaaba
↓
Tを2文字shift
S:aadaa   |
T:  aaaaab|a
文字列はaaaaaaab

i文字shiftした時の文字列をDiとしてDiとDjが同じ場合は辺を張るようにしてグラフを作ります。
i < jとして、DiからつながっているDjを考えたいです。するとj-i = lずれた先でも同じということは文字列Tがcyclicになっていることを表します。
よってDiがDjと繋がる条件はTがl周期の文字列でありかつS[i,i+l]=T[0,l]となります。
するとDiとつながっているDjのうちjが最小のものをjmin、jmin-i=lminとすれば、Diはj=i+lmin,i+2*lmin,i+3*lmin...としかつながりません。
さらに、S[i,i+l]=T[0,l]の条件も合わせて考えれば、Diから辺を貼るのはDjminのみで良いことがわかります。
こうして作ったグラフは木なので結局(グラフの頂点数-辺の数)で異なる文字列の数がわかります。
あとは文字数で固定するのではなくshiftの文字数で固定してiterationを回せばできます。
高速化ですが、S[i,i+l]=T[0,l]を判定するのはSuffix array, cyclicになっているかはMP法を使えばいいです。計算量は全体でO(NlogN)で済みます。

int N, M;
string S, T;

int fd(const vi& vec, int a) {
	return upper_bound(all(vec), a) - vec.begin();
}

void solve() {
	cin >> S >> T;
	vi vt = MP(T);
	int N = sz(S), M = sz(T);

	SA sa; 
	vi vs;
	rep(i, 0, N) vs.pb(S[i] - 'a');
	vs.pb(26);
	rep(i, 0, M) vs.pb(T[i] - 'a');
	sa.init(vs, 27);

	vi vec;
	rep(i, 1, M + 1) {
		if(vt[i]) {
			vec.pb(i - vt[i]);
		}
	}
	ll res = 1ll * N * M;
	rep(i, 1, N) {
		int d = sa.common(i, N + 1);
		res -= fd(vec, d);
	}
	cout << res << "\n";
}

SRM埋め(4)

わりとeasyうまくなってきたし、easyとmediamともに残っているセットを残しておきたいので、mediam練習します。

SRM 732 mediam, hard
2問ともsurreal numberとかいう競プロではあまり馴染みのない道具を使う。知ってる人は一瞬だけど知らない人は絶対解けない。さらにテストケースが弱かったらしく、hardで嘘解法が通ったらしい。ひどいね。topcoderさんこういうのだけはやめてください。

SRM 731 med
勉強になった。式が出てきてなかなかO(K^3)から改善できなかったんですが、うまく期待値に言い換えなおすと出来ました。出てきたものを精査するのは基本中の基本ですができてなかったね。

SRM 730 med
完全にごり押してしまった…。それっぽい辺張ってdp復元。もっとうまい方針でやりたかった。

SRM 726 med
よくあるやつ。重心(2つあるならどっちでも良い)からtourして最後に重心と隣の点で終わればいいです。

最小全域木

この記事は
https://adventar.org/calendars/3598
の6日目の記事として書かれました。
昨日の記事はsatosさんの独断と偏見による根津/本郷飯事情でした。

19erのomochana2というものです。
最小全域木を扱う際で有効な定理を紹介したいと思います。めっちゃ数学っぽい話になって申し訳ないです。結果だけ知りたかったら四角で囲ってある部分をサーっと読んでください。一番下に定理を使って解ける演習問題も置いといたので、よかったら解いてください。

要は、辺が最小全域木に含まれたり含まれなかったりするための条件を考えようぜって話です。
カット特性

辺のコストが全て異なるとする。 S空集合でも V全体でもない点の部分集合であるとし、辺 e=(v,w)は端点の一方が Sに他方が V-Sに属する辺のうちでコストが最小のものであるとする。すると、どの最小全域木も辺 eを含む。

図にするとこうなっています。
ここで辺 eのコストは e',fよりも小さいです。

軽く証明します。 e最小全域木に含まれていないとします。すると、 e'のような、 S V-Sにまたがり、かつ vから wへのパス上(図でオレンジ色で示してあります)にある辺が存在します。 e'を削除して、 eを追加しましょう。すると新しいグラフも全域木となり、元の全域木よりもコストが下がりました。これは仮定と矛盾するので証明完了です。
簡単に言えば eと、ある S V-Sにまたがる辺を交換しているわけですが、またがってさえすればどんな辺でもいいわけではないことです。実際 e fを交換してしまうと、閉路ができてしまい、全域木ではなくなってしまいます。

この定理を利用するとKruskal法やPrim法の正当性が出来ますが、ここでは割愛します。

閉路特性

辺のコストは全て異なるとする。 C Gの任意の閉路とし、 Cに属する辺で最もコストの大きい辺を eとする。このとき eはGのどの最小全域木にも属さない。

カット特性は最小全域木に含まれる辺の条件だったのに対し、閉路特性は最小全域木に含まれない辺の条件です。これもカット特性のように辺を交換することによって証明できるので考えてみてください。

カット特性と閉路特性の合わせ技
ここからがアツいです。上の2つの定理を使うとこんなことが言えます。

辺のコストは全て異なるとする。辺 e=(v,w)について、  eよりコストの小さい辺のみからなるパス P v wを結ぶことができる \Leftrightarrow  e G最小全域木に含まれない。

証明.

  1.  eよりコストの小さい辺のみからなるパス P v wを結ぶことができる。 \Rightarrow  e G最小全域木に含まれない。
  2.  eよりコストの小さい辺のみからなるパスで v wを結ぶことができない。 \Rightarrow  e G最小全域木に含まれる。

この1,2が示されれば証明できたことになります。 まず、 P eを加えると eがコスト最大であるような閉路が得られるため、閉路特性から e G最小全域木には含まれません。これで1は示されました。
逆に v w eよりコストの小さい辺のみからなるパスで結ぶことができないとします。点の集合 Sを、 eよりコストの小さな辺のみからなるパスで vから到達可能な全ての点の集合とします。すると、仮定から w \in V - Sです。また、 Sの定義から、一方の端点xが Sに属し、他方yが V-Sに属して、eよりコストの小さい辺 fは存在しません。もしそのような辺が存在したとすると、 x eよりコストの小さい辺のみからなるパスで vから到達可能であるので、 yもまた到達可能になり、 Sの定義に属するからです。これによりカット特性を使えば、2も示されたので証明完了です。

コストが同じ辺がある場合
コストが全て異なるなら場合分けが、

  1.  eよりコストの小さい辺のみからなるパス P v wを結ぶことができる。
  2.  eよりコストの小さい辺のみからなるパスで v wを結ぶことができない。
    の2つでよかったんですが、コストが同じ辺がある場合は、
  3.  e未満のコストの辺のみからなるパス P v wを結ぶことができる。
  4.  e未満のコストの辺のみからなるパスで v wを結ぶことは出来ないが、 e以下のコストの辺のみからなるパス P'では v wを結ぶことができる。
  5.  e以下のコストの辺のみからなるパスで v wを結ぶことができない。

と3つになります。ここで1と3、2と5が対応していることに注意します。

実は3と5は1,2の証明をほぼそのまま適用できます。よって結果も同じです
問題は4ですが、もし e最小全域木に含まれていないとするなら、最小全域木上のパス Q eとコストが同じ辺 e'が存在します。もし Q上に eよりも大きい辺 fが存在するならば e fを交換することによって、全域木のコストを下げることが出来てしまい矛盾します。よって Qにはコストが e以下の辺しかないことになりますが、4の仮定により、 e未満のコストの辺のみからなるパスは存在しないため、全域木の全ての点が互いに到達可能であるという条件から e'が存在します。よって e e'を交換することによって、 e最小全域木に含めることができました。
 e最小全域木に含まれているとすると、 P'上の eとコストが同じで、最小全域木上にない辺 e'が存在するので、これを eと交換すれば e最小全域木から除外できました。

以上より、4が成り立つときは、全ての最小全域木には eは含まれないが、 eを含む最小全域木は存在する、となります。証明できたことをまとめると、

グラフ G=(V,E)上の辺 e=(v,w)について、

  1.  e未満のコストの辺のみからなるパス P v wを結ぶことができる。 \Rightarrow  eを含む G最小全域木は存在しない。
  2.  e未満のコストの辺のみからなるパスで v wを結ぶことは出来ないが、 e以下のコストの辺のみからなるパス P'では v wを結ぶことができる。  \Rightarrow  e G全ての最小全域木には含まれないが、 eを含む G最小全域木は存在する。
  3.  e以下のコストの辺のみからなるパスで v wを結ぶことができない。  \Rightarrow  e G全ての最小全域木に含まれる。

となります。これがおそらく一番使いやすい形になっています。

演習問題

  1. 連結グラフG(全ての点が互いに行き来可能)が与えられる。Gの特定の辺 eが指定されるので eを含むGの最小全域木が存在するかどうか O(|V|+|E|)で判定せよ
  2. 最小全域木が複数あるかどうか判定せよ
  3. "ほぼ木"が与えられる。このグラフは連結であり、 |E|=|V|+8を満たす。この時最小全域木 O(|V|)で与えよ
  4. (難)(これも紹介したかった)最小全域木の辺 |V|-1本をコスト順に並び替えたものを aとする。ある全域木の辺 |V|-1本をコスト順に並び替えたものを bとした時、全ての 0 \leq i \leq |V|-2を満たす自然数 iに対し、 a_i \leq b_iを示せ(元ネタ:http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2012%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=MedianTree.pdf)

参考文献

  1. Jon Kleinberg, Eva Tardos(2008)「アルゴリズムデザイン」浅野 孝夫, 浅野 泰仁, 小野 孝男, 平田富夫訳, 共立出版

明日の記事はlmt-swallowさんの"Browsing History Leakage (Sniffing?) について書きます"です。楽しみですね。

SRM埋め(3)

SRM 714 easy
easyはこれくらいの難易度が良いよなぁ。何ターン目までに消さないといけないという条件が求まる。

SRM 713 easy
難しい。保留->わかったんですけど、easyにしては実装複雑すぎでは?と思ってkmjpさんの解説記事見たら全く同じでおったまげました。(p^d)^a=(p^e)^bみたいにpという一番簡単な形で累乗を表せばあとは適当にgcd取りながら計算していけばいいです。しかしこれがめんどくさい上に、工夫しないとO(n)になって死んでしまう。大変。

SRM 712 easy
良問。まず1ターン行動するとsumは2倍になることから何回行動するかはわかる。実験してみると2項係数がかかった式になるのでできる。Combinationをバグらせて遅かった。コード貼っときます。

ll C(int a, int b) {
	ll tmp = 1;
	rep(i, 0, b) {
		tmp *= (a - i);
		tmp /= (i + 1);
	}
	return tmp;
}

簡易版ですね。

SRM 711 easy
まずnがk桁1が連続するか見る。そうでなかったらk桁連続するところを1にしてそれ以降0にするのが最適。最初バグったコードを投げたけどなぜかsys test通った(えぇ…)

SRM 710 easy
できたんだけどこういう解法が怪しいやつは得意じゃない…。typeAとtypeBは可逆です。typeAのみでN-1に石を全部置けたらあとはtypeBでTに戻せばいいです。間隔的にはN-1以外のholeに作用させまくれば良さそうですが、実験してみるとそれでうまくいきそうなことがわかります。

SRM 709 easy
Aの要素が50以下なのでYのうち影響を及ぼすのは下6桁のみです。よってbitdpできます。

SRM 708 easy
constructive多すぎでは…similarityは減らしたくて、そうすると長さ1の文字列を並べるのが良いです。後はwxwxwx....みたいな文字列で帳尻合わせします。

SRM 707 easy
へびみたいにpathを蛇行させればいいです。実装まあまあ工夫できて結構早く通せた。

SRM 706 easy
混乱したのもあるけど無駄にdijkstra書いたせいで遅くなってしまった。ベルマンフォードは更新される数だけループする以外は、dijkstraの更新と同じことをちゃんと覚えておきましょう。あとtupleの使い方も覚えておきましょう。get < idx > (tuple)ですよ。

SRM 705 easy
グラフ張ってループあるか見るだけですがこういうめんどくさいのはSCCにやらせましょう。

SRM 704 easy
あまりバグらせることなくうまく出来たなぁと思ったけどみんな早すぎ。直径を最初に取ればいいです。よくあるやつ。

SRM 703 easy
あーこれtopcoder40問目のeasyだったのに誤読+全然思いつけなくてつらかった。sortして、前の方から順番に辺を張るみたいなことをすればいいです。

SRM埋め(2)

当分easyで鍛えます。(気分でmedときます)

scoreですが目安としては
5分で満点*0.95
10分で満点*0.9
15分で満点*0.8
20分で満点*0.7
36分で満点*0.5
と覚えておけばよいでしょう。早解きは正義。

SRM 730 easy
「「「「「non decreasing」」」」コードは1発で書けたからもったいない。

SRM 729 easy
dpやるだけ

SRM 729 med
状態削減が本質になることに気づくのが遅すぎるし、角だけでいいと思って嘘解法してしまった。ダメダメ。辺全部試しましょう。

SRM 728 easy
結構好き。1つだけ見た時取りうる長さの候補がO( (logA)^2)通りだから、全部長さを試してminを取れば良い。
SRM 728 med
なんか昔に解いていた。座圧してdp

SRM 727 easy
難しい。後回し。->解きました。面白い。良問。SAがあったら直後にNを挿入して、後にTAを加えればいいです。なければ後にSANTAを加えればいいです。
SRM 727 med
真ん中の#の個数と.の個数を決め打つ

SRM 726 easy
条件整理して同じようなDPを3回する。

SRM 725 easy
bitDP復元

SRM 724 easy
まずorでbitが0の桁は2つの数もその桁は0です。1+0,1+1を判別するためにはt=sum-orを考えればいいです。ただし(t & or)==orを満たしている必要が有ります。(これを見逃した)桁ごとに条件が出たので、あとは簡単です。

SRM 723 easy
これはうまく出来た。上のbitから見ていって2つ以上そのbitを持つ数があれば、答えは(2^(k+1))-1みたいな形になります。
1つならその数をvとしてvを削除、v-2^kを追加して下の桁を見に行けばよいです。

SRM 722 easy
桁dpで良いです。でもdpの形にする必要はなかった。

SRM 720 easy
渾身の出来。だいぶ時間意識したら結構うまく実装できた。疲れるけど。
digit1とdigit2のそれぞれ1つの桁に注目して数え上げdpすればいいです。

SRM 719 easy
どっかの行に行って移動します。
SRM 719 med
根を含む部分木を選択して、その部分木上にない頂点を取る問題になります。割と速く通せたと思う。欲を言えば緩和にもう少し早く気づけたらよかった。

SRM 718 easy
渾身の出来。適当に0かけながらDPするだけ。

SRM 717 easy
フローからの復元と思って、それで通ったけどなんか想定解は違ったみたい。ちゃんと理解したい。

SRM 716 easy
A = sa + sb, B = sb + sc, C = sc + saみたいに対称な形にして、sa,sb,scのうち一番短いものを01010101...として、残りは000000....と111111....にするみたいな方針で通りました。

SRM 715 easy
いやどういうこと。今までtopcoderで解いた中で一番簡単だったかも。+の数と-の数大きい方が答えです。