Aの解説です。
続きを読むXmas Contest 2016 H解説
H問題の解法と雑な証明です。
open all / close all
generated by indenter
以下ソースコードです。マクロ多くてごめんなさい。
#include略 #define fi first #define se second #define rep(i,n) for(int i = 0; i < (n); ++i) #define rrep(i,n) for(int i = 1; i <= (n); ++i) #define drep(i,n) for(int i = (n)-1; i >= 0; --i) #define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next) #define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++) #define rng(a) a.begin(),a.end() #define maxs(x,y) x = max(x,y) #define mins(x,y) x = min(x,y) #define pb push_back #define sz(x) (int)(x).size() #define pcnt __builtin_popcount #define uni(x) x.erase(unique(rng(x)),x.end()) #define snuke srand((unsigned)clock()+(unsigned)time(NULL)); #define df(x) int x = in() #define dame { puts("-1"); return 0;} #define show(x) cout<<#x<<" = "<<x<<endl; #define PQ(T) priority_queue<T,vector<T>,greater<T> > #define bn(x) ((1<<x)-1) using namespace std; typedef long long int ll; typedef pair<int,int> P; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<P> vp; inline int in() { int x; scanf("%d",&x); return x;} inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');} template<typename T>istream& operator>>(istream&i,vector<T>&v) {rep(j,sz(v))i>>v[j];return i;} template<typename T>string join(vector<T>&v) {stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);} template<typename T>ostream& operator<<(ostream&o,vector<T>&v) {if(sz(v))o<<join(v);return o;} template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v) {return i>>v.fi>>v.se;} template<typename T1,typename T2>ostream& operator<<(ostream&o,pair<T1,T2>&v) {return o<<v.fi<<","<<v.se;} const int MX = 100005, INF = 1001001001; int n, m; vvi to, co; int cnt; int dfs(int v, int x, int p=-1) { int a = 0, b = INF; rep(i,sz(to[v])) { int u = to[v][i]; if (u == p) continue; int r = dfs(u,x,v)+co[v][i]; if (r*2 >= x) { mins(b,r); } else { --cnt; maxs(a,r); } } if (a+b < x) return b; ++cnt; return a; } int f(int x) { cnt = 0; dfs(0,x); return cnt; } int main() { scanf("%d%d",&n,&m); to = co = vvi(n); rep(i,n-1) { int a,b,c; scanf("%d%d%d",&a,&b,&c); --a; --b; to[a].pb(b); co[a].pb(c); to[b].pb(a); co[b].pb(c); } int l = 1, r = INF; while (l+1<r) { int c = (l+r)>>1; if (f(c) >= m) l = c; else r = c; } cout<<l<<endl; return 0; }
Xmas Contest 2016
Xmas Contest 2016 にご参加いただいた皆様、ありがとうございました&お疲れ様でした。
難易度が高すぎて順位表が大変なことになっていましたね。。
1問をじっくり考えるのに慣れていない方には少しつらいセットだったかもしれないです。
でも、なんだかんだ出来ることはあって座るだけにはならなかった方が多く、その点は良かったかなぁと思っています。
それでは解説を...のつもりだったのですが、解説をガッツリ書く体力が残っていないため、ヒントだけで失礼いたします。
ヒント
open all / close all
generated by indenter
ACC2016 24日目「色塗り2」解説
Advent Calendar Contest 2016 24日目の問題「色塗り2」を出題させていただいたので、その解説
問題はこちら。
open all / close all
generated by indenter
IOIへの出題について - 解説編
open all / close all
generated by indenter
IOIへの出題について
※この記事はCompetitive Programming (その2) Advent Calendar 2016 - Adventarの2日目の記事です。
IOIにあまり興味が無い方は、下の方の僕が出題した問題の方だけをお読み下さい。
IOIとは
IOIとは"International Olympiad in Informatics"の略で、日本語で言うと「国際情報オリンピック」のことです。
IOIの大会としての特徴は以下のとおりです。
- 高校生以下が対象の世界大会
- 1989年から開催されており、2016年に第28回が行われた
- 各国で国内選抜があり、日本はJOIが選抜を行っている
- 日本から選手団が派遣されたのは1994~1996と2005~現在
- 2018年に日本(つくば)で開催予定
競プロのコンテストとしての特徴は以下のとおりです。
IOIへの問題の応募
毎年、その年の公式サイトに「Call for tasks」という形で問題募集の情報が公開されます。
今年のものはここです。
近年は問題の集まりがあまり良くないらしく、毎年応募期限が延長されています。
今年の期限は12/15に延びたので、まだ間に合いますよ!
IOIは時間ペナルティなどのないコンテストなので、部分点が多い問題が求められています。
簡単枠ならその限りではないかもしれません。
また、5時間3問なので、実装は重くてもOKです。
ただし、シラバスの範囲内からしか出題できないので注意してください。
IOIで求められている問題の傾向は以下のとおりです。(多分)
- 意味のある部分点の多い難しい問題
- 部分点はそれほど多くないが、面白い問題
- 変わった形式の面白い問題(ここ2年は出題されていない)
- 簡単枠の面白い問題(恐らく競争率が高い)
- 汎用的でかつ珍しめのテクニックを使う問題は好まれる傾向にありそう
応募する際に送る必要のある情報は以下のとおりです。
問題に自信があれば、なるべく親切にいろいろなファイルを作っておくと採用率が上がって良いのではないかと思います。
- 問題文(英語)
- 運営がストーリーを変えたりすることもあったりするので、原案を伝える程度のもので大丈夫だと思います。
- 過去問が公式サイトで公開されているので、構成はそれを参考にすると印象が良くなるかもしれません。
- 自分はmarkdownファイルとそれをpdfにしたものを用意しました。(txtでもなんでも良いと思います。)
- 解説
- 部分点を含めた解法を書いた文書を用意する
- 解答ソースコード
- IOIの形式は少し特殊なので、過去問のデータを取ってきてそれに合わせて書くと良いでしょう。
- テストデータ
- 必須ではありませんが、あるとかなり印象が良くなると思うので用意することを推奨します。
- ジェネレータも置いておくとなお良いと思います。
- プロフィール
- 作問者が何者なのかを書きます。協力者がいる場合はその人も。
- 連絡先、氏名、所属、国籍、情報オリンピックにおける立場(選手のトレーナー/委員会の役員/無関係等)を書きました。
- readme
- フォルダ構成を書いておくと親切だと思います。
もし実際に応募する場合は公式サイトを読んでもらうのが良いと思います。
応募を真剣に検討している方は、僕に声をかけてもらえれば、参考として僕が送ったファイル類を渡します。
IOIに問題が採用された時の流れ
2015にも1問送ったのですが、落ちました。落ちた場合は何も連絡は来ないので少しさびしかったです。
去年秋のある日大学に向かうバスで思いついた問題が自信作で、部分点もある程度つけられそうだったのでIOIに送ってみることにしました。
この年のCall for tasksの期限は年始すぐくらいで、帰省中にも作業してたような記憶があります。
1/11に提出し、しばらく経っても音沙汰がなかったので少し落胆していると、5/31に採用通知が来てめちゃくちゃ嬉しかったです。
問題が採用されると、shortlistという9問くらい(?)の問題候補の中に入ります。
実際に使われるのはこのうちの6問くらいで、残りは予備・来年に繰り越しになります。
問題が採用されてshortlistに載ると、IOIに招待され、IOIにguestとして参加することが出来ます。
もちろん、断ることも出来ます。
現地では特に仕事がないので、日本選手団と行動するなり、guest用の観光に行くなり、自由にしていればいいです。
ただし、問題が実際に使われて公開されるまではあらゆる情報が秘密なので注意が必要です。
現地に行く場合は、現地についてから「え、なんでいるんですか?おっ、writerか〜?」となるのは仕方ないので問題なしです。
IOI 2016に採用された問題
Code Festivalの本戦の問題を作ろうと、風船釣りを元ネタとした問題を作ろうとしていたときに原型が出来ました。
結局これは風船が全く関係ない問題になり、その後風船ツリーが出来ました。
その後、少し問題設定をいじると、自作問題の中でも 1, 2 を争うくらい好きな問題になりました。
さて、送った問題ですが、ドラえもんのガリバートンネル(とスモールライト)を知っていると理解しやすいと思います。
問題
ガリバートンネルが N 個あります。
トンネル i の入口のサイズは A_i、出口のサイズは B_i です。
snuke君はこれらのトンネルを1列に並べ、順番に通り抜けていこうとしています。
トンネルの入口に入るには、体のサイズが A_i より小さくなくてはなりません。
トンネルの出口から出てくると体のサイズはちょうど B_i になります。
snuke君の体のサイズは最初 1 です。
snuke君はスモールライトを持っていて、これを 1 秒使うと体のサイズを 1 減らせます。
トンネルの並べる順番を工夫したときの、スモールライトを使う必要のある秒数の最小値を求めて下さい。
実際に出題されたときは、ジェットコースターの侵入速度制限付きのレールユニットを組み合わせる設定になりました。
制約
- 2 ≦ N ≦ 200,000
- 1 ≦ A_i,B_i ≦ 10^9
入力例
4 1 7 4 3 5 8 6 6
(1,7) (6,6) (4,3) (5,8) の順で並べれば、1個目→2個目で1秒、2個目→3個目で2秒使えば良くて3秒で済み、これが最小なので答えは3。
体のサイズは、1-tunnel->7-light->6-tunnel->6-light->4-tunnel->3-tunnel->8 という感じで変化していくことになります。
部分点
1. (11点): 2≦n≦8.
2. (23点): 2≦n≦16.
3. (30 点): 答えが 0 かどうかだけ判定すれば良い
4. (36点): 満点
解説は別記事で紹介します。
また、ここのday1の2問目でonline judgeが利用できます。
IOIの大会中のコンテスト以外のイベント
1. 到着日
2. register、開会式
3. コンテスト1
4. エクスカーション1
5. コンテスト2
6. エクスカーション2
7. 閉会式
8. 出発日
というスケジュールです。
1週間と長いですが、あっという間です。
毎年、JOIから問題文の翻訳等をするための随行員が派遣され、各コンテスト日の前日夜に問題文の翻訳をします。
あと、大会期間中何度か開催される全体会議にも出席したりします。
僕はIOI 2015の随行員で、カザフスタンに行っていました。
そして今年はguestであって随行員ではなかったのですが、暇なので翻訳のお手伝いをしました。
大会期間中撮りためた写真をtumblrにまとめたので、IOIの様子が気になる方や、わふれるかが見たい方はどうぞ。
JOIの写真速報もあります。
IOI後
IOI2016の優勝者jcvb氏と帰りの空港で会ったので少し話しました。
結構前なので記憶が曖昧ですが、名前の由来についての話題をきっかけにして話しかけた気がします。
"jc"は本名のイニシャルで、それだと短すぎてIDが取れなかったので適当に2文字つけたと言っていたと思います。
出題の件に関しては「ロシア人が作ったのかなと思っていたが、コーチから日本人が作ったらしいという話を聞いた」みたいなことと、問題に関する良好なフィードバックがもらえて嬉しかった憶えがあります。
その数ヶ月後、CodeFestival 2016でksun氏に「are you snuke?本戦のwriterだよね、reverseの問題良かったよ。」的な感じで話しかけられました。
ksun氏はIOI2016にもカナダ代表で来ていたのでIOIの話題を振って「IOIの問題も書いたよ。」「ま?あの問題面白かった。本番中は解けなかったけど後で解いたよ。」的な話ができて嬉しかった。
IOIへの出題は、こんな風にIOI後に海外勢と話すときに話題に出せるという特典もありますよ。
ICPC Tsukuba 2016 参加記
慶應義塾大学のチーム「Running」として参加し、3位の銅メダルでした。
メダルを取ることが出来たのは初めてで、とても嬉しいです。
時系列順で感想を羅列していきます。
コンテスト前日
つくばエクスプレスの車内で合流して、つくばのリンガーハットでご飯を食べた。
プラクティスでは、キーボードの癖の把握とスタックサイズの調査をすることにしていました。
キーボードは重めでびっくりしましたが、打ちやすくとても良かったです。
いつもはMacで⌘→で行末に移動しているので、Endキーを押さないと行末に移動できない環境には少し戸惑いましたがそんなに大きな影響はなかったです。
時間はあと15~30分ほど長いと嬉しいなと感じました。
会場の配線は、人が通る場所に線が、去年より心なしか少なかった気がする?
懇親会は帰りのバスを待つ時間が長くて、寒かったのもあってつらかったです。
ホテルについたら真っ先に大浴場に入った。
それから、peryaudoと近くのショッピングセンター的なところで買い物をした。
レジが半自動ですごかった。
ホテルに帰るときにライトアップされた変な建物を見つけた。
だいたいこういうのってラブホテルとかいうやつなんですが、それにしては大きいなぁと思って調べてみると、近くに保育園があって、教会系の結婚式場なのではという結論になった。納得した。
夜は結局寝れなかった・・・
結構眠気が強かったので寝れそうだと思っていたんですが、2時間ほど浅い睡眠をしたあとに廊下の声とかで起きてしまって、そこからは絶望の時間が始まりました。
なんか今年も1時くらいに暴走族がいたんですが、これIOIやったときにもいたら日本の印象的な意味でアレそう。
結局1~2時間くらいしか寝れなかった。
コンテスト当日
わりと眠かったですが、プリン食べてユンケル飲んで乗り切りました。(去年もそうした)
入場する前にタイピングソフトをやってみたところ、そこまで悪くない速度だったので少しだけ安心しました。
(これが遅かったら脳の回転速度が相当低下しているということで、やばかった)
コンテスト中の動向
うちの体制は、A,B をperyaudoに投げて、その間に先の問題を読んだり解法を考えたりしておくという感じです。
その後は2人に問題を読んでもらって、ライブラリ写してもらったりサンプル図示してもらったり手計算を投げたりとかする感じです。
A
開始直後peryaudoに投げたら一発で通してくれた。
D
Cが簡単だったのでperyaudoに投げてみて、Dからやった。
1回WAを出して直して投げたら、map<vector<int>,int>のせいでTLEしてしまった。
C
ジャッジ待ちの間にperyaudoに聞くと少し自信がなさそうだったので、自分でやることにした。
出力を改行区切りにしてしまって1WA食らった(だめやん)
D2
ハッシュに書き直して投げたけどWA。もうちょっとちゃんとハッシュを組まないといけなかったっぽい。
B
Cやってる間にperyaudoに読んでもらっていたので、やってもらった。1発ACいいぞー。
罠があったっぽいですが、少しのデバッグで乗り切ってたのはさすがっすね。
コーディングしてもらってる間に問題文を聞いたりした。
D3
vector<pair<vector<int>,int>>をsortすることにしたら通った。
TLEでハマるのはかなり泥沼なので、この程度のロスで済んだのはよかった。
ただ、ペナルティを結構食らったので、以降はペナルティをあまり意識しない方針にした。
G
E,Fがパッと見では分からず、順位表見たらGが解かれていたのでGに行く。
はじめsetを書こうとしたけど使わなかった。
細かいバグを何回か埋め込んで、3WA食らった。
E
Iが見た目簡単そうに見えたけど、WAしてるチームがあったしやめといた。
(そのとき考えてた方針は結局計算ミスしてて全然ダメだった)
次にやるものがないなーと思っていたけど、Eは同じ記号を違う文字に割り当てられないのに気づいて、それならただの実装問題やんとなり、これをやることにした。
再帰下降構文解析は頭を使わずに書くだけでいいので楽ですね。
末尾に'$'とかをつけておくと配列外参照とかを防げて楽でした。
(イテレータを正しくインクリメントするのだけは気をつけないといけないけど)
文法が正しいかまで含めて式を評価しないといけない問題だったので少し不安だったけど、1発で通ってびっくりした。
F
Jが解かれていたけど幾何だし、通してた中国チームはなにか類題を見たことがあったっぽい雰囲気を感じたのでやめた。
とりあえずFに取り組んだ。
問題設定がなかなか独特で、どうアプローチすればいいのかに悩んだ。
2-SATっぽい雰囲気のある設定だったけど、全然そんな形にはできなさそうだった。
mineとサンプルの具体例を構成してみた。
sample3がなぜYesなのかを考えていると、大体の条件はfalseにして置けばOKなことに気づいたので、その方向で考えていくと解法がわかった。
計算量は適当でも間に合いそうだなーと思っていましたが、BFSで次の辺を見つけるパートを合計O(N^3)でやらないといけないことに気づき、少し考えたけど、すぐ分かって良かった。
@sigma425 WFっぽいところ?a→bを繋いだ時、x→aがあればx→b と b→xがあるときにa→x の2通りの遷移だけで良い。
— 走りませんでした (@snuke_) 2016年10月16日
あとで聞いた話だと、64bit高速化とかで乗り切ったチームとかもいたっぽいですね。
解法の証明は甘々にしかしてなかったので怖かったですが、1発で通ってびっくりした。
この問題不思議な問題で、なんかプロコン慣れしてる人ほど苦しんでたんじゃないかと思います。
解法自体のユニーク性、O(N^3)に落とすパート、面白い問題だと思いました。
少し感動して気持ちが上がった。
この時点では2位だっけ。
H
とりあえずIの両辺が10^9の正方形のケースでの解答の構成をチームメイトに依頼して、Hを考えた。
なかなか一筋縄ではいかないなぁと思った。
とりあえず、無限判定について考えてみると、無向辺で繋がってる頂点を縮約してやるといい感じになることに気づいた。
無向辺だけ見たときにサイクルがあればダメで木になるので、木を頂点としたDAGで最長経路を求められれば良さそうとなる。
木の最長経路パートは、
Hの木パートは、各頂点に長さhogeの鎖が付いてると考えれば、直径・中心があることが分かるので、直径の端点2つからの距離のmaxを取ればいい。
— 走りませんでした (@snuke_) 2016年10月16日
「木に分解」「DAGを作る」「DFSする」「DFS内でダブルスイープ」とやることを分かりやすいパートに分割出来て、あまり頭を使わずに実装できるので量は多めだけど楽な実装だった。
それでも量は多い実装なので、1発で通ってびっくりした。
「木を頂点としたDAGにすればいい!」って気づいたときは感動しました。
また、グラフを変換する方針があるらしいです。
Hはdp[e,向き]=eをその向きに沿って移動したあとの最大パス長 を計算すると ∑(次数)^2 だけかかってダメなんですが、各頂点を次数の分だけ複製して重さゼロのパスで繋いで隣接辺が分散するようにすると次数が3以下になって線形時間になります 実装もそこそこ楽?
— *IRU (@ir5) 2016年10月16日
面白い方針だと思ったのですが、少し実装の見通しが悪くバグのリスクが高いこともあり、僕なら木に分解する方針を選びます。
一般に「自分の書き慣れた形」を組み合わせてコードを書いていくとバグを出しにくくなる気がしています。
I
Hやってる間にmineが一辺10^9の正方形の構成を思いついてくれて、それを長方形に拡張したときに何が問題になるかとかの部分まで考えてくれていて、それを聞いたら解法を思いついた。
制約からルートで分割しそうなオーラは感じていたんですが、どういう分割をするのかは思いついてませんでしたが、チームメイトと議論してるうちに正しい解法へとたどり着けました。チーム感を感じたり、そもそも解法が面白くて感動したりで、気持ちが上がった。
extgcdあんまり使い慣れてなかったので不安でしたが、1発で通ってびっくりした。
この時点では4位と2完差の3位だったし、9完が出てもペナルティで勝てそうだったので3位を確信して少し肩の荷が降りました。
K
上にも下にも差があったので解いてもあまり変わらなさそうでしたが、1時間弱あったしやりました。
気が抜けたこともあり、睡眠不足が効いてきて意識朦朧としてました。
peryaudoと話してたら和んだ。
結局解けず終了。
-
-
- -
-
とりあえず解けなかった問題に関しても感想を書きます。
J
三角形と円の共通部分面積のライブラリは持っていたのですが、探索方法が思いつきませんでした。
解説でいろいろアルゴリズムが紹介されていてすごかった。
きゅうりに教えてもらった解法を上げておきます。
x軸方向とy軸方向で独立に3分探索をします。
というのも、多角形が凸多角形なため、x軸方向だけで中心を動かすと凸関数になっています。y軸方向もしかりです。
なので、x軸で3分探索をして、その評価関数内でy軸方向の3分探索をすれば良いです。
補足:まず、例えば長方形のときとか凸関数ではない。(ただ値が変化しない区間は必ず最大値を取るということは証明できるかもしれない)
あと、面積が0になる区間はうまく避けないと三分探索が機能しないので注意しないといけない。
K
唯一不満を持った問題です。理由は思いつきようがないようなマイナーな知識を要求するだけの問題だからです。(申し訳程度の半分全列挙はありますが。)
いや「こんな知識を知ってるなんて、よく勉強してるなぁ」という風に、一応一理はあると思うんですが、デメリットの方が多いと思います。
あまりマイナーな知識を要求されると大会に対する対策のしようがなくなり、モチベーションが下がります。
また、ICPCはネット検索などもできず論文を検索したり出来るような大会ではないので、「出典:〇〇」のような問題は少し場違いに感じます。
参加者のフィードバックとして参考にしていただけると幸いに思います。
ただ、この知識自体はとても興味深いものです。
もしブログなどで出会ったとすれば素直に感動したりしそうです。
出典の本に関しても関心が高く、ぜひ読んでみたいと思います。
コンテスト後
体調最悪で、解説まではだいたい寝てました。
PFN勢がたくさん来ててすごかった。
解説は結構じっくりやってました。
順位表解凍はネイティブな感じでいい感じでした。
終了時の予想通り、前述の通り3位でした。
ただ、1位が全完していたのは予想外でした。SJTUさすがだなぁ。
3位はつくば賞とPFN賞をもらえました。
PFN賞です。(完全に社長の趣味ですね、間違いない pic.twitter.com/iDYgf2nKq5
— 走りませんでした (@snuke_) 2016年10月16日