誤読

文字通りくそコード

JOI'18本選参加記

情報オリンピック2018本選に参加してきました。結果はでてないのでこわい

・1日前

ちょっと前にインフルエンザにかかってからだらだら過ごす癖がついて精進を全然しておらずまずかった。

荷造りをしようと思ったら明日の出発が遅いことに気づき放棄した

めちゃくちゃ早く寝てやろうと思ったら結局1時くらいになる

・1日目

古文の授業中にPlugsを考察する(解けてないね)

学校の4限を爆破することで時間的余裕を得た

お昼ご飯を高2のメンツで食べる

のしに僕のドリンクバー代金を持ってもらった、ありがとう

PASMOが死んでたのでチャージ(1回目)、つくばエクスプレスに乗ってつくばへ

出るときに足りなくてまたチャージ(2回目(は?))

電車内で迷路君と解いていたStrapsが通せていなくてきもちわるい

つくばオカピとか言いながらつくばカピオ

 学生証を2年連続で忘れるが定期でイケることが昨年分かっていたので昨年の経験を生かして楯と解像度の悪いクリアファイルのゲットに成功

荷物置き場に行くと双子とかWA_TLEがいて平均レートが一気に上がるのを肌で感じた

会場に向かって自席に座ると隣の机にWA_TLEがいて泡を吹いて倒れる

恐る恐る話しかけると「あなたは誰ですか」と言われて寒色系コーダーの肩身の狭さを感じた(僕の顔が覚えにくいという評価を時々される)

双子がリンゴを投げまくってるのを見てたらプラクティスが始まり、30分くらいで全完する(Eclipseの設定につまらなかったのが良かった)

終わった後レッドコーダーやオレンジコーダーなどと交流し、数え上げpdfさんから教えてもらったEmacsゲームシリーズで遊ぶ

クソゲーに埋もれた唯一の神ゲーadventureがわくわくするので明日全完したらやりたいなぁ~~などと思った

Ciscoのありがたい講演があったためStrapsの続きをやるが、無限にWAが取れず険しくなる

晩飯はいつもの感じのビュッフェで即消費された

自己紹介フェーズで面白いことを言おうと思ってたのに全然思いつかずめちゃくちゃ普通だった

宿舎へのバスにのって宿舎にいくと尋常でないスピードでセッティングを終えたプロたちがみんプロに参加していた

800を人々と読むと問題名にXORが入っているうえ問題文が読めなかったので諦めて風呂を急ぐ

azさんが体をふくタオルがないにもかかわらず風呂に入って出られなくなってたのが面白かった

迷路君とコンビニに行って本選会場に持ち込むお菓子などを買いに行くが、ぼくが間違えて宿のスリッパで外出してしまい、社会性ポイントを大幅に失った

PCKで風船があったのが好きだったので、本選では自分で風船作るかということで1問ACするごとに風船を作るため風船ガムを3つ購入(3完くらいできると思ってた)

部屋で800を一緒に考察だけするか~みたいなことをしていたら人が4人くらい来て雑談に花を咲かせる

一回ロビーに行ってテトリス勢とテトリスをして部屋に戻って雑談をすると日付変更線を跨いだため解散

歯を磨いて寝ようとするが、まくら硬すぎベッド硬すぎ切れない暖房通気性0の部屋などの要素のシナジー効果で睡眠を妨害されるも1時ごろ就寝

・2日目

朝6時過ぎに目覚ましをかけた人を絶対に許さない気持ちとともに目が覚めるが、早すぎるため耳の感覚を切って2度寝する

昨日モーニングコールを頼んだazさんが激しいノックで起こしに来たため起床

俺は徹夜したみたいな自慢を聞き流しながら白飯が多すぎる和風朝食を食べて頭に栄養を回した

バス内で3つくらい解説を読んで頭がよくなった気になりつつ、SCCを空で書けない不安に襲われる

会場で椅子に座ると最後のJOIということもあって緊張がヤバく、不安で泣きそうだったが、隣にすわるWA_TLEが無表情なため僕も無表情になる

競技開始までの待機時間が長すぎる

残り時間が0になった瞬間に問題を開く

・1問目

環境設定にちょっとつまる

見たところDP?みたいなことを思ったが考え直してはい

ここで20分

・2問目

読んだだけだと分からない

JOIなので部分点は正直だろうと思い、一つずつ考察すると3つ目の部分点でAmax-Amin固定嬉しい~みたいなところから、Amaxかなんか全探索してAminとSはO(1)かな~~と思い、S+Aminの前計算を思いつく。書いて投げるとAC

ここで50分経過

ここまではすらすらとけて、これ割と余裕では??と思うが、自分の解けるレベルであることに不安を覚える

・3問目

読んだところ依存関係をグラフにしたくなったのでグラフにすると、次数が3以下でグリッドに埋め込める形のグラフになったためあぁ~2部グラフとなる

連結成分ごとに白黒塗り分けしてでかいほう取りたい気持ちになり、気持ちに正直なため実装して投げるが、WAする。

この時点ではちょっと前にあった企業コン(SoundHoundのフローで解けるやつ)で全く同じミスをしているのを忘れており、自信満々で1時間30分ほど溶かす

どうしても通らないので端から適当に取ってくやつをやると、ACはしないが、小課題2までで塗り分けでWAだったところをたまたまACしているので2つともやって小さいほうを取ることで嘘解法ではあるものの小課題2まで取れて33点

この後もごにょごにょやるが通らず、あきらめて部分点オタクになることを決意する

ここまでで3時間

・4問目

問題文を読んで小課題を見ると自明が2つで31点だったので通す

小課題3も分かったが、実装がめんどくさいためやらない(WFは思いつかず、グラフ拡張ダイクストラ

ここでのこり30分になり、5問目を見るか4問目の小課題3を頑張るかの2択になるが、5問目の問題文の長さでコンテストをやめたくなってきたので4問目を頑張って実装していたら終了コールが入って終了した

コンテストが終わって隣のレッドコーダーにボーダーがどのくらいか聞くと、多分通ってるでしょと言われ安心する

人から3問目解法を聞いて悲しくなる

4問目解法も聞いて悲しくなる

食事をして解説会

受験生だと思っていた人が壇上にいてびっくり

3問目の部分点33が僕しかいなかったためちょっとうれしくなる

5問目が面白そうなのでいつ解きたい

人々に別れを告げ、電車に乗ろうとするが、PASMOが死んでいたためチャージをする(3回目)

電車から降りるときもPASMOがだめだったためチャージをする(つくばエクスプレスが高すぎる)

家に帰って姉がバレンタイン用に作った緑色のクッキーを食べてJOI本選が終了した

 

春合宿に行けたらすごくうれしいので通っていることを祈っている

実は修学旅行と春合宿ががっつりかぶっているのでまずい

 

数列の任意の範囲で大きいほうから任意の個数のsumをO(1)で求める

追記;若干のタイトル詐欺が含まれています
追記2;これはメモリがすごい

WaveletMatrixをします。

解説をします。


まずWaveletを理解していない人は↓を読んでください。

これ見てからウェーブレット木の世界 | Preferred Research

これ読んでwww.scribd.com

上からk番目の値を求める操作を知ってるとイメージしやすそうなので上のに合わせて理解してください。




ARC074Dについて、某さんが上からk個のsumライブラリほしいみたいなことを言っていたので、書いてみたら書けた。

ベクトル並列型もやし先輩 on Twitter: "上からn個の和、WaveletでめっちゃくまくやればO(1)でできそう"


基本的にはk番目の値を求める操作と同じく潜っていきます(この場合は再帰でやっていきます)。その過程で、bit桁ごとに2のべき乗ずつ合算していくことで、最終的に全体のsumを出すイメージです。

図解

f:id:akihiro1001:20170523205307p:plain

↑な感じに行列があったとする。(オレンジ枠は緑枠の数字のnbit目、紫線は0,1のボーダー)

・n桁目のみでのsum

popc(立ってるビットの数) * 2^n であり、さらにこれに下位bitでのsumを加算する。(pow使うな)

・下位bitでのsumの出し方

本題の操作をmore_Kthsum(start, end, kth, n桁目)(kth >= 1)

ランクはrank(start,end, 0 or 1)で閉区間 (0か1のbit数)

n桁目の段階で、popc > kth の場合は、more_Kthsum(ボーダー + rank(0,s,1), ボーダー + rank(0,e,1), kth, n-1)であり、これはk番目の値を求めるときの操作とおんなじでまあ普通

そうでない場合がミソで、ナイーブな方法だと、

    more_Kthsum(rank(0,s,0), rank(0,e,0), kth - cou, n-1) + more_Kthsum(ボーダー + rank(0,s,1), ボーダー + rank(0,e,1), cou, n-1)

だが、ここで分岐してしまうのは計算量大爆発なのでなんとかして一本化したい。

注目すべきは→のほうで、範囲内の立ってるビット全てのsumを求めている。

ここで各桁において、立ってるbitの場所だけ 現在の桁以上の桁を削った後 の累積和をあらかじめ取っておくと、→が[end,start)の和に置き換わって計算量爆下げO(1)である。(↓図)

※現在の桁については n桁目のみでのsum で加算されてしまっているので、n桁目のみでのsumを出す時点で引くなりなんなり上手い感じに処理して

f:id:akihiro1001:20170523213754p:plain




例えば、

[2,7)で大きいほうから4個のsumを求めたいとする

・2bit目 popc = 3 kth = 4 popc <= kthなので、popc*2^2 + [2,7)の和 + more_Kthsum(0, 2, 1, 1)である。

・1bit目 popc = 2 kth = 1 popc > kthなので、popc*2^1 + moreKthsum(4, 6, 1, 0)

・0bit目 popc = 1 終わりなのでpopcを返す。

みたいな感じになります。


これでARC074Dを通しました(説明と若干違ったり、bitvectorがゴミ実装だったり)
Submission #1304562 - AtCoder Regular Contest 074 | AtCoder



備考:

WaveletMatrixの計算量O(1)を真に受けてはいけない。これは競プロ

これを利用したら小さいほうからk個もできます。(普通の累積和-大きいほうから(end-start)-k個 てきな)

(完)

Union-Find with deletions

謎のデータ構造を見つけてしまった。実装したくなかったが、してしまった。後悔しかしていない。

UnionFindといえば競プロerであればほとんどの人が知ってると思われるが、あれはUniteとFindはあってもある要素をフリーにするという操作ができない。

UF木の葉以外を削除しようとすると計算量が増えてしまうのは想像がつくと思う。

そこでUnion-Find with Deletionsというのがあって、これを使うとUniteをO(A(n)),FindをO(A(n)),DeleteをO(1)でできるようになっておいしい。
(追記)論文でUniteがO(1)なのは集合をしていしてUniteする実装だからで、要素を指定してそれらの属するグループを併合するっていうのはFindを挟む必要があるのでO(A(n))になっているだけです。


主なアイデア

1.要素の部分と木構造の部分を切り離して木のノードが要素を持つという形にすると、削除したいノードの持つ要素とその木の中での葉の要素をswapしてから葉を消せばよい。

2.入りだけのオイラーツアーを持つことで葉のノードがわかる。

3.経路圧縮でいつものやつじゃなくてTarjan and Jan van Leeuwenが考えた経路圧縮を使いましょう。(ノードを親の親にくっつける)

説明能力が皆無なのでこの論文とこのスライドを合わせて読むと実装できます(大嘘)


この論文の通りにだと実装できなかったんですけど、アレンジを加えて頑張りましょう💢💢💢💢💢💢💢💢

↓ぼくのじっそう(ゴミ)

[C++] class UFNode; class LNode { public: UFNode *Myval; LNode *Prev, *Next; L - Pastebin.com


普通に汎用性高そう(小並感)なので今後の競プロ界のトレンド間違いなしだよ

せっかく無限に時間を溶かして書いたのに使う問題とか一切見当たらないため非常にアレなので使えそうなのがあったらほんと教えてください。

HOJにverify問投稿しようかな…

DSU on tree (CF600 E CF570 D)

GuniとかSackともいうっぽい、汎用性が高そうなので実装した。あと問題を2つ解いた



木があって各頂点にプロパティを持っている(例えば、ノードに色がついてるなど)時に、あるプロパティを持つ頂点の数を調べなさいとか、この部分木には何種類のプロパティがあるとか、そういったクエリを先読みして全部でO(n log n)でこたえられるテク。(部分木ごとに答えられる(大事))

ただ、これを使う問題は普通のマージテクだけでとけることもおおいっぽい


例題として、頂点に色がついた木で各頂点の部分木に何種類の色があるか出力する問題を考える。頂点数は10^5とか10^6とかくらい

愚直に各頂点からそれぞれdfsするとO(V^2)かかるし、ダメ

vector<int> cnt(n),ans(n);
int cou = 0;
void add(int cur, int p, int x){
//cnt[cur]が0->1になったときansが1増える、またその逆
    cou -= (bool)cnt[ col[cur] ];
    cnt[ col[cur] ] += x;
    cou += (bool)cnt[ col[cur] ];

    for(auto itr: g[cur])
        if(itr != p)
            add(itr, cur, x)
}
void dfs(int cur, int p){
    add(cur, p, 1);
////この時点でcurを根とする部分木での答えが出てる/////
    ans[cur] = cou;
//////////////////////////////////////////////////////
    add(cur, p, -1);
    for(auto itr : g[v])
        if(itr != p)
            dfs(u, v);
}

これをこうするとO(nlogn)↓

vector<int> cnt(n), sz(n),ans(n);/////szには部分木のサイズが入っているものとする
int cou = 0;
vector<bool> isbig(n);

void add(int cur, int p, int x){
//cnt[cur]が0->1になったときansが1増える、またその逆
    cou -= (bool)cnt[ col[cur] ];
    cnt[ col[cur] ] += x;
    cou += (bool)cnt[ col[cur] ];
///////////////////////////////////////////////////

    for(auto itr : g[cur])
        if(itr != p && !isbig[itr])
            add(itr, cur, x)
}
void dfs(int cur, int p, bool keep){
    pii bigc = {};
    for (auto itr : g[cur])
        if (itr != p)
            bigc = max(bigc, { sz[itr], itr });
    for (auto itr : g[cur])
	if (itr != p && itr != bigc.second)
	    dfs(itr, cur, false);
    if (bigc.first)
	dfs(bigc.second, cur, true), isbig[bigc.second] = 1;

    add(cur, p, 1);
////この時点でcurを根とする部分木での答えが出てる/////
    ans[cur] = cou;
//////////////////////////////////////////////////////
    if(bigc.first) isbig[bigc.second] = 0;
    if (!keep) 
	add(cur, p, -1);//結果をクリアする
}

これは何をしているかというと、

①子で最大の部分木探す
③最大じゃないやつ->最大のやつって順番でdfs
④最大のやつだけは親の頂点に帰るときに結果を持って帰る(一番大事)
・addでは、最大フラグが立ってるやつ以外に潜る(最大フラグが立っている場合、最大のやつdfsの結果が残っているのでやる必要がない)(最重要)

要は、子で最大の部分木の計算結果を親に持ち帰ることで、その分の計算を省くことをしてる

なぜこれでO(nlogn)が達成できるかというと、マージテクと同じ原理です(僕はそもそもマージテクの原理を雰囲気で理解してしまってるので、雰囲気で理解して(まあ最大を廃部いてるんだから計算量も減るでしょ!w))

備考
・部分木ごとに結果が出てるっていうのを強く意識するとよい
・基本的にコメントで囲ってるところを変えて問題を解く
・クエリを処理するとなると、ansに代入してるところでループを回したくなることがよくあるが、できるだけaddのところで随時処理してあげて、ループをなくそう(計算量大爆発、地球滅亡)
デバッグはわりとしやすい(4時間)



入門:
Problem - E - Codeforces
頂点に数字がついてて、部分木で最頻の数字をDominating Colorとか言うんだけど、その合計を求めてという話

随時(大事)Maxを更新してあげて、随時(大事)最頻値の合計を数えてあげる(随時じゃないと、ansに代入するところでMaxを求めるループを回さないといけないのでダメ)
地味にintだとオーバーフローするのが最大のイライラポイント
Submission #25946251 - Codeforces

実装違うけどちょっと早いver↓
Submission #25888745 - Codeforces


Problem - D - Codeforces
頂点に文字がついてて、部分木と全体での深さが指定される。部分木内の指定された高さの頂点についてる文字を並べ替えて回文が作れますか?という話
・回文を作るには奇数個の文字が1つ以下ならよい。
・深さごとにカウントを持つといける
・クエリを頂点ごとに持つのもイケメンポイント

Submission #25922457 - Codeforces


上の二つを解いたら感覚がつかめた。
両方とも想定解ではないっぽい。(上はただのマージテク、下はオイラーツアーでほいみたいなことをするっぽい)


このエントリにすごいお世話になった、感謝して(いろんな実装が乗ってる)(問題も載ってるのでとくっきゃない)
http://codeforces.com/blog/entry/44351


備考
・CFのブログって変なのいっぱいあるよね
・Rngedbaseループの変数名をitrにしてしまう癖があるんだけど、なんか違うっぽい

2-SAT (ARC069-F)

ARC069-Fがすごく解きたかった

2-SATは知ってた(以前minisatとか触った関連)ので書くのにはそんなに困らなかった。

解の構築は普通にできそうだけど、どこにも書いてないのが怖い(今度書いてみるよ)

さらっと探してみても使う問題を見ないし、実はだるかったりするんかな

・ARC069-F Flag

にぶたんはそれはそうで、判定部に2-SATを使う。

普通に2-SATを組むとすると、

候補2つのうちどちらか1つだけを使う ( ( ¬ A ) ∨ ( ¬ B )) ∧ ( A ∨ B ) に加えて、

各旗候補地についてmid以内にある旗と共存できないっていうのを

¬ ( A ∧ B ) → ( ¬ A ) ∨ ( ¬ B )と書き換えられることを使って表すことになる。

しかし、これだとImplicationグラフでの辺の数がO(V^2)とかになってやばいので減らす努力をしなければならない。


各旗候補地について、共存できないとして論理式につっこむのは連続してる旗たちなので

区間をセグ木っぽく表してあげて、 旗と共存できない ではなく 区間と共存できない として論理式を作ってあげるとO(VlogV)の辺で抑えられる。


また、親の区間が偽なら子の区間はかならず偽(その逆はない)なので ( ( ¬子 ) ∨ 親 ) を加える

f:id:akihiro1001:20170327122002j:plain:w500

僕のソース
Submission #1180258 - AtCoder Regular Contest 069 | AtCoder

bool TWO_SAT(int n, vector<pii> clause, vector<int> &ans) {
	DGraph g(n * 2);
	for (auto itr : clause) {
		g.con(itr.first + n, itr.second);
		g.con(itr.first, itr.second + n);
	}
	vector<int> scc;
	SCC(g, scc);

	REP(i, n) {
		if (scc[i] == scc[i + n]) {
			return 0;
		}
	}

	return 1;
}

  
・備考

TWO_SATってめちゃくちゃダサくないか

必要十分な論理式を考えるのがほんと難しい

論理式を考えるのがすごく楽しい

Tarjan's SCC

lowlinkを書いたばかりだったので、lowlinkを使ってSCCが書けると聞いて飛びついた。(が、完全に罠だった)

kosarajuは書いたことあるけどtarjanはないって人多そう(実際のとこ定数倍とかで早いのはどっち)

日本語の資料が微塵もなくて辛かった(有志は英wiki全部移植して)

①強連結成分は、dfs木を作ったときに必ず部分木になる(強連結成分はどの点からでもすべての点に行けるのでそれはそう)

②lowlinkとorderが等しい頂点が強連結成分の部分木の根(もしlowlinkのほうが小さかったら、それよか上まで自由に行けるので)

ので、dfsの行きがけでスタックに頂点を積んでいき、戻るときにlowlinkとorderが等しい頂点が見つかったら現在いる頂点が出てくるまでスタックから積んできた頂点を取り出す。そいつらがひとまとまりの強連結成分。

f:id:akihiro1001:20170327113005j:plain:w300

・罠

一般的なlowlinkは無向グラフでやるもので、有向グラフでlowlinkを無向と同様にやるとdfsするときの順番で結果が変わってしまうので少し違う。無向の時は後退辺だけだが、有向の場合は再帰のスタックに積まれてる頂点への辺も含めて考える。(ほんとにどこにも書いてなくて有向リンク界隈の廃れを感じる(そんなものはない))

あと、これを使って2-SATを書いたよ

void SCC(DGraph& g, vector<int>& scc) {
	vector<int>  orb(g.vn, -1);
	scc.resize(g.vn, -1);
	int cc = 0,k = 0;

	vector<bool> used(g.vn);
	stack<int> st;
	function<int(int)> dfs = [&](int cur) {
		int low = orb[cur] = ++k;
		st.push(cur);
		used[cur] = 1;
		for (auto itr : g.g[cur]) {
			if (orb[itr.first] == -1)
				low = min(low, dfs(itr.first));
			else if (used[itr.first])
				low = min(low, orb[itr.first]);
		}
		if (low == orb[cur]) {
			while (1) {
				int cp = st.top(); st.pop();
				used[cp] = 0;
				scc[cp] = cc;
				if (cp == cur)
					break;
			}
			cc++;
		}
		return low;
	};
	REP(i, g.vn)
		if (orb[i] < 0)
			dfs(i);
}