ACM-ICPC 2018 国内予選 参加記

ACM-ICPC 2018 国内予選に参加しました。

RiPProとしては「priMe.caT」「2,3,4回生チーム」「2回生チーム」の3チーム参加してました。

メンバーは「ixmel, T.M, rika(そすうさ)」

 

ixmel:前川みく担当

T.M:考察担当

rika:サポート

5月ぐらいからチーム練習をして頑張ってた。

今年がICPC最後なのでアジア地区に行きたい気持ちが高かった。

模擬国内予選が終わってからコンテスト練習みたいなことをしていなかったね。

 

前日

大雨で当日電車が止まる宣言をされたのでやむなくラボ後輩の家にお泊り

 

当日

 前日からT.Mから連絡がとれなくてめちゃくちゃ焦る。

 

駅前の銭湯にいく。良かった。

 

T.Mと連絡がつく。いかばっかりしてないで。

開始前バタバタしてて2秒ぐらいロスした。

 

コンテスト開始

rikaがテンプレ写経している間にABをよむ。

書き終わったところでバトンタッチ、AをAC。(A.8:03)

Bも書き終えるがバグる。サンプルを見ると想定していない折り方をされていた。

そのときはひっくり返してから折ることにしてサンプルが合う。投げる。

→ 「Empty Answer」(意訳)

ひぇぇぇ

入力データの1番目でセグってたことが判明する。怖すぎる。AC。(B.29:55)

Cに取り組む。解法は生えていたので実装する。AC。(C.37:09)

Dの安心できる解法がなかったので話し合うとやっぱり枝刈り全探索でいいんじゃないかとなったので書いて投げる。AC。(D.63:22)

この時点で4位だったのでテンションが上がる。

Eの適当解法を書く。サンプルが合わない(敗因.教訓1:適当な考察で実装をしない)

Eは考察得意なT.Mに投げてFに取り組む。

それっぽい解法が生えて実装してサンプルが合うが遅い。実行させといてEに戻る。(敗因.教訓2:高速化しろ)

T.Mが生やした解法を実装する。サンプルがあわない。泣いた。コンテスト終了。

 

よくみるとFの実装、logが2つついていた。えーん

帰宅時にlogを1つおとして実行させたが終わらない。おいおいマシンパワーで負けてないか

 

結果:4完 23位

去年よりかはいい順位だったがもっと上を狙えたはず...

この5年間5完以上できなかった。悲しい。わりと落ち込んでる。

 

おつかれさまでした。お祝いのにぼ

 

なにはともあれアジア地区にはいけそうです。そのころまでには圧倒的精進をして良い成績取るぞ

RUPC2018 参加記

参加しました。

 

来年以降参加しようと考えている方にアドバイス

 

DAY1

今年は昨年より参加人数がかなり増えていた。

知っている人がたくさん参加していたので楽しみ。

RUPCが始まる。

作問が燃える。

自己紹介フェイズが始まる。

うくにきあ様は本当に尊敬するにゃ(うさみんポジ)

 

コンテスト1日目は立命セット。

チーム数が多いので風船配りがなくなる。

水色以下の人が多いので今回は普段の立命セットのD問題レベルを2問作成することになった。

H問題(G問題レベル)を作っていたんですが当日までバグ祭りで、コンテスト直前に新たなバグが見つかったりしたのでコンテストに出すのを諦めた。

なので全完たくさん出るだろうなあって感じのコンテストになり申しました。

でも39分で全完はさぁ...(3時間コンテスト)

以下感想

Bは問題解読難でみくも異を唱えたが1回生に読ませてみると読めたようなのであのままになったにゃ。

クソコンテスト認定されるかとひやひやだったがそんなことなくてよかった。

 

懇親会はいかず、友人とラーメンを食べた。麦笑というラーメン屋。替え玉無料で実質食べ放題。

4玉食べるつもりが3玉で限界に。(お菓子たべたから)

 

運営特権でこの日は立命の施設でお泊り。

カタンをしてお風呂入ってカタンして寝た。

人々がゲーセンいっててうらやましかった。

 

DAY2

軽く寝坊しながら会場入り。

だらだらしてたらチノちゃんがおずおずと会場にやってきた!

みくアイドルなので2ショットしたにゃ。

RiPProの今後が不安です。

 

コンテスト2日目は会津セット。

簡単な問題、難しい問題がいっぱいなので乱択チームで出ました。

tosachiさん:toさん

こっそり歩くちゃん(椅子を温める)さん:iaさん

Aをtoさんになげ、Bをiaさんになげ、みくはお菓子を食べるにゃ。AC。

Cをtoさんになげる。toさんはpython勢らしいのでc++を布教しながらなんとかAC。

Dをiaさんになげる。解法をなげながらお菓子を食べる。AC。

この時点で1時間半。ひぇ。

残りで投げれるものはないかなと探すとFがとっつきやすそうなのでなげる。

その間他の問題を読む。EGIの大まかな解法を考える。

ACしたみたいなのでフローを流せるかと聞くとどうやら流せないみたいなのでHをなげてEGIをACする。おわり。

 

結果:ABCDFをお二人に投げてEGIを解きました。老害パワーを発揮した気がする。

コード書いている間お二人を放置してしまっていた感あるのでうーん。

 

懇親会は肉!

お肉たべまくってお酒もたくさん飲んで喉壊しました。

pulmn君を本名で言いかける。ミッション失敗。

 

その後RUPCゲーセン勢で膳所駅付近にあるレジャーランドにいく。

夜だったので人が少なく、いい感じの環境だった。

ひとしきり遊びみんなより先に離脱。とても楽しかったです。こたつがめ氏やママうまい。

疲れからか降りる駅を乗り過ごす。

 

DAY3

大幅遅刻した。ごめんなさい。

 

コンテスト3日目は北大セット。

Aをyazatenさん、BCをixmel、Dをpulmnが読む。

pulmnがDの実装初めてプロ。

合間にyazatenさんがAを実装してADをAC。

Bをyazatenさんと相談しうまい実装方法を考えながらyazatenさんが書きAC。

Eはpulmnにまかせ、Fが解けそうだったのでCは後回しにして先に手を付ける。

最短路DAGの抽出をyazatenさんの力をかりながら実装し、フローを流してAC。

ついでにCも実装しAC。

Gを見る。誤読はしてないが考えていくうちに誤読みたいなことしていた。

Aho-Corasickを持っていたので。勝ち。tourist。AC。

pulmn君がEに苦戦していたのでトイレに行って戻ったら終わってた。プロ。

1時間20分で全完(3時間コンテスト)。全完は初なのでうれしい。

NEW GAME 7巻の特典をどれにするかをpulmn君と言い争う。

本気のじゃんけんに負けてアニメイトの特典をもらうことになった。

ちなみにみくはメロンブックスの特典が欲しかったにゃ。

 

RUPCが終わる。お疲れさまでした。

 

RUPCゲーセン勢とゲーセンに行く。

京都行付近のイオンモールに行く流れになったがKONAMI系の音ゲーがないため(ボルテは一台あった)うーんって感じ。

 

 

最後に

いろいろ不手際はありましたが大きな問題なく終われたのでほっとしています。

来年も開催できたらと思います。ご参加お待ちしています。

 

ICPCアジア地区予選つくば大会2017

参加しました。
実はICPC参加4回目にしてICPCアジア大会は初。
(去年は国内予選惜しかったね)
チーム名:SIMnit
チームメンバー:ixmel, T.M, noy72
せっかくなので参加記を書きます。

事前訓練

US配列のキーボードを買い練習。
テンプレ増やす。
僕は英語ができない。
チームメイトの英語力向上を願う。

1日目

当日に新幹線の切符を買う。
事前購入したT.M君の指定席の隣がたまたま空いてたのでそこをとる。
デートアライブを読む。12,13巻未所持で14,15巻を買ってしまって辛い。

北千住まで行ってつくばエクスプレスに乗り換えると良いことをT.Mから教えてもらった。
来年に生かそうとしたが来年は横浜らしい。yataa

 

つくばに着くとペットボトルが大量に置かれている。謎。
実績解除:外国人さんに話しかけられる
?「hogehogehoge(どこいくの?みたいなこと)」
ixmel「Ah~~...(無言でcodefesバッグにあるcodefesマークを指す)」
?「Oh~」
会場の中に入ると強い人がいっぱい。空気が変わる。


noy君がいない。
noy君と合流。

 

開会式が始まる。英語。

Practiceが始まる。3問。
とりあえずEmacsの環境構築をしてみる。
やったことは、「行番号追加、C-zでUndo、現在いる行ハイライト、スタートメッセージをなくす」ぐらい。
あとAC,RE,WA,TLEを出してみる。
配列intの7000*7000がとれてマジ?となるが普通?。
forを10億回してみたらACしてマジ?となるが普通?。
C問題はめんどくさくなって解いてない。
Practiceが終わる。拍手。

 

WelcomeParty会場にバスで行く。
食べ物が茶色で覆われていてつらかった。

野菜と寿司も出してくれ。
チーム紹介が始まる。各チーム前に出て事前に送ったスライドを表示して少し話す。
チーム1英語ができないのにリーダー?だからみたいな理由でしゃべる羽目になった。

"miku-nya is so cute"と言おうとしたが恥ずかしくてやめた><(前川みくはかわいい!
ウクニキア様が素晴らしかった。見習わないと。
WelcomePartyが終わる。

 

2泊するのに5000円しかもらえなかったのでネカフェに泊まる。
近くにゲーセンがあったので1時間ほど遊ぶ。

ダーツやりたかったけどつかささんに叱られる><

漫画8冊ぐらい読んで寝た。
寝坊が怖くて、結局4度寝した。


2日目

朝シャンして良いasa!!をむかえた。
朝ダーツもした。501を2連続クリアできてうれしかった。またやりたい。

領収書の名前聞かれてつい自分の名前を言ってしまう。
ICPCネカフェ勢マジ?みたいなことtwitterにあったけど、
漫画読めてダーツできて安くてで逆になんでって感覚。

 

会場に行く。電子機器は中に持ち運べないのでtwitterとはおさらば。
緊張するなぁ。
タプリスの><の画像を印刷した紙を置く。(真ん中)

 

コンテスト開始

ID/Passwordの封筒を真ん中から破る。
noy君に環境構築をしてもらう間きれいに座る。
テンプレをうつす。その間2人には問題を読んでもらう。
大体書き終わる。Aの概要を聞く。DPじゃんとか言ってAを書く。AC。
Bの概要を聞く。えーDFSしたいなあとか言ってBを書く。AC。(この時点で6位ぐらい。yabai)
ここでCの概要を聞くつもりが問題が発生する。
!!!--Cの問題英語が読めない--!!!
らしい。こまったなあ。
解読お願いして適当にぱらぱらみる。英語わからずひるど。
Gをみて察する。
EとIの概要を聞く。Iのポリシーoneが読めないらしい。くまった。
Eを考えるがわからず。とりあえずDのポリシーtwo解法を書く。
結構体内時間たってなんだかんだしてCの概要がわかる。書く。AC。
結構体内時間たってなんだかんだしてIの全概要がわかる。書く。AC。

タプリスの代わりにサタニキアの画像を印刷した紙を置く。(真ん中上)
その他のよく解かれてる問題の概要を聞く。Fがやりやすそう。
考えるとHAPPYの判定は簡単で、SOSOかSADの判定をすればいい。
ダイクストラで使われる辺だけ考えると良いよねっていうとT.Mから橋を使う解法がふってくる。
多重辺にキレながら書く。AC。
その他問題わからんなぁとか言ってGに取り組む。
適当に平面にすると良い感じにまっすぐ線引けて良いねと言って実装するが、
平面にする方法が悪く次元が曲がり時間ぎれ。

 

5完15位でした。(この時点では順位はわからず)
6完または20位以上を目標にしてたのでまあ満足

 

チームメンバーには感謝とこれからもがんばれの気持ち。
チームに黄コーダーが欲しい。

 

解説が始まる。はい。
閉会式?が始まる。
偉い人のあいさつが長いかつ人数が多すぎる。解説の時間で育った眠気がピークに来る。

 

順位表解凍が始まる。
現状下位チームから順に凍結された結果が一つずつ解凍。
こんな感じなの初めて知ったので感動。
ACのときYES/NOおじさんがYES!!!いうて順位が上にあがってくの楽しい。
まあ自分の順位が下がるとあーーって感じですが。

 

飯&企業タイムが始まる。


飯を食べながら早いうちに企業ブースをめぐる。めっちゃいろいろもらう。
「帰ってきた!コネクションハント」があり、
20チーム(distinct)回答を集めるとTシャツがもらえるらしく、今回は頑張った。
お題は「目標にしてる人」で、touristで埋まるだろうなあと思ってたが、
「目標」なので越える気持ちをもつ必要があり回答に悩む人もいて、思ったより回答がばらけた。
ハントなのでいい感じの人に「めるです」と言って話しかけるんですが、意外と名前は知られてるらしく、驚く。
アナウンスで呼ばれたらしいが全く気付かなかった。

 

解散。お疲れさまでした。
自分はあと一回出場権があるので来年も頑張ります。

 

今度は新宿に向かう。
JAGの時に泊まったネカフェが安くてシャワー実質無料でほかに比べ良かったので。

着いたとき22:00ぐらいで今からネカフェ入るのは若干損なので23:30まで自由時間にすることにした。
荷物をコインロッカーに預けゲーセンへ行った。ラーメン食べた。めっちゃおいしかった。また行きたい。

集合時間にTLEしながらも(ごめん)荷物を取りに行くがシャッターが閉まってて取れなかった。悲しい。

ネカフェでシノハユを初めて読む。物語がちゃっちゃか進んで面白かった。
寝落ちする。

3日目

起きてシャワー浴びてマンガ読んで荷物回収して吉野家で飯食べて恵比寿に向かった。
駅から出た場所が悪くてTLEした。ごめんなさい。

indeed見学。環境がすごくよくて興味がわいた。
ICPCのお金で飯を食べる。


LINE見学。LINEキャラのオブジェがあちこち置いてあった。

解散。

 

お疲れさまでした。

ACPC2017 JAG夏合宿2017 参加記

初めに

twitterの自分のツイートを遡りながら書いてます。 

コンテストがたくさんあったのでコンテスト内容はあまり覚えてません。

 

出発直前にSteins;Gate0をgetしたのでこの合宿にわたりプレイする。

ACPC DAY0

助成金パワーにより新幹線で前日入り。シュタゲをする。

夜はtuki_remonとラーメン来夢。

東横インに泊まります。

この日は台風が来ててなかなか眠れない。シュタゲをする。

ACPC DAY1 

ホテルの朝ご飯を食べるがあまりおいしさを感じなかった。

ゲオでハンターハンターを立ち読みしていい時間になったあたりで会津大学に向かう。

会津に着き建物に入るとき、いつもの儀式を行った。

自己紹介フェイズ。kenkooooさんとウキニキア様の自己紹介が印象に残る。

立命セットなのでジャッジ側に入る。

コンテスト開始直後、うし(ei1333)さん即A提出、部屋が盛り上がる。惜しくもWAる。

Fに制約のミスがありごめんなさい。

Gが解かれず、つらみ。

懇親会はいかず、1回生二人とbigboyにいく。ホテルに戻りらずひるど(Luzhiled)君とうさぎとデレステをする。シュタゲをする。

ACPC DAY2

ホテルの朝ご飯は食べない。

会津セットコンテストはYang33(__KasSA)さんとたじま(tj_mi0)さんと組んだ。

老害なので前半の問題はお二人に投げた。

解説きくとDとMが賢かった。

この日の懇親会はRCOさんの力によりタダになる。

懇親会会場にいく途中、うしらずうさぎが並んでtwitterで話しててウケ。

デレステの宝くじでかわいい子をget。

写真撮影をする。準備の間yebi君が寝てて苦笑。

ホテルに帰りらずひるど君とうさぎとデレステ。コドフォがあったので早く終わる。シュタゲをする。

ACPC DAY3

ホテルの朝ご飯は食べない。

北大セットコンテスト。day1にらずひるど君を組む話をしていたので組む。うしさんもいた。

Bを担当してて、数学の授業を受けてた。

あとは二人が練ったDを実装した。それだけ。うしさんがプロ。

ACPC終わり、お疲れ様でした。

僕とT.M(IS0283IR)君はJAGに参加するのでこのまま新宿へ向かう。

郡山までの電車でらずうしと再会。

郡山で1時間暇あったのでアニメイトらしんばんにいく。

いいグッズ特になかった。

ゲーセンがあって、jubeatが置いてあったので少し感動。

新宿へ到着。

都会にビビる。

歌舞伎町にいい感じのネカフェがあったのでそこに泊まる(次の日もここで泊まる)。シュタゲをする。

ACPC day4 JAG day0

この日は新宿でぶらぶら。

jubeat の非公認大会、「jubeatech」の予選があり、日程が合宿とまるかぶりだったのでこの日しかゲーセンに行くことができず、ゲーセンに行く。

ACPCの疲れと寝不足で厳しかった。

疲れたらゲーセン出て周りぶらぶらしてまたゲーセンに行く、を繰り返した。

歌舞伎町は風俗街らしく、キャッチが怖かった。一回にいちゃんに話しかけられた。「君何歳?成人してる?」

夜はラーメン二郎にいく。

結論から言うとにぼ次朗のほうが圧倒的においしい。

いい時間になったので僕のjubeatech予選はおしまい。

ネカフェにいきシュタゲをする。寝落ち。

JAG day1

会場にはやめについた。

ヘクトさんチームと組む。プロだった。これがプロかと肌で実感。

シュタゲをする。

JAG day2

チームメイトのT.M君とraven_38_さんと組む。

問題文が英語なのに苦戦しながら4完。

Hはborderingを端と思い誤読。英語の授業を受けた。

IはPythonで通した。

シュタゲをする。

この日はcodefestival2017予選Aがあるので談話室にいく。人がいた。

A: substrの内部の処理に自信が持てずsizeで場合分け

B: これ200か?とビビるがAC

C: AC

D: 紙に書いてあれこれ考えるといい感じの埋め方を思いつく。が、実装に結構手間がかかり開始一時間弱でようやくAC

予選Aで通れたので満足。

ついでにjubeatechの予選最終日でもあり、結果が1時ぐらいに発表、ぎりぎり予選通る。シュタゲをする。

JAG day3

りあんさんチームを組む。ほんまにプロだった。肌で実感。

これで一週間にわたる合宿が終了、一息つく。

新幹線の時間まで空きがあるので秋葉原に寄る。

みくにゃん可愛い。

お疲れさまでした。

ACM-ICPC 2017 国内予選 参加記

ACM-ICPC 2017 国内予選に参加しました。

RiPProとしては「4,3回生チーム」「2回生チーム」「1回生チーム」の3チーム参加してました。

メンバーは「ixmel, T.M, noy72」。

昨年、一昨年はSIMritとしてでていたが、チームの一人が競プロ離れしたため一人swapしSIMnitと変名して参加。チーム名後ろ3文字はメンバーのIDの頭文字。

 

結果: 4完 29位 学内1位なので通るかと (追記:通りました!!)

 

作戦を立てる時間は楽しいので作戦は今までで一番細かく立てた。以下

  • ixmelが実装担当、T.Mは考察担当、noy君はテンプレ写経と構文解析と考察担当
  • T.Mとnoy君が考察しixmelに伝えixmelが実装、の流れ
  • 提出の際全員でチェック(提出ミスはしたくない
  • バグるorWAったときは誤読、認識の差異、実装ミスなどの可能性が高いため2人に実装方法を伝える(よくここでバグった理由が判明する
  • コンテスト開始直後noy君がテンプレ写経、その間2人でABの実装方法を考える
  • ixmelがABを実装、T.Mとnoy君がCの考察
  • ixmelがCを実装、T.Mとnoy君がDの考察
  • ...
  • noy君の手が空いたらFとかGとか読む(幾何問題あればワンチャンなので

 

コンテスト開始前

テンションが上がってくる

F5アタックしながら待機

 

コンテスト開始

ページ読み込み?が始まってオッとなるが読み込みが長い。

気を抜いてマウスから手を放した直後表示されてアッ。

印刷クエリ投げてる間にT.MがAを解き終えてた(はや。

noy君がテンプレ写経してる間にBをめんどいやつだなーと思いながら実装方法を相談する。

写経し終わったっぽいのでAとBを通す。(A.9:50 B.25:45)

 

Cの解法を教えてもらい通す。(C.36:45)

NAISTのyazatenプロ,yurahunaプロチームには勝ちたい気持ちがあって、この時点で勝っていたので喜ぶ。

 

Dの解法が2人から降ってこなかったのでDの考察に加わる。

D、フローはダメ、制約より同じのを消してったら√n種類に収まるかなー(嘘かつ嘘解法)などいろいろ考える(T.M迷走

nが小さいと全探だよなーmが小さいとbitでいけるなーとT.Mが思いつたっぽいので実装しD AC(D.77:45)

ここまで0WAなので予選突破ほぼ確チャンとなりT.Mが滑る椅子を使い躍る

 

Gをフローで解けるのでは(ソースから左上と右下へ容量2、左下と右上からシンクへ容量2の辺を張る)と考えるが実装し終わってサンプルが合わず噓解法と判明。捨てる。

 

Eに手を付ける。

Eは入力が16文字までなので答えとなる長さ最短な式には変数が4つまでしかないことから全探する解法でいく。

前日あたりに「2分探索」という言葉が脳にinputされていたため、多少遅くてもいいやというノリがあって前計算でいけることに気づかない。

列挙する部分はできたので、構文解析担当のnoy君にバトンタッチ。この時点で順位表見ると1回生チームが2回生チームにペナルティ100差で勝っていてあまりにも僅差で感動。

残り約10分に実装が終わりサンプルを通すが一つだけ合わず。否定がかかる順序やらが怪しいが時間切れ。

 

コンテスト終了

菓子パ。

 

https://twitter.com/wk1080id/status/885827579751444481

感想

模擬含め5完したことがないのでしたかった。来年こそは。