読者です 読者をやめる 読者になる 読者になる

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

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

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. 推敲していない文章なので、間違いがあれば言ってください!

GDB+DDD

JOI本選で何が一番辛いかというと、やはり普段使い慣れているソフトが入っていないことでしょうか。僕は普段Visual StudioWindowsの上でほんわかと使っているのですが、そんな贅沢な環境で暮らしているひ弱なかものはしにとってUbuntu+最低限のエディタ+gccオンリーというのはまるで冬の雪山のど真中に捨てられたような気分です。(昨日ようやくこの小さい記号~(チルダというらしいです)がホームディレクトリであることを知りました。)そんなLinux初心者ですが、今日は過酷な環境の中で唯一の命綱と言ってもいいほどありがたいソフトであるDDDを取り上げようと思います。

 

DDDってどんなもの?

DDDとはData Display Debuggerの略で、gdbというCUIのデバッガーソフトをGUI化したものらしいです。アイコンは蜘蛛を虫眼鏡で覗いている画像です。初期配置では左側のメニューの上から6つ目にあります。

早速開いてみましょう。おお、何やらTips of the day(今日の豆知識 的な?)が出てきましたね。でも英語なのでそっとじ。ソフトを起動するたびに出てくるので、煩わしければ設定でオフにできます。

とりあえず画面の見方から。上からメニューバー、ツールバー、データウィンドウ、ソースウィンドウ、デバッガーコンソールがあります。一番下のデバッガーコンソールはCUIであるgdbのコマンドがそのまま使えるので、もう知っているという人はそちらからパチパチうってくださいな。

基本操作

ではデバッグをしてみましょう!まず、gcc「-g -O0」オプションデバッグ情報付き、最適化なしのコンパイル)をした出力ファイルを読み込ませましょう。メニューバーのFile→Open Programから出すことができます。この時、絶対にファイルやパスなどに日本語が含まれていないようにしてください!DDDは何故か日本語との相性がとても悪く、アイコンやブレークポイントの位置表示がバグったり、ファイルを開けなくなったりします。一応日本語でも動かないことはないらしいですが、コメントも極力半角文字で済ませましょう。

開くと、ソースウィンドウにはソースコードが表示されるはずです。右側の行数字を右クリックしてSet Breakpointでブレークポイントをつけることができます。さらに右クリックでPropertiesを選択すると条件付きにしたり、通るたびにコマンドを実行させることもできます。使えたら強そうですね。ブレークポイントが置けない!or正しく動作しない!という人はもう一度gccコンパイルオプションをチェックしてみましょう。

実行をするには、メニューバーのProgram→Runをクリックしましょう。そこでArgumentsの指定ができるので、例えばここに「<~/in.txt」などと入力すれば、ホーム直下にあるin.txtを標準入力にリダイレクトしてくれます。またそのまま実行すると出力は下のデバッガーコンソールに表示されて割と見難いので、Program→Run in Execution Windowにチェックを入れて実行画面を表示させましょう。ちなみに、実行画面を閉じてしまうとこのオプションのチェックも外れるという謎の仕様があるので、一度出したらなるべく消さないほうがいいと思います。

せっかくなので付属の小さいウィンドウのボタンも紹介します。Runは前述の通りプログラムを最初から実行させます。Interruptは処理を中断させます。Stepはステップイン、Nextはステップオーバーです。Stepi,Nextiはどうやら機械語に沿った動きをするようです。(いらない)Continueは一度止めた処理の再開、Killは処理の終了です。

変数表示

ここからが今日の本題です!ブレークポイントをつけて適当なところで処理を止めましょう。その状態でカーソルを変数の上に置くと、変数の中身が表示されます。ダブルクリックまたは右クリック→Displayとするとデータウィンドウに変数が常に表示されるようになります。配列はもちろん、文字列や構造体も表示できます。変数の中身が大きすぎる場合、データウィンドウ上で省略される場合があります。その場合はクリック→Show allすると良いでしょう。

ツールバーの空白に変数名を入れて、右側のPrintボタンを押すと下のデバッガーコンソールに結果が表示されます。それならDisplay機能で間に合ってる、ですか?いえいえ、このツールバーなんと変数だけでなく式や関数も処理してくれるスグレモノなのです!試しに例えば変数a,bがあるとき、「a==b」と入力してPrintすればtrueまたはfalseと出力され、例えば関数dpがあったとして「dp(2,3)」と入力すればその戻り値がキチンと出力されます!(この時、戻り値を取得するために関数を実行しているので、2重処理には注意してください)また、変数の中身を変えることも出来ます!代入式を入力し、Setボタンを押すと値が変更されます。本当にやりたい放題ですね。

終わりに

あとは煮るなり焼くなりです!DDDは上記以外にもユーザー定義コマンドや簡易マクロなどのVisual Studioに匹敵するような機能も持ち合わせています。癖があり慣れるのに少し時間がかかりますが、しっかりと使いこなしてJOI本選という真冬の嵐を乗り越えましょう!

 

 

P.S. 文章書くのって体力が必要だね!

ひとりごと+自己紹介

どうも、platypusです。

 

先日情報オリンピックという学生向け競技プログラミング大会の予選を通過しまして、(すごい希望的観測ですが)合宿にも行きたいと思っているただのプログラマーです。意気込みだけは他の人並みにあると思います。

 

思い返せば、半年ほど前にTwitterを使い始めてからすごく成長したと感じます。競技プログラミングのおかげで、普段プログラミングをするときもよりコードを身近に感じるようになりました。実装力も普通のプログラマー並にはつき、C++がすこしだけ「母国語」のようになった気がします。(ただ肝心の日本語はどんどん抜けていきますが...)最近はgccや各種CUIエディタに触れ、いかに統合開発環境を使っていた自分が本質を理解していなかったかを痛感しました。

 

しかしながら、最近練習し始めたvimgdbでも、自分が1日かけて全くわからなかったことを試しにつぶやいてみると、1分も立たないうちに先輩方が丁寧な説明をリプライしてくださって、尊敬すると同時に、いかに自分がまだまだなのかを深く感じました。少し焦る中、もっと努力をしなければ、と自分を奮い立たせるいい機会にもなりました。

 

そこで精進の一環として、自分の気が向いた時にブログを書いてみようかなと思います。本当に気が向いた時だけなので、この文章でこのブログの最後の記事になってしまうかもしれません。むしろ早く強くなって、今度は他の人たちに知識を授ける側になりたいと思っています。いわゆる日記と備忘録の中間点みたいなやつです。

 

さて、そろそろみなさんもブラウザバックしている頃でしょうが、自己紹介と行きます。自分は確か3年ほど前に学校のコンピューター部に入り、C++とDxLibを使ったゲームプログラミングをはじめました。競技プログラミングはそれに比べて本当に最近で、AtCoder最古のAC記録は去年の2/22でした。まだ一年も経っていません。

 

最近はJOI本選のためにUbuntuという(自分にとって)謎のOSを使って、これまた(自分にとって)謎のソフトたちであるvimgccgdbなどを練習しています。AtCoderやたまーにCodeforcesTopCoderなどのオンラインの大会にも頑張って出場しています。そのせいで、というわけではないのですが、最近は全くゲームプログラミングをしていません。でも文化祭までに一つ作品を作ったほうが良さげなので、構想だけは頭の中に入っています。

 

うーん、自己紹介というよりかは近況報告のようになってしまいましたが、以上です。これからは何卒よろしくお願いいたしますm(_ _)m

 

 

P.S. この文章にある微妙な臭さをどうにかしたい...