CODE FESTIVAL 2016 参加記 ver0.1(ほぼチームリレー(優勝)について)
宣伝
コード祭りの参加記については
ひとり Advent Calendar 2016 - Adventar
の序盤の記事としてもっとちゃんと書きます。
今は、簡単な総括と、あと“““圧勝を収めた[要出典]チームリレー”””について何が起きたのか適当に書きます。
(チームリレーに関してはおそらくjapljさんやきゅうりさんも書かれると思いますが、私は自分の問題が開始6分で終わったのでわりと全体の様子が見れてたんじゃないかなぁ、と思うので一応私も書きます)
AdCの期間中に、いつも通りツイートとともに振り返るみたいな記事として生まれ変わる予定なのでクソAdCの方もどうぞよろしくお願いします。
一日目
本戦
まさかの4完(49min)で133位でした。まさかのatcoderのレートが微減しました。まさかのatcoderレート黄色内で最下位でした。
この結果は自分でも本当に想定外で本当に落ち込んでいるのですが、ただ、数少ない人々から4完だったの意外、と言われて少しだけ他に認めてもらえるくらいの実力がついてきたのかもなぁ、と少し嬉しくもありました。
(問題についてとか詳しい話を後日追記)
暇な時間
🍣🍖🍕を食ったのち、ボードゲームとかカードゲームとかして遊んでました。たのしい。
エキシビジョン
オープンの方でuwiさんが早々にBを通していてすごいなぁとなった、オンサイトの方は、やはりチームワークは大事という感じがあった。
ホテル
間違って隣のホテルに入ってしまいフロントで困り果てるとかいう面白イベント(面白くない)がありました。
今回は睡眠妨害コンテンツがなかったので酒を入れたのち2時前くらいに寝たと思います。
二日目
asa
起床成功、ホテルのサービスコーヒーを飲みつつ会場まで歩く。
トーナメント
最終的にマージされる32人のうち唯一atcoderのレートが黄色、本戦での爆発炎上もありとてつもないプレッシャー。
結果としては無限にバグを踏み抜き、本当にギリギリで最後まで勝ち抜きました。
壇上でtouristと並んで写真を撮った(!!!)
#codefes #code_festival pic.twitter.com/LeGUtcTLKG
— 148_りあん (@rian_tkb) November 27, 2016
うちわ、家まで持って帰ってきてみると本当にただの単色のうちわなのでなんかロゴくらいは欲しかった
Round1 : 2位通過(200 + 100)
— 148_りあん (@rian_tkb) November 27, 2016
Round2 : 4位通過(200 + 200)
Round3 : 3位通過(0 + 400)
でした(めっちゃ調子がクソだった、やはり早解きコンテストは無理) #CODE_FESTIVAL
内容は本当に散々だったがギリギリ結果を残せたので本当によかった
(TODO : もう少し細かく)
昼〜
#codefes #code_festival pic.twitter.com/Yf4ovO2SC8
— 148_りあん (@rian_tkb) November 27, 2016
トーナメントの商品であるところのステッカーを貼り、ついにMBAがステッカー台紙と化した。
UFOキャッチャーでタオルゲット! #codefes #code_festival pic.twitter.com/64bJpo83oQ
— 148_りあん (@rian_tkb) November 27, 2016
UFOキャッチャーでタオルをゲット! アームがクソ固くて普通のゲーセンの金を吸い込むUFOキャッチャーとは比べ物にならないくらい楽だった。
広げてみると普通にバスタオルサイズでびっくり
チームリレー
お待たせしました。
チームMは、海外勢が ksun48 さん、日本勢は japlj さん、きゅうりさん、kzyKT さん他。
方針としては、始まったら簡単な問題が解きたいと申告した4人がA~D、残りからksun48さん、japljさん、きゅうりさんを除いた4人がE~Iくらいまで、ksun48さんはJだかKだかを一人一問読み、解法まで至らなくても問題概要がわかったらそれをjapljさん、もしくはきゅうりさん(確かA~Dをjapljさん、E~をきゅうりさんに、みたいな感じだったと思う)に伝えて、解法・実装を練ったのち誰かに実装を回す、みたいな感じで行こうという話になりました。
結果的にこの方針は、結局ほとんどの人が最初に自分が読んだ問題の実装を担当することになった、という点以外はこのまま進んだと思います。問題の数と人数が等しいので、この点についてはもう仕方ないと思います。
以下、大まかに時系列順になります(時間が前後していたりする可能性が大いにあります)
とりあえず始まると、私はE問題が目についたのでE問題を読みました(本戦がボロボロだったので弱気になっていた部分が大きいと思います)。
(x/gcd + y/gcd - 1) * gcd が答えなのはすぐに気づけたので、問題概要とともにきゅうりさんに説明、GOサインが出ると同時にA問題が通ってPCが空いたので、ささっと書きに行きAC。E問題で6:32なのでさすがにFAであってほしいが。
その後B, Cが通り、Dが少しバグっていて先にFが通る。
その間私はGにちょっかいを出しに行っていた(こうじゃね? みたいなことを言ったが結局自分でよりシンプルな解法を思いつかれていて何もしてない感がある)。Dが詰まっていてPCが空いていたので先にGをコーディングしてくるように言う(何様のつもりだ)(しかもこの時、解法の信ぴょう性を疑っていた)。
そんなうちにDがなんとかなる。A~F 6完が 31min(これはそこまで良いタイムというわけではなかったと思う)。
その頃、実はまだHが誰にも読まれていないことに気づく。読むと 24 * 60 * 60 (秒)でModを取った後 3 * 60 * 60 (秒)の区間に含まれる点の最大を求めればいいとわかる(ただ、アホなのでRMQなのでBITとか言った(どう見ても累積和でやるべき))。きゅうりさんに見せる。
Gがバグっていて、ますます解法の信ぴょう性を疑う。ただ、手元では合ったはずのサンプルもWAになっているので、コーディングのミスだろうなぁという気。
そんな頃、まさかのIが通る。kzyKTさんがガチプロで、一人で考察を進めて一人で通した。わけわかめ。
さらに、ksun48さんがKの解法をjapljさんに投げた後、自分はJを通しに行った。3, 4分で帰ってきた。あたまおかしい。
その間、何をしていたかと言うと、japljさんと二人でGのソースコードのデバッグをする。幸い、単純なifやforの条件ミスで、すぐに通る。解法疑ってめっちゃ申し訳ない。
残った2問、まずH問題をきゅうりさんが書きに行く。サンプル以外全部RE。japljさんに交代。a_0 + b_0 + a_1 + ... がオーバーフローして添え字がマイナスになっているのでは、という話になったがサンプル以外全部REなのは違和感があったので注意深く確認する。が、やっぱりそこしかなさそう。
そんなこんな言ってる間にjapljさんが帰ってくる(最後の問題のコード、dfsとか書いてあってそこそこ実装ありそうなのになんか5分くらいで帰ってきた、まったくもうなんやねん)。
きゅうりさんが走ってオーバーフローを処理したコードを提出。
全員でジャッジを見守る。
二人のコードが同時にジャッジが終わり、両方ともAC。おそらく10完していたチームを2つくらい颯爽と抜き1位になる。
おそらく勝因は、各人が与えられた問題をしっかり解けた、というところだと思います。解法が全くわからなくて japljさんやきゅうりさんに泣きつく、みたいなシーンはほぼ見なかったように思います。特にksun48さんとkzyKTさんがガチプロしていて、結果japljさんときゅうりさんが本当に実装するだけ、みたいになったのは本当に良かったと思います。
また、あまりどハマりすることもなく、一番多くWAを出した問題でも2回、全体で5回しか出していないのも本当に良かったと思います。
あと、サンプルが通らない場合はとりあえず提出してモニタの方でバグを探す、としたのも本当に良かったです。ICPCでもとりあえずソースコード印刷しようと思います。
PCが空いている時間もほぼなかった。
(なんか考えれば考えるほど本当に完璧すぎるチーム戦だったのでは???)
という感じでした。
こちらが、各問題のAC時間になります(全提出は見る権限がなかった)
トーナメントと合わせて2回も壇上に上がれてほんま嬉しい。
(TODO : 全体の感想とか、今後の目標とか)
ひとり Advent Calendar 2016 - Adventar
を、お楽しみに!!!
コード祭り予選突破練習会をやりました
やりました。
コード祭り予選突破練習会@大岡山【非公式】 #atnd https://t.co/1WdPuvGBUO
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年9月28日
・開催1ヶ月半前
【初心者向け】 CODE FESTIVAL 予選突破練習会 【非公式】 #atnd https://t.co/ZZBfhrOzE1
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年8月21日
宇宙ツイッタラー(@kenkoooo)さん主催で今年も練習会が開かれ、今年も参加させていただきました。
そこでおよそ3分の1が東工大生だったので、これは学内で開いても集まるのでは? と思い、学内で練習会したいなぁと思い始める
そう、東工大生向けのコード祭り練習会したいなぁと思っている
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年8月22日
なんか週に1回のペースで言ってるなこいつ
そういえばコード祭り予選突破練習会inたいてくしたいって言ってる
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年8月30日
コード祭り予選突破練習会いんたいてくしたい
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年9月4日
rogyの合宿で酔っ払いながら酔っ払ってるyosupotに絡む
そういえば昨日だか一昨日だかに酔っ払いながらよすぽにコード祭り予選突破練習会開いてって言いまくった気がする
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年9月16日
・開催2週間前
予選Aで通れて気を良くしてしまい、練習会開催にとても前向きになる
・開催1週間前
なんかrogy(所属している技術系サークル)の部会でしゃべりたかったら喋っていいよ、と言われ一晩でコード祭りを大雑把に説明するスライドを作る
そのまま適当に日時を決める
これが一番つらかった
ところで問題の傾向が大きく変わってしまったのでこの前の練習会で作った問題セット( https://t.co/1SRmn6ahdd )が役に立たなくなってしまった
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年9月28日
それはそう
🍣はね、予選通過してリリリーリの金で食べてくれ、練習会では出ません
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年9月29日
・開催2日前
D, E問題用問題を集めようとするも地力が足らない、くまったくまった……って言っていたらyosupotが颯爽と問題を追加してくれた
あと宇宙ツイッタラーさんに唐突にatcoder problemsの仕様変更をお願いする(本当にありがとうございました…!)
・開催1日前
バイトに勤しむ
ばおわや
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年10月5日
・開催5時間前
初めて車🚗を運転する
乗るぜ🚙🚙🚙💨💨💨 pic.twitter.com/iUl0dkhw0S
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年10月6日
ところで昼に今日の問題セットを公開するつもりがぶーぶをぶーぶーしてました
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年10月6日
・開催2時間前
問題セットを公開
コード祭り予選突破練習会問題セット - Google スプレッドシート
この問題セットはきっとめっちゃ有用なのでみんな活用していこう!
・開催10分後
練習会サイトを公開
A問題 : AtCoder Problems
B問題 : AtCoder Problems
C問題 : AtCoder Problems
D問題 : AtCoder Problems
コード祭り予選突破練習会、始まりそう pic.twitter.com/uOc5IGSI06
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年10月6日
練習会で具体的にどう解いていってもらうかをわりと考えていかなかったので、予想通りけっこうグダグダになってしまった気がする
でもまたやりたいなぁ(今度はちゃんとコンテンツを用意して臨みたいなぁ…!)
CODE FESTIVAL 2016 予選A 参加記
コード祭り2016の予選Aに出ました。
ABCDの4完で全体107位、日本人40位でした。registerフェーズで落ちてなければ予選突破してそう。
・開始
配点が 100 - 200 - 400 - 800 - 1200 なのでとりあえずCを解かなきゃ話にならないなぁと思いCから開く
解法はすぐ思いついたが無限にバグらせて4WA
・20分経過
ひいこら言いながらCを通す
順位表みたら300位とかでおいいいいい、っつった
・25分経過
B, Aと通してDを開く
が に依存しないかつ が に依存しないことはすぐ見えたけどわからず
・40-45分経過
下のツイートの解法を思いついて実装する(自分はハマらなかったけどグラフが連結でない可能性があるので注意)
こんなグラフを作って幅優先して、距離が異なるパスが発見されたらNo、ってした pic.twitter.com/pSRcHULB9K
— りあん♨🍶 (@rian_tkb) 2016年9月24日
・60分経過
実装して提出する
Submission #895510 - CODE FESTIVAL 2016 qual A | AtCoder
サンプルが一個落ちていることにより入れる値が負数じゃダメだという条件を見逃していることに気づく
・75分経過
列の最小値を持って幅優先探索中に更新していけば良さそうと気づいて実装を始める
・85分経過
実装したがWAが取れない
Submission #896588 - CODE FESTIVAL 2016 qual A | AtCoder
仕方ないから幅優先探索後にめっちゃループ回してさらに最小値を更新するか〜〜〜って言う
・90分経過
1 ケ ー ス WA
Submission #896888 - CODE FESTIVAL 2016 qual A | AtCoder
・100分経過
最後のループで300回以上更新があった場合もう負数になるんじゃね? ってNoを出力するコード出したらAC
(コンテスト後にsubmit二分探索したら30回ほどで打ち切って大丈夫だったらしい)
不正感しかないけど通ったからいいんだもん...!
Submission #897265 - CODE FESTIVAL 2016 qual A | AtCoder
不正感が強い pic.twitter.com/Wf66V4zpbh
— りあん♨🍶 (@rian_tkb) 2016年9月24日
あとはゆっくり順位表を眺めてました
(コンテストが終わったあと考察したらこれEのほうが簡単じゃない? ってなった)
とりあえずホントにどうなることやらって感じだったのでホントにホッとしています...
今年もパーカー得たい〜〜〜!!!
あと、予選Bまでに東工大内でコード祭り予選突破練習会開きたいです、協力者(というか主催者)募集中です
ハーフパイプ(2) 解説?
今回、testerをさせていただきました。
問題はこちら
No.398 ハーフパイプ(2) - yukicoder
まずはwriterさんの解説をご覧ください
http://yukicoder.me/problems/no/398/editorial
この問題、想定解法は埋め込みです。testerで問題をもらった時 6*100*100*600*100 = 36億 から落ちないよぉふぇぇ... ってなって解説をカンニングして、は〜〜〜、ってなった記憶があります。
ただ、ちゃんと定数倍改善を行えばこのオーダーでも C++ で 250ms, C# で 900ms で通る(かつ埋め込みのための列挙がほぼ同じ時間でできる!)ようになります。まずはその解説から。
まず dp[index][min][max][sum] というDPを考えます。これの更新式は以下のようになります。
for m in {0..100}:
dp[i + 1][min(j, m)][max(k, m)][l + m] += dp[i][j][k][l]
初期化については、一番左に置く数について埋め込み、
dp[0][i][i][i] = 1
としてしまうのが楽だと思います。
このdpの場合、
sum = x * 4とし、
for i in {0..100}:
for j in {i..100}:
ans += dp[5][i][j][sum + i + j]
とした ans が求めるものです。
このままやるともちろんTLEしますが、端的に言うと dp[i][j][k][l] == 0 の場合に m のループに入らないようにすれば良いです。
というのも、dp[i][j][k][l] == 0 となる場合が(定数倍の範囲内ですが)そこそこあり、その時に内側のループに入らないようにしてあげればループ回数がおよそ1億回ほどになり、C++等で通ります。C#でも1300msほどで通りましたが、Python等の言語では厳しいと思います。
(参考 : http://yukicoder.me/submissions/103388,
: http://yukicoder.me/submissions/103389,
: http://yukicoder.me/submissions/103496)
また、dp[i][j][k][l] > 0 となる l の範囲は連続なので、そこだけループを回すようにしてあげればもう少し早くなります。
(参考 : http://yukicoder.me/submissions/103467,
: http://yukicoder.me/submissions/103495)
dp[i][min][max][sum] > 0 なる sum の 範囲は、
最小値が min + max + max + ... + max = min + max * i,
最大値が min + ... + min + min + max = min * i + max となるので、そこだけ回すとC++で250ms, C#で900msほどになります。
まぁ詳しくはソースコードを読んでください。
さて、そして問題のなんか場合分けして速いの(http://yukicoder.me/submissions/103511)についてですが、オーダーとしては 100^3 です。
やってることとしては単純で、
a + b + c + d + sum && a <= b <= c <= d
なる (a,b,c,d) を全探索し、一つ一つに対して min <= a なる min と d <= max なる max を追加した時の並べ方の場合の数を数え上げています。
min と max については、
・min == a && d == max
・min < a && d == max
・min == a && d < max
・min < a && d < max
の 4通りだけ調べればOK。
並べ方の場合の数については、
{a,a,a,a,a,a} : 1
{a,a,a,a,a,b} : 6C1 = 6
{a,a,a,a,b,b} : 6C2 = 15
{a,a,a,b,b,b} : 6C3 = 20
{a,a,a,a,b,c} : 6P2 = 30
{a,a,a,b,b,c} : 6C1 * 5C2 = 60
{a,a,b,b,c,c} : 6C2 * 4C2 = 90
{a,a,a,b,c,d} : 6P3 = 120
{a,a,b,b,c,d} : 6P2 * 4C2 = 180
{a,a,b,c,d,e} : 6P4 = 360
{a,b,c,d,e,f} : 6P5 = 720
となります(実際に解いた時に用いたメモを紛失したので間違ってるかも...、変なとこあったら教えてください><)
あとはこれを落ち着いてコードに起こすと、以下のコードになります。
#include <iostream> using namespace std; int main() { int a, b; scanf("%d.%d", &a, &b); int sum = (a * 100 + b) / 25; long long ans = 0; for (int i = 0; i < 101; ++i) { for (int j = i; j < 101; ++j) { for (int k = j; k < 101; ++k) { int l = sum - i - j - k; if (l < k) break; if (l > 100) continue; int m = 100 - l; if (i < j && j < k && k < l) ans += 180 + (i + m) * 360 + i * m * 720; else if (i == j && j < k && k < l) ans += 60 + i * 180 + m * 120 + i * m * 360; else if (i < j && j == k && k < l) ans += 90 + (i + m) * 180 + i * m * 360; else if (i < j && j < k && k == l) ans += 60 + i * 120 + m * 180 + i * m * 360; else if (i == j && j < k && k == l) ans += 20 + (i + m) * 60 + i * m * 180; else if (i == j && j == k && k < l) ans += 15 + i * 60 + m * 30 + i * m * 120; else if (i < j && j == k && k == l) ans += 15 + i * 30 + m * 60 + i * m * 120; else if (i == j && j == k && k == l) ans += 1 + (i + m) * 6 + i * m * 30; } } } cout << ans << "\n"; return 0; }
もしこれが想定解法として提示されたら窓からMacBookAirを投げ出すレベルの解法ですが...
まぁこんな面倒くさい場合分け、競プロerだとあんまりしないですけど、そこまで競プロになれてない人だと逆にこっちで頑張るのが自然かも、とも思いました。
Segment treeを整備したという日記
(2019/10 追記:自分のライブラリを GitHub で管理するようにし始めたので、最新版が以下から参照できます)
github.com
最近Sumsegtreeを使う問題を解いたら、持ってたSumsegtreeがバグってたので、ついでにもっと色々使えるように手直ししたのでその備忘録みたいなものを書きます。
c#でのsegtreeのコード載せてるページ少ないし、ね。
なお、基本的に秋葉大先生のスライドをとても参考にさせていただいて作っているので俺の記事は読まなくていいのでこちらをお読みください
プログラミングコンテストでのデータ構造
以下コードです。
using System; class Segtree<T> { int n; T[] tree; Func<T, T, T> f; T exnum; public Segtree(int m, Func<T, T, T> f, T ex) { this.f = f; this.exnum = ex; n = 1; while (n < m) n <<= 1; tree = new T[(n << 1) - 1]; for (int i = 0; i < tree.Length; i++) tree[i] = ex; } public Segtree(int m, T ini, Func<T, T, T> f, T ex) : this(m, f, ex) { for (int i = 0; i < m; ++i) tree[i + n - 1] = ini; all_update(); } public void assign_without_update(int j, T x) { tree[j + n - 1] = x; } public void update(int j, T x) { int i = j + n - 1; tree[i] = x; while (i > 0) { i = (i - 1) >> 1; tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]); } } public void all_update() { for (int i = n - 2; i >= 0; i--) tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]); } public T look(int i) { return tree[i + n - 1]; } // [s, t) public T run(int s, int t) { return query(s, t, 0, 0, n); } T query(int s, int t, int k, int l, int r) { if (r <= s || t <= l) return exnum; if (s <= l && r <= t) return tree[k]; return f(query(s, t, (k << 1) + 1, l, (l + r) >> 1), query(s, t, (k + 1) << 1, (l + r) >> 1, r)); } }
(2016/04/19 : iniが指定されていない時にexnumで初期化するように設定しました)
(2016/10/03 : 色々細かいところを修正したのと、全体の初期化を でなく で実現するための関数を追加、あと半開区間にしました!)
まず、型を自由に指定できるようにしてあります、これは基本的にはlongにしとけばどうにかなるのであんま意味ない気もしますが、doubleにしたい時とか
D: タコヤキオイシクナール - AtCoder Regular Contest 008 | AtCoder
とかだとまぁ楽かなぁという気がします。
それでは、変数の解説をしていくと、
・Func
Func
また、MaxとかMinだと Math.Max とか Math.Min を渡してあげるだけで動きます、嬉しい。
その他でも、f(x1, f(x2, x3)) = f(f(x1, x2), x3) を満たす関数なら動くのかな...? 理学部じゃないのでわからん。
・T exnum
exnum は、区間が範囲外の時に返す値を入れる変数で、とても弱い値を入れておけばokです。例えば、Sumの時は0, Maxの時は-∞, Minの時は+∞, といったように。
・T ini
ini は、初期化用変数です。別にいらないような気もするかもですが、Tがclassだったりすると馬鹿みたいにランタイムエラーを起こすのであったほうが良いです。
あとは前述したスライドとほぼ同じなので、これで使えます。
一番の肝はコンストラクタで初期化する時で、そこがちゃんと出来てしまえばあとは毎回同じように使えます。めっちゃ嬉しい。
こちらが使用例になります。
Submission #694898 - AtCoder Regular Contest 033 | AtCoder
Submission #694924 - AtCoder Regular Contest 008 | AtCoder
#118362 No.426 往復漸化式 - yukicoder
(2016/10/03 : 使用例を追加しました)
最小費用流とか平衡二分探索木とかも持っとかなきゃなぁという気はしてる(書く気は起きない)。