うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

DDCC2016 参加記

AtCoder DDCC

これは
ひとり Advent Calendar 2016 - Adventar
の3日目の記事です。



DDCC2016に行ってきました。



人権が少ないタイプのコンテスト


コンテストの結果としては、A, B, Cの部分点は50分そこそこで取れて、Cの嘘解法がなぜか1WAしか出なくて、解法を見つけるというより嘘解法でごり押して通そう！ って方にシフトしてしまい結果1時間座ってるだけになってしまった😇

結果は2完1半で43位でした。
うーん、2ページ目までには入っておきたかった、というか3完したかった。



🍣とかちょこふぉんでゅとか食べた


講演会、厚切りジェイソンさんとDISCOの方のお話を聞いた。
厚切りさんは普通に有能な人という感じだったし話も面白かった。


KKM(かしこいかわいい森田)




葦くんが酔って顔が真っ赤になっていた



おまけ



結局寿司食べて酒飲んだだけになってない…？

CODE FESTIVAL 2016 参加記 ver0.1（ほぼチームリレー（優勝）について）

CODE FESTIVAL

宣伝

コード祭りの参加記については
ひとり Advent Calendar 2016 - Adventar
の序盤の記事としてもっとちゃんと書きます。

今は、簡単な総括と、あと“““圧勝を収めた[要出典]チームリレー”””について何が起きたのか適当に書きます。
（チームリレーに関してはおそらくjapljさんやきゅうりさんも書かれると思いますが、私は自分の問題が開始6分で終わったのでわりと全体の様子が見れてたんじゃないかなぁ、と思うので一応私も書きます）

AdCの期間中に、いつも通りツイートとともに振り返るみたいな記事として生まれ変わる予定なのでクソAdCの方もどうぞよろしくお願いします。

一日目

本戦

まさかの4完(49min)で133位でした。まさかのatcoderのレートが微減しました。まさかのatcoderレート黄色内で最下位でした。

この結果は自分でも本当に想定外で本当に落ち込んでいるのですが、ただ、数少ない人々から4完だったの意外、と言われて少しだけ他に認めてもらえるくらいの実力がついてきたのかもなぁ、と少し嬉しくもありました。


（問題についてとか詳しい話を後日追記）

touristのtalk


これめっちゃ好き（自画自賛）

暇な時間

🍣🍖🍕を食ったのち、ボードゲームとかカードゲームとかして遊んでました。たのしい。

エキシビジョン

オープンの方でuwiさんが早々にBを通していてすごいなぁとなった、オンサイトの方は、やはりチームワークは大事という感じがあった。

ホテル

間違って隣のホテルに入ってしまいフロントで困り果てるとかいう面白イベント（面白くない）がありました。
今回は睡眠妨害コンテンツがなかったので酒を入れたのち2時前くらいに寝たと思います。

二日目

asa

起床成功、ホテルのサービスコーヒーを飲みつつ会場まで歩く。

トーナメント

最終的にマージされる32人のうち唯一atcoderのレートが黄色、本戦での爆発炎上もありとてつもないプレッシャー。
結果としては無限にバグを踏み抜き、本当にギリギリで最後まで勝ち抜きました。
壇上でtouristと並んで写真を撮った（！！！）



うちわ、家まで持って帰ってきてみると本当にただの単色のうちわなのでなんかロゴくらいは欲しかった


内容は本当に散々だったがギリギリ結果を残せたので本当によかった


（TODO : もう少し細かく）

昼〜


トーナメントの商品であるところのステッカーを貼り、ついにMBAがステッカー台紙と化した。



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が空いている時間もほぼなかった。
（なんか考えれば考えるほど本当に完璧すぎるチーム戦だったのでは？？？）


という感じでした。

f:id:riantkb:20161127223306p:plain

f:id:riantkb:20161127223317p:plain
こちらが、各問題のAC時間になります（全提出は見る権限がなかった）


トーナメントと合わせて2回も壇上に上がれてほんま嬉しい。



（TODO : 全体の感想とか、今後の目標とか）


ひとり Advent Calendar 2016 - Adventar
を、お楽しみに！！！

コード祭り予選突破練習会をやりました

CODE FESTIVAL

やりました。


・開催1ヶ月半前


宇宙ツイッタラー(@kenkoooo)さん主催で今年も練習会が開かれ、今年も参加させていただきました。
そこでおよそ3分の1が東工大生だったので、これは学内で開いても集まるのでは？ と思い、学内で練習会したいなぁと思い始める
なんか週に1回のペースで言ってるなこいつ

rogyの合宿で酔っ払いながら酔っ払ってるyosupotに絡む


・開催2週間前
予選Aで通れて気を良くしてしまい、練習会開催にとても前向きになる


・開催1週間前
なんかrogy(所属している技術系サークル)の部会でしゃべりたかったら喋っていいよ、と言われ一晩でコード祭りを大雑把に説明するスライドを作る

www.slideshare.net
そのまま適当に日時を決める


これが一番つらかった


それはそう


・開催2日前
D, E問題用問題を集めようとするも地力が足らない、くまったくまった……って言っていたらyosupotが颯爽と問題を追加してくれた
あと宇宙ツイッタラーさんに唐突にatcoder problemsの仕様変更をお願いする（本当にありがとうございました…！）


・開催1日前
バイトに勤しむ


・開催5時間前
初めて車🚗を運転する



・開催2時間前
問題セットを公開
コード祭り予選突破練習会問題セット - Google スプレッドシート
この問題セットはきっとめっちゃ有用なのでみんな活用していこう！


・開催10分後
練習会サイトを公開
A問題 : AtCoder Problems
B問題 : AtCoder Problems
C問題 : AtCoder Problems
D問題 : AtCoder Problems


練習会で具体的にどう解いていってもらうかをわりと考えていかなかったので、予想通りけっこうグダグダになってしまった気がする
でもまたやりたいなぁ（今度はちゃんとコンテンツを用意して臨みたいなぁ…！）

CODE FESTIVAL 2016 予選A 参加記

CODE FESTIVAL AtCoder

コード祭り2016の予選Aに出ました。
ABCDの4完で全体107位、日本人40位でした。registerフェーズで落ちてなければ予選突破してそう。



・開始

　配点が 100 - 200 - 400 - 800 - 1200 なのでとりあえずCを解かなきゃ話にならないなぁと思いCから開く
　解法はすぐ思いついたが無限にバグらせて4WA


・20分経過

　ひいこら言いながらCを通す
　順位表みたら300位とかでおいいいいい、っつった


・25分経過

　B, Aと通してDを開く
　{(a_{i, j} - a_{i, j + 1})} が {i} に依存しないかつ {(a_{i, j} - a_{i + 1, j})} が {j} に依存しないことはすぐ見えたけどわからず


・40-45分経過

　下のツイートの解法を思いついて実装する（自分はハマらなかったけどグラフが連結でない可能性があるので注意）


・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
　


あとはゆっくり順位表を眺めてました
（コンテストが終わったあと考察したらこれEのほうが簡単じゃない？ ってなった）


とりあえずホントにどうなることやらって感じだったのでホントにホッとしています...


今年もパーカー得たい〜〜〜！！！



あと、予選Bまでに東工大内でコード祭り予選突破練習会開きたいです、協力者(というか主催者)募集中です

ハーフパイプ(2) 解説？

yukicoder

今回、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だとあんまりしないですけど、そこまで競プロになれてない人だと逆にこっちで頑張るのが自然かも、とも思いました。