とりになりたいかものはし

プログラミング(主に競プロ)に関するひとりごとなど

Codeforces AIM Tech Round Div1C Centroids

概要

$N$個の頂点で構成された無向木が与えられる。 あなたは最大で一回、辺を削除し別の頂点と頂点を辺で結びなおすことができる。
ただし、辺を追加した結果も木でなければいけない。
この時、適切な操作を行い$i$番目の頂点を重心にすることはできるかを判定しなさい。

重心とは?

重心とは、削除して1つ以上の木に分解したとき、 それらの木のどれもが頂点数$n/2$を超えないような頂点のことである。
木の「中心」との違いに注意せよ。また、重心が複数個ある可能性にも留意せよ。

制約

$2\le N \le 4*10^5$

考察

まずは各頂点に対し、重心かどうかの判定をしよう。 これは簡単な全方位木dpで求まるため、ここでは扱わない。
次に、すでに重心である頂点は自明に(0回操作することによって)重心にすることができるので、 重心でない頂点を考える。
重心でない頂点を削除すると、定義より、$n/2$を超える大きさの連結成分ができる。
このような$n/2$を超える大きさの連結成分は一個しかないので、この連結成分をどうにかして操作することによって 2つの$n/2$以下の連結成分に分解できないかを考える。
まず、適当な重心を根として、木を再構成する。
そうすると、$n/2$を超える大きさの連結成分は必ずどの頂点の親側にあることがわかる。
根を通らずに連結な頂点をグループ分けすると、 どのグループの大きさも$n/2$を超えないので、 自分が含まれているグループ以外のグループの中で一番大きいグループと、そうでない頂点で分割するのが一番良い。(下の図を参照)
f:id:platypus999:20170501192200p:plain
ただ、一つだけ例外があり、自分のグループのサイズがちょうど$n/2$の場合、自分以外の全グループに加え、根自体もまとめて分割するのがよい。(下の図を参照)
f:id:platypus999:20170501192512p:plain
いずれにせよ、分割によって無事大きさn/2以下の二つの連結成分に分解できればOK、そうでなければその頂点は重心になれない。












木の問題、難しい

Codeforces Beta #84 Div1C Lucky Tree

概要

$N$頂点で構成された無向木が与えられる。 無向木の各辺には"Lucky"かそうでないかの属性がついている。 頂点から頂点までのパスにLuckyな辺が一つ以上含まれている時、それをLuckyなパスと呼ぶ。 異なる頂点$i,j,k$について、$i$から$j$までのパスと$i$から$k$までのパスが共にLuckyである$(i,j,k)$の通り数を求めよ。

制約

$1\le N\le 10^5$

考察

iを全頂点について試す。この時、$i$からLuckyなパスでつながっている頂点の数を$A(i)$とすると、 $A(i)*(A(i)-1)$が$(i,j,k)$の通り数となる。
$A(i)$をどう求めればよいだろうか? 一見辺$e(u→v)$について、$e$を通らずに$v$と連結なすべての頂点の集合についてDPすればよさそうである。
しかしもし頂点の出次数が非常に大きい場合(例えばウニグラフの場合)計算量は$O(N^2)$となり、間に合わない。 (virtual中はこれを$O(N)$と勘違いしてしまいTLEした。)
そこで、「全方位木DP」と呼ばれるテクニックを使おう。
全方位木DPとは、まず単純な木DP(各頂点を親とした部分木についてのDP)を行い、その計算結果をもとに今度は各頂点を根とした木全体についてのDPをすることである。
まず適当な頂点$par$を根にして有向な木にしよう。 次に、$F(i):=i$を親とした部分木について、$i$からLuckyなパスでつながっている頂点の個数を算出しよう。
これは各$i$の子$j$について、$i$と$j$をつなぐ辺がLuckyな場合$C(j)$、そうでない場合$F(j)$の総和を求めればよい。
(ただし、$C(x)$とは、頂点$x$を親とした部分木の頂点の個数である。)
これは単なる木DPである。
今度は、$G(i):=i$を親とした部分木に含まれない頂点について、$i$からLuckyなパスでつながっている頂点の個数を算出したい。
$i$が$par$の場合、当然$G(i)=0$である。
そうでない場合、$i$の親$j$について、 $i$と$j$をつなぐ辺がLuckyな場合$C(par)-C(i)$、 そうでない場合、$G(j)+F(j)-F(i)$である。
理由は下の図を参考にしていただきたい。

f:id:platypus999:20170428205705p:plain

f:id:platypus999:20170428205700p:plain

後は、$A(i)=F(i)+G(i)$なので、一番最初に考察した式によって答えを算出すればよい。





手書き図見にくいな(だったらつくるな)

Codeforces #150 Div1B/Div2D Hydra

問題要約:

頂点u-vをつなぐ辺を一つ持ち、端点の片方がuの辺をh個、端点の片方がvの辺をt個持つグラフをHydraグラフと呼ぶ。(図参照) 頂点数n,mのグラフGと整数h,tが与えられるとき、Gの部分グラフにHydraグラフが含まれるか?

f:id:platypus999:20170405203818p:plain

 

制約:

\(n,m\le 10^5\)

\(h,t\le 100\)(超重要)

 

解法:

Hydraグラフのu-vをつなぐ辺を全通り試そう。u-vを固定すると、注目する頂点は以下の3つに分類できる。

①uと隣接している頂点

②vと隣接している頂点

③u,v両方と隣接している頂点

図にすると、このように分類できる。

f:id:platypus999:20170405203825p:plain

(ただし、③に含まれるものは①、②から除外する)

頂点xの次数を\(deg(x)\)で表す。この時、①②③の個数をそれぞれ\(P,Q,R\)とすると、

\(P+Q+R=deg(u)+deg(v)\)である。

また、Hydraグラフを作ることができる必要十分条件

\(P+p\le h,Q+q\le t,p+q\le R\) である。

P,Q,Rを求めることは簡単ではなさそうだ。ここでは前処理により簡単に求められる\(deg(u)\)と\(deg(v)\)からHydraグラフの有無を検出しよう。

 

A.\(deg(u)\lt h+1\)または\(deg(v)\lt t+1\)の時、

そもそも辺が足りない。当然ながらHydraグラフは作れない。

B.\(deg(u)\le h+t+1\)かつ\(deg(v)\le h+t+1\)の時、

たとえ全ての頂点が③であっても、また逆に③の頂点が一つもない場合でも、Hydraグラフを構築できる。

C.その他

この場合は素直に\(P,Q,R\)を求めよう。ここで\(h,t\le 100\)と小さいことを活用できる。

AでもBでもないので、\(h+1\le deg(u)\lt h+t+1\)かつ\(t+1\le deg(v)\lt h+t+1\)である。つまり、頂点u,vに隣接する頂点を全列挙しても\(deg(u)+deg(v)=\)高々\(2(h+t+1)\)個であり、計算量は全体で見ても\(O(m(h+t))\)と十分小さい。

 

以上のA,B,Cの場合分けは以下のように図示できる。

f:id:platypus999:20170405203811p:plain

 

 

 

 

 

 

h,tの制約を見落としていてvirtual中は解けなかった。

SRM n周目(n > 1)

 

なんか1か月半ほど前にSRM6xxのDiv1 Easyで解けるものを全部解くといいましたが、やっと3日ほど前に1周することができました。

やはり難易度にはとてもばらつきがあったので、問題をこなすスピードは結構変動しました。中にはただの実装ゲーというべき余り良問でないものも存在しましたが、最終的に100問中68問解くことができました。(1回以上system testing failedしたものも含めます)

Div1 Easyの難しめの問題のサンプルとして、解けなかった残りの32問のSRM番号を貼り付けておきます。青コーダーくらいの人ならどれもじっくりと考察しなければいけない問題だと思うので、2,3問やってみてはいかがでしょうか。

602,603,607,608,614,616,622,629,630,631,633,638,639,642,645,646,653,654,659,662,665,666,669,672,677,681,682,683,686,692,697

ではでは

 (追記:616はあまりにもやるだけな問題だったので飛ばした問題でした。考察要素は全くないので一覧から消しました。)

 

2周目、つらい

 

 

 

 

SRMで精進!

どうも、platypusです。なんか暇なんで文章を書きます。

最近(というか3か月ほど前から)競プロのレートが全体的に伸び悩んでいたので、SRMのDiv1Easyを埋めていくことにしました。
とりあえず699~600までの100問を埋めたいです。

ルールとしては、
・とにかく上から解く
・問題を解いている途中は絶対解説を見ない
・1時間たってまだ考察が終了していない場合はパス
・System Test Failedをしてもすぐにテストケースを見ない

上のルールで、一日5問ほどこなせれば(ACするとは言っていない)いいかなーなんて思ってたりしています。
もしかしたら気まぐれで各問題の印象などをまとめるかもしれません。

これでレートが上がるといいなー ではではー

P.S. 精進すれば果たしてレートは上がるのだろうか

人権剝奪されました

とりあえずいろいろ言いたいことがあってまだ気持ちの整理がつかないのですが、先に書いておきます。

今回のJOI2017で人権を剥奪されたplatypusです。

前日のプラクティスも含めた2日間、どのように過ごしたのかを箇条書き風に書きます。本選激落ちマンのブログですので時間が惜しい人はブラウザバックを激しくお勧めします。

11日

朝起きる。ツイッターを見て12時ごろにJOIerが秋葉原で食事をするという情報を得る。少し早いが家をでる、と思った矢先に財布を忘れて往復30分の無駄な行動をする。

何とか秋葉原には定時に到着、もやし先輩とeiyaプロ(同じ学校の一年上の先輩)と先に合流しロイホで待機、さらにこたつがめさん、Tsuzuさん、pazzleさん、Azさん、izryt石油王さん、などと一緒にお昼を食べる。緊張していたので余り食べれなかった。

そのまま会場へ移動、中で予選通ったやつの賞と名札を受け取る。中でyukiプロとしゃべっていたKS勢やTK勢とすこーしだけしゃべってレベルの違いをひしひしと感じる

プラクティス開始する。4問目がトラウマなだけに一発で通せて安心する、お昼を食べたみなさん+浜松工業+沖縄高専などの人たちとしゃべる、やることがなくなって1問目をBITで通してみる、終了。

講演はニューラルなんちゃらについて割と基礎的な理解ができてよかった。行列を知っていたらもっと面白かったのかもしれない。

夕食会、maroonプロをはじめとするJMO勢が到着、なんと丼土さんが本選リストに追加されている52人のアイコンをプリントアウトしてきてくれる!おかげで話がINF倍しやすくなり会場はリアルタイムラインに

双子に514号室について教えられついでにハラスメントを受ける。ひどい(いいえ)

自己紹介はマスコットを掲示しました。はい

終わって宿舎へ。やっぱり独房だ。ほかの人たちは514号室の前に来てはしきりにニヤニヤしたりする。Luzhiledさんから「まずうちさぁ、風呂あるんだけど、入ってかない?」と言われる。関係ないけどLuzhiledさんめっちゃ沖縄の人だった。

1回にWifiが通っていることをツイッターで知る、もやし先輩とテトリスをする。オンラインはやっぱり慣れない。

丼土さんが持ち込んだスクリーンでABC全完勢などとともにけものフレンズを見る。ごいりょくがだんだんさがっていくよ!あしたあさはやいけどへーきへーき!たのしー!

さすがに2話で切り上げて部屋へ。pazzleさんと少し会話した後の就寝(ただし一時間ほど熱いやら緊張するやらで寝れなかった)

 

12日

起床を5:30にする。AC。

けものフレンズのBGMが流れている中dijkstraとunion-findを復習する(全く意味がなかった)

朝ごはんを食べる。MLEしてWAせずに済む。

荷物をまとめて会場へ。kurokojiさんとバスで隣になる。

本選開始前にもう一度双子からハラスメントを受けるがyukiプロとともに懸命に逆ハラをする

本選競技始まり!

1問目。なんかやけに易しくて嵐の前の静けさって感じだった。40分で実装。

2問目。1時間ほど2次元DPを考えるが貪欲で行けることをわかる。手元のテストケースも頑張って全部通す。やった!あとは通すだけ…と思ったら18点!?sample全ACなのにもかかわらずWAでなすすべ無し。貪欲はうそ解法かもしれないと思い次へ。

5問目部分点。狙えなさそう。ここから人権が削れ始める。

4問目部分点。は?って感じ。やばいやばい。

3問目!なんと5点しかない小課題を狙ってしまった上に盛大に誤読!0点で終わり。

人権を失い終了。絶望する中前のみやじろープロは2完したらしい。春合宿おめでとうございます。すべてを失ったなか昼食へ。

丼土プロの隣で、2問目の自分の考察はどうやら間違いではなさそうということを知る。こういう時に限って神頼みになって、なんで神様は僕をACさせてくれなかったのだろうと人格が壊れ始める。

解説フェーズ。精神が壊れかけていたので何も頭に入ってこない。やっとこさで2を実装するも今度はsample全ACなのに0点コードを書く。頭がなくてつらい。

最後は最初に会った人々+こたまねぎさんと一緒に帰る。こたまねぎさん、訛りが入っててとてもプロっぽかった。モチベが-INFになるなか終了。

 

とまあこんな感じでした。2問目なんでバグらせたのかいまだにわからないので、Hackしてほしいのですが近々ソースを上げようと思います。春合宿勢助けてくださいお願いします…

 

今回は実力とか以前に、「精進の量が足りない」という今更ながら当たり前の事実を突きつけられる大会になりました。人権を取り戻すためにも、近々何かを埋め始めるつもりです。本当に泣きそうなのですが、これでJOI参加記の終わりとさせていただきます。

P.S. いや、でも本当にTwitterのみんなとあえて楽しかった!

JOI本選前日!

ついにやってきましたね!JOI本選!
さっきけものフレンズの上映会で2話まで見てIQを溶かしてきたplatypusです。
プロたちはもっと見るらしいのですが僕は本選余裕勢ではないのでほどほどに切り上げました…

とりあえず明日の戦略でも書いておきます。

まず始まった直後はvimrcとすべてのプログラムの先頭に使うテンプレートファイルを作ります。

.vimrcはこちら

set nu ts=4 sw=4 et cin sta mps+=<:> nowrap
sy on
"commands for debugging
command! DBG execute "!g++ -std=c++11 -Wall -O0 -g ".expand("%:p")." -o ".expand("%:r")
command! RLS execute "!g++ -std=c++11 -Wall -O2 -DEVAL ".expand("%:p")." -o ".expand("%:r")
command! TST execute "!./".expand("%:r")." <in.txt"

テンプレートはこちら

#include <bits/stdc++.h>
using namespace std;
#define REP(i,x) for(int i = 0;i < x;++i)
#define FOR(i,x,y) for(int i = x;i < y;++i)
#define ALL(a) a.begin(),a.end()
using ll = long long;

int main()
{
    return 0;
}

うーん、少し盛り過ぎでしょうか…
特にvimrcの1行目、すごく不安です。でも明日のために一生懸命暗記してきたから大丈夫なはず…!(フラグ)
C++テンプレートの方は割と無難ではないでしょうか。
vimの:rコマンドを使って先頭に埋め込んでいきますね

この時点で15分程度立っていると予想… 落ち着いて…
それで、次は普通に1問目を見ます。普段の自分ならば解けるはずの難易度(超絶死亡フラグ)なので、そのまま満点を狙います
まあでも絶対緊張してバグを発生させると思うので、DDD(Data Display Debugger)の設定も合間にしておきます。
実はそのまま使うとvectorの中身を表示できないという欠点があるので、ユーザー定義コマンドを付け加えます。
vectorのoperator[]関数がインラインなせいでDDDでは反応してくれないんですよね… なので生ポインタから直接たどるしかないんです…)

define vecp
  if $arg1<0 || $arg1>=$arg0.size()
    print "Out of range"
  else
    print $arg0._M_impl._M_start[$arg1]
  end
end
define veca
  set $i = 0
  while $i < $arg0.size()
    vecp $arg0 $i
    set $i = $i + 1
  end
end

これらのコマンドで、vectorの要素をボタン1つで見ることができるようになります。
あとは頑張ってブレークポイントをポチポチしてデバッグをひたすらがんばります。

2問目、これはもしかしたら躓くかもしれないので、もしさっぱりだったら3問目も目を通します。
解法を思いついてからプログラムを書き終わるまで自分は平均30~45分程かかり、
バグを埋め込んでしまうと一気にまた30分ほど潰してしまいます。
そのため、競技時間4時間は圧倒的に短いと思っているので
わからない問題があるくらいだったら4,5の部分点でももぎ取っておいたほうがまだましだと思っています。
4,5問目は部分点狙いですが、部分点だったとしても決してコード量が減るわけではないので、時間を多めにとって
ラスト30分位になったら書き始めようと思います。
それでは今日はもうぐっすり寝て、明日に備えようと思います。おやすみなさい!


P.S. 推敲していない文章なので、間違いがあれば言ってください!