ICPC 2020 国内予選参加記
なかなか書く気になれず本当に遅くなりましたが、軽く参加記を書きます。
結果から言うと5完22位。予選敗退です。
敗因は単純に学内の強い人々に敵わなかったことでしょうか。無条件で通過できる10位以内に入るしか勝ち目はありませんでした。 自分から上の順位で予選落ちしているのがUTとKUしかいないのを見ると思うところはありますが、敗退は敗退です。
Fがあと少しで間に合わず6完を逃したことや、Cで助けを求められたとき即座に正しい解法に気づけなかったこと、解法がある程度わかっていたDの実装方針を詰めるのが遅れたこと、もっと精進をしなかったことなど、後悔している点は挙げればキリがないです。
学年的にもう次はないので、これでICPCは引退となります。去年の国内予選およびDanang regionalと合わせて3回のみ出場しましたが、とても楽しかったです。本当によい経験になりました。
最後になりますが、コロナが収まったら、学友が強すぎて国内予選を通過できる見込みのないチームは是非海外regionalに出てみてください。国内予選とは大きく異なるチーム戦が楽しめると思います。
ICPC 2020 模擬国内予選参加記
ICPCの国内予選直前に毎年開催されている模擬国内予選に参加しました。
結果はFまで6完で、本番参加者のうち11位。見事予選突破です。
コンテストを通して致命的なミスが複数起きてかなりひやひやしたが、結果的に勝ててよかった。やっぱ完答数だよなぁ
コンテスト中の流れ
自分がAをとおす、そのままテンプレの写経をする。
番兵がB、ゆきのんがCを書き始める。
Dを読んだけどわからない。
番兵がBを落として困っていそうなので様子をみにいく。 しばらくコードを読むが、どうも正しそう。 もしかしてファイルを間違えていたのではないか？と聞くとそんなことはないらしい。 が、どう見ても正しいコードなのでゴリ押しでもう一度提出してもらう。 一応自分も見ていると、番兵が違うディレクトリを見ていたことに気づく（は？？？）
模擬でよかったといいながら番兵にDを読んでもらって、自分はEを読む。
すぐに2-SAT+にぶたんとわかったので、書く。バグる（？）
デバッグしているうちにC, Dが通る。かなり焦る。
ゆきのんがFを読んで嫌そうにしつつも書き始める。
なんどか見直したけどもう一度...と思い、写経を見直すと間違いを発見する（？？？？？）
写経ルール、やめへん？
直すとサンプルがあって、意気揚々とテストケースを実行するが、待てど暮らせど終わらない。
しゃくとりするか...といって書きなおす。すぐに実行出来るようになって、出すと落ちる（？）
ちょっと直すと通った。
Fの成功を祈りつつ番兵とHを考える。番兵のおかげで考察は進んでいたが、さっぱりわからない。
そうこうしているうちにゆきのんが「F書けちゃった笑」と言い、提出をみんなで見守る。
通る 6完
感想
gazeruとHeno Worldに9割勝てないので、他の強い数チームに本番も勝つか10位以内に入るしかない。がんばります。
HUPC2020 コンテスト感想
・day1
ABをスッと通す。
ゆきのんがCを考えているあいだにEを読んでたら最小点被覆になったので実装する。通る。
Dを考えてると三角形を取り出すと候補が確定しそう。ゆきのんがCを通したので書いて出す。通らない。終了......（このまま2時間溶かした）
・day2
まずゆきのんがA、自分がB、番兵くんがCを読む。
ゆきのんが書き始める。通る。なぜかBをやっていたらしく自分が無職になる。
どうしようかなーと思いつつMを読むと、コマごとにGrundy数を求めたら良さそう。
気づいたらゆきのんがGを通している。
ゆきのんからDの方針を聞いて、頂点が動いた結果を反映していなさそうだったので指摘。 ゆきのんが書いて通る。
番兵くんがJを書いた。通る。
Iをゆきのんが思いついて通る。
Mでへんな方針を生やして詰まっていたらゆきのんが拾ってくれて通る。
ゆきのんは天才
Kを読むと大変だけど書くだけっぽかったので二人に他の問題を考えてもらいつつ書いていく。最後まで16ケース目あたりで落ち続けて終了。
終わってから苦しんでいるとなぜか初期値が間違っている。私が戦犯です........
・day3
ACをすっと通す。
Bが簡単なはずなのに難しそう。あとまわし。
Mを読んでるとWUPCで見たやつっぽい。書き始める。
途中で番兵くんがI、ゆきのんがFを生やしてくれたので、交代する。無事とおったので自分も書き終えてMを通す。
Gを読むとコストの計算を頑張れば解けそう 書き始める。
このあとなぜか空白の期間があるが、数時間たって番兵くんがBを解いたらしいので交代して書いてもらう。苦しみながらもなんとか通る。
最終的にGのコスト計算が間違っていて通らなかった。悲しい
コンテストが終わってからGLJを通した。Lの証明たのしいね
運営の方々、本当におつかれさまでした！
楽しいコンテストを提供してくださってありがとうございます。
HUPC2020 札幌オンサイト 参加記
・8/19
オンサイトが中止になりました。
[重要]
— HCPC 北海道大学競技プログラミングサークル (@hcpc_hokudai) 2020年8月19日
「北海道大学競技プログラミング合宿 HUPC」についてですが，新型コロナウイルスの感染拡大状況を踏まえ，非常に残念ではございますが，オフラインでの開催を中止にすることに決定いたしました．
関係者の皆様には多大なる迷惑をおかけしますことをお詫び申し上げます．
完
・9月頃
せっかくだしチームで北海道へ旅行に行こうということで宿や飛行機を取った
もともとオンサイトのために1泊2000~3000円とかの宿を取っていたけど、gotoキャンペーンのおかげでめちゃくちゃ安くなってたのでもうちょっといいホテルを取ることにした
飛行機+5泊6日の宿で3万円くらい goto様々
・9/13
前日はISUCON10があって、疲れたーといいながら出発
昼を食べて、暇だったので3時間くらいWUPC2020を解いた（え？）
9完できてうれしい
夜はラーメンを食べた
数日後燃えてしまった どうして..... news.yahoo.co.jp
・9/14
二条市場に行った。
お昼ごはんに海鮮丼を食べた。
大通公園を歩いていたらソフトクリームがあったので食べる さむい
day1に出た（感想は一番下）
夜はジンギスカンを食べに行った。肉と酒、最高！
こいつら飯以外の北海道要素楽しむ気がないな。
・9/15
昼ごはん
day2にでた（感想は一番下）
晩ごはん
・9/16
疲れて昼まで寝てたのでお昼ごはんはおにぎりにした
day3にでた（感想は一番下）
晩ごはん
・9/17
ここに来て初めて観光 小樽へ行く
街並みがとても綺麗
札幌はとても整理されている感じだったけど、こっちは歩いていて楽しい感じ
お昼は海鮮丼
別行動で少しうろつく
やはりポツポツと閉まっている店があってつらい
ルタオ本店でケーキを食べた
ドゥーブルフロマージュを買おうと思ったけど送料が高くて断念 空港で売ってたら買うかも
【追記: 買いました】
また少し別行動
オルゴール堂に入ったら100年くらい前の貴重なオルゴールや自動演奏器を試演してた すごかった（こなみ）
オルゴールはいいですねとなって歴史を見ていると、100年ほど前に蓄音機の普及によって全盛期が終わりました、と書かれていてすこし悲しかった
札幌に帰って晩ごはん
最終日の宿でこれを書いています
やっぱりオンサイトはたのしいね！
↓コンテストの感想
RCOでインターンしてきました
めちゃくちゃ楽しかったですと言いたいだけの記事です。
メンターの二人に死ぬほど質問を投げつけて一緒に議論出来たのはとてもよい経験でした。
COVID-19のためリモートをしている人が多い時期だったのですが、1~2年目の比較的年の近い方達がよくご飯に連れて行ってくれてとてもやりやすかったです。
RCOはいいぞ。
今年の夏もやっているので、興味があれば是非に。名称はアルバイトになってますがやることはインターンといっしょです。 engineers.recruit-jinji.jp
ICPC 2019 Asia Danang Regional 参加記
12/6にダナンで開催されたICPCアジア地区大会に参加してきました。
12/2
フライトが次の日の朝早くだったため、関西国際空港に宿泊。 6000円でカプセルホテルの天井が高くなったやつに泊まることができた。
12/3
日本脱出。
チェックインや出国審査に思ったより時間がかかり、早めに出ておいてよかったなあとなった。
だいたい14時間かけて空港についたが、予約していたホテルの送迎が来ない。
仕方なくその辺のタクシーに声をかけたら案の定ボられてしまった。（それでも元々の物価が死ぬほど安いため、10km2000円とか。）
なんとかホテルに辿り着く。ホテルの部屋が1泊4500円(1人1500円)なのに死ぬほど広くてビビる。
12/4
余裕をもって一日早く着いていたので観光をする。 ハン市場とダナン大聖堂に行った。買い物難しい。
夜にSleepingDragonとHeno Worldに合流して、運営に着けてもらった現地ガイドの人とご飯を食べに行く。 1食100~300円で金銭感覚がバグる。
12/5
practiceの日。バスでダナン工科大学に向かう。 到着するとまずopening celemonyがあった。壮大なBGMが流れていてちょっと面白かった。 コンテストについての説明などを聞いて、practiceに向かう。
直前になって、現地ガイドの人が「昼ごはんにパンか何か買うかい？」的なことを聞いてくれたらしく、 れなすとゆきのんがガイドの人と一緒にパンを買いに行った。数分で戻ってくると思っていたが間に合わず、結局自分一人で会場へ入ることに（あとから来た）
自分の席につくと、謎の使用済み計算用紙（？）と、ベトナム語で何か書かれている紙（？？？）が置いてある。 紙にIDとパスワードとリンクが書いてあるので、ここにアクセスしてIDとパスワードを使ってログインすればいいのかなと考える。が、リンクが開かない。 運営サイドの人に聞くと、まだpracticeは始まっていないらしい。なるほど、となってテンプレやエディタ設定の写経を練習する。
そのまましばらく経って、周りがkattisにログインし始め、運営が開始のアナウンスをしてるのが聞こえたのでさっきのリンクにアクセスする。が、リンクが開かない。 周りを眺めると見たことある問題（ドーナツのやつ）を解いていたので、まだ始まってないから過去問でも解いてるのかなあなどと考え、自分たちも適当に問題を解く。（実はこの時もう始まっていたらしい）
そのまましばらく経過し、不安になったので運営に「この紙に書いてあるリンクにつながらないんだけど？」と聞くと 「その紙は違います。」などと言って紙をﾋﾞﾘﾋﾞﾘに破きはじめ、おっﾜｸﾜｸか？と考えていたらpracticeが終了した（は？）
あとで京大勢に聞いたらkattis使ったことあるなら大丈夫やでと言われたので一安心する。 夜は中華っぽいレストランでご飯を食べた。量が異常に多かった。
次の日は早いがこどふぉがあったのでもちろん出る。 23時半頃に就寝。
12/6
本番の日。5時半起床。
眠い目をこすりながらバスで大学に向かう。
会場に入って自分の席に着くとちゃんとkattisのログインページが表示されていて一安心する。
コンテスト中の流れはネタばれを含むので下に書く。
コンテスト後はパゴダにいった。 大きな大仏などがあってわりと楽しかった。
19時ごろからYES/NOがあった。Heno Worldが10完単独優勝を決めていてアツかった。 宿に帰ってから4人あつまって麻雀をした。
12/7
ホイアンとコン市場を観光。お土産をかった。 飛行機に乗って帰った。
感想
そもそも今年の国内予選が初めてのICPCで、チームを組んだのが国内の直前だったため3完で横浜には遠く及ばなかったが、 自分が今年4回生で残り回数も少ないこと、旅費が思ったより安いことを理由に自腹でアジア地区大会に参加することにした。 黄青水（登録時点では青青水）のチームだったため実力不足を懸念していたが、終わった今となっては参加してよかったと思っている。 結果はチームの実力にしてはよくできた方だと思う。少なくとも国内予選の時よりは確実に成長しているのを感じた。
反省
自分の実装が遅い、チーム全体として速度が足りていない。
たいしたことないコーナーケースにひっかかったりしょーもないバグを埋め込んだりしてWAを生やしたのはとても反省している。精進を続けるしかない。
来年は日本のアジア地区予選に行きたいね。
～～～ネタバレ注意～～～
0:00～ 自分がテンプレとエディタの設定を写経してる間に、ゆきのんにA~F、れなすにG～Mを読んでもらう。
~0:13 写経し終わったので、れなすがめちゃくちゃ簡単だと言っていたMの概要を聞く。 考察が簡単すぎてさすがに自分で読みなおし、納得して書く。WAが出る（は？） すぐにn<=2のケースを忘れていたことに気づき、AC
~0:82 Gの見た目が簡単そうなので、れなすと考えてみる。 れなすが(1000...にするのにかかる回数) +（各桁の和 - 1） + 桁数みたいな式を生やした。正しそうなので実装して投げる。WA。 すぐにコーナーケースがたくさんあることに気づき、後回しにする。 ゆきのんがD解けそうと言っているので、そのまま任せる。 自分はKを考えていたが、さっぱりわからず順位表を見るとDとIが解かれていそうだったのでIを考える。 しばらくしてゆきのんがDをAC
~2:19 Iが解けたので書いてみる。が、WA。（スイッチとライトの対応を間違えていた） 一度置いておいてGに戻る。れなすがいくつかコーナーケースを発見したので実装して投げる、がWA。 この辺から絶望していて、順位表で皆が通していそうなIを先にやることにする。 すぐにミスに気づき、実装してAC
~2:31 れなすがGのコーナーケースをもう一つ見つける(最下位以外に1があるケース)。実装して投げてみるとAC
~3:55 Hを眺めながられなすと話していると、行の制約を満たす塗り方を全列挙して全部の組合せを確かめるのが間に合いそうだという話になる。 自分が実装することにして、その間れなすとゆきのんにAを考えてもらう。 とりあえず全列挙パートを書き終わったあたりでれなすとゆきのんがAの解法を生やしたらしいので、先に書いてもらう。AC。
~4:36 Hの実装が終わったので投げる。RE。(実装方針を一部変更する前のassertを取り忘れていた.....) ゆきのんがLがもしかしたら貪欲で通るかも？と言っていたので、かなり怪しさを感じたが解けそうな問題がないので実装してもらう。 自分はゆきのんがかいてる横でマウスを使ってHのデバッグをしていた。（これが功を奏した。） REやしセグフォやろ～と思っていたら大昔にassertを入れていたことを思い出し、ゆきのんの手が止まったタイミングで取り除いて投げてみる。AC
~5:00 Lを実装するゆきのんを応援する。が貪欲ではダメなので通らない。コンテスト終了。
フィックスターズのインターンシップに参加してきました
9/9~9/27の期間で株式会社フィックスターズのインターンに参加してきました！
インターンでやった内容はほぼ公開してもよいとのことだったので、そのあたりについても書いています。
（念のため文章はNDAに引っかかっていないかどうかメンターさんにチェックして頂いています。）
間違った記載がありましたらコメントなどでご報告ください。
申し込むまで
インターンに申し込んだのはたしか6月だったと思います。
今年は4回生だし、セキュキャンに行けることも決まっていたのであまり積極的にインターンなどをする予定はなかった（一応Googleは申し込んでみたけど、phone interviewがなぜか英語になって爆発した）
のですが、院試勉強の合間にぼーっとtwitterを眺めていたらフィックスターズのインターンの宣伝が流れてきて、おもしろそうだと思って応募しました。
僕が申し込んだのは「深層学習コンパイラの開発」というテーマです。 この技術に対して深い知見があったわけではありませんが、どんなことをやっているか知ってみたかったというのがこのテーマにした理由でした。
面接では人事の方や実際に入ることになるチームの人たちとskypeで話しました。 コーディング面接があって、Googleのphone interviewの顔が見える版みたいなことをしました。 倍率などの詳しいことはわかりませんが、面接を受けた感じでは特に選考が厳しそうな印象はありませんでした。
何日か後に無事に合格の連絡がきて、参加する運びとなりました。
移動日～初日
もともとは9/8に移動して前泊することを想定していたのですが、運悪く台風と被ってしまいました。 前日の時点でのぞみは19時ごろに終電を繰り上げるという情報が入っていたのですが、 「まあゆっても大丈夫やろ！ｗ」くらいのノリで17時ごろに京都駅に行った結果なんと東京行き新幹線の終電がもっと繰り上げられていて、 重い荷物をもってとんぼ返りするハメになりました。（後で見ると当日の昼頃にはそのことが発表されていた)
翌日は来れる人は11時集合とのことだったので、始発の新幹線で東京に向かって、マンスリーマンションに荷物を置いて、急いで会社に向かう、、、と頑張ってみたのですが、まあ30分くらい遅れました。（他のインターン生たちも間に合ってない人のほうが多かった） 自分は宿が品川だったので新幹線を降りた後はずっと徒歩移動できたのですが、もう少し遠くに住んでいる人は交通網がマヒしていてまともに移動できなかったんじゃないかと思います。
その日は結局午後の時間をつかって書類を書いたり説明したりが行われました。
インターン中にやったこと
自分がやったのは、"Tiramisu"という並列計算を記述するためのDSLの処理系がどんな風に実装されているか、またTiramisuをつかってどんなことができるか調査しましょう、といったタスクです。 めちゃくちゃざっくりいうとTiramisuはHalideにバッファの再利用機能が追加されたようなDSLです。（ざっくり言い過ぎなので突っ込みどころはたくさんあると思います。） バッファの再利用が可能になるとデータ依存が起こるのでそれを検出・解決するためにpolyhedral modelというのを使っていると論文には書いてありました。 インターンの開始時点でHalideに対する知識もintroductionをやった程度しかなかったのでキャッチアップにかなり多くの時間を費やしました。
Tiramisuのgithubページ github.com
とりあえず初日はtutorialをやってTiramisuでどんなことが出来るのかを確認してみました。 また、簡単な例として2次元のconvolution演算を実装してみました(C++でも実装して、出力が一致することを確認した) ここまでで2日ほど費やしました。
正直ドキュメントがあまり充実していないプロジェクトのソースコードを読んで理解するという経験はしたことがなかったので社員さんにどんな感じで進めて行くのがよいか質問してみたところ、 戦略としてはひとまずデバッガをつかって1ステップずつ進めながらどういう感じで動いているか観察してみるのがよいとの回答をいただいて、なるほどと思いながら解析を進めました。
数日(！？)くらいそんなことをしていると浅いところで何をしているかがなんとなく見えてきて、実装に関する知見をまとめたりpolyhedral modelについて勉強したりして過ごしていました。
他にはTiramisuを使ってどんなことが記述できるかを試したかったので、行列計算のうち繰り返しを使って何かするアルゴリズムとしてべき乗法を実装してみました。 べき乗法は絶対値最大の固有値を求めるアルゴリズムで、やることの9割がランダムな初期値をもつベクトルに行列Aをひたすらかけ続けるだけというシンプルなものだったためこれを採用しました。
C++で愚直に実装したものとTiramisuで愚直に実装したものとTiramisuでいい感じにSIMDをつかって高速化したものを比べてみたいなーと思っていたのですが、残念ながら時間がたりずそこまではできませんでした。
ただ、実装が間に合ったものとして「二本のバッファを使って繰り返しの操作を回す」という処理が挙げられます。 （社員さんの話を聞いた限りでの僕の理解としては）Halideでは計算の途中に用いるバッファを明示的に指定できないため上のような処理はできず、ひとつ前の結果に依存するような繰り返しの回数に比例してメモリを消費してしまう可能性があるのですが、Tiramisuでは特に困ることもなく上のような処理を記述できました。これはHalideに対してTiramisuが優れている点だと思います。
一方で、Tiramisuがやっていると主張している「データ依存関係の検出」という処理がうまくされていなくないか？という疑問が生じました。
Tiramisuは
・アルゴリズム
・スケジューリング
・バッファ割当
の3つを記述するのですが、バッファ割当に対して間違ったスケジューリングをしていても特にそれが検出、修正されている様子はありませんでした。
正直このあたりはTiramisuに一番やってほしかったところであるため、見つけた時は少し残念でした...
感想
会社自体はとても働きやすそうなところでした。 10円でコーヒーなどの飲み物を買うことができたり、広めの雑談スペースがあったり、本がたくさん置いていたり、お昼寝スペースがあったり、、、 また、社内で勉強会が行われていたりもしていました。
みなさんも興味があれば通年でインターンシップを募集しているので申し込んでみるとよいと思います。 夏休みの期間は他期間と区切ってインターン生の受け入れを行っているようです。 お給料(時給2000円)、交通費、宿泊費（前泊・後泊込み）が出るのがかなりありがたかったです。
AtCoder水色以上の方はJobsから申し込みましょう。（夏休み期間は公式ページから申し込んだほうがいいんか？と思って公式ページから申し込んだけどそんなことはなかったっぽい）
AtCoderJobsからのインターンシップ申し込みフォーム
AtCoderJobs - 求人詳細 - 【通年】あらゆる手法を駆使し、実社会で動いているソフトウェアを高速化するインターン募集！
公式ページのインターンシップ申し込みフォーム
インターンシップ | フィックスターズ 採用情報
