ICFPC 2020参加記
感想
初めてICFPC(https://icfpcontest2020.github.io)に参加しました。
折り紙の回とかは問題だけ見て無理だと逃げてました。
会社の(私よりレートの高い)方達と出てまして、初チーム戦*1だったので、刺激的でかなり楽しかったです。
例年は集まって参加していたらしいのですが、今年はオンラインだったので少し残念でした。
簡単に今回のコンテスト概要を説明すると、前半パートは謎解き+関数型謎言語のインタプリタ実装で、
後半パートは前半の謎が解けているほど有利なゲームAIコンテストでした。
以下、日ごとにしたこと。
記憶が曖昧なので時系列は適当です。出場した人しか意味がわからない内容になっていそうですが(過酷さ)と面白さが伝われば幸いです。
1日目
未解明の言語仕様が公開される。最初は全チームで言語仕様の解明。
SKIコンビネータとか知らなくて恥ずかしい気持ちになった(今もよくわかっておらず)。
そのうち問題が公開されて、それまでは関数型言語の勉強してほしいのかなという話をしていた。
2時頃に謎言語で書かれたプログラム(Galaxy Pad)が公開されたが、私に出来そうなことはなさそうだったので寝る。
2日目
朝起きたら、謎言語インタプリタが完成していて驚く。
このあたり何をすれば良いかよく分かっておらず置物になっていた。
Galaxy Padを使ってサーバーと通信する方法に誰かが気づく。
謎解きが進み、ついに対戦やチュートリアルが選択できるメイン画面までたどり着く。
とはいえ、まだあんまりピンと来ておらず。
結構遅くまで色々見ていたが特に成果は得られず、スタートラインが遠過ぎる…
3,4日目
ビジュアライザが完成(すごい)
ライトニングコンテスト(チュートリアルを解いた問題数で競う前半パート)の締切が終わった後だが、チュートリアルがチュートリアルであることに気づく*2。
私はとりあえずチュートリアルを進める。ゲーム仕様の学びがあった。
同時に対戦方法の解析も進む。
このあたりからはルールが不明確なAIコンテストみたいな感じに。
ゲームの内容は、宇宙船での1対1の対決でした。攻防に分かれ、それぞれビームやら自爆やら分裂を駆使して、攻撃側は相手を倒せば勝ち、防御側は生き残れば勝ち。
チームの方が早い段階で敵機の前の位置や速度から次の位置を推測してビームを撃つAIができていて動きが的確で凄かった。
防御側は分裂して軌道に乗せるのが強そう*3だったので、それを書いてみることに。
ギリギリ分裂して軌道に乗せるところまでなんとなく書けたが、何体かが軌道に乗せているはずなのに死んでいた...。直しきれずに終了。
他の方が分裂防御を綺麗に書けてそうだったので、そちらを位置を推測してビーム撃つAIとマージして提出。
雑記
- Discordでコミュニケーションを取っていたが、公式の連絡も基本Discordで一貫性があり便利だった
- 公式Discordのチャットに高速で英語で情報が流れていて追いきれなかった
- 謎解きパートが多かったので完全に座るだけは免れて良かった
- 人海戦術が効きそうだった
- インフラ周りの整備の速さが凄かった
- 負担がかなり集中してそうで申し訳なかった(手伝いたいが、手伝っても負担を増やすだけなのでごめんなさい...)
- それぞれでチュートリアルや対戦を回して情報収集していたが、2人組みで対戦するのが序盤は効率良かったんじゃないかなぁという反省
- 寝食のタイミングを失って消耗した(起きていてもどうしようもない時は素直に休めば良かった)
- 小さな自動化ツールや気付きがチームの役に立って嬉しみ
- チーム内の自動対戦環境くらいは私でも頑張れば作れそうだったのでやれば良かった
- 色々な人の気づきで一歩ずつ前に進んでチーム感があって結構楽しかった
- 時間が足らず消化不良感。終わってからぼろぼろ知らない要素をtwitterで見かけて悲しい
- 運営が凄い力入ってるなぁという感じだった
- (前後半パートのどっちかだけで良かった気はする)
- チームの方々のお陰で楽しむことができた。ありがとうございました。
- (一人じゃインタプリタ実装の時点で諦めてそう)
競技プログラミングをだらだら5年くらいやってみて
特に対象読者も決めていないクソポエムです。
思いついたことから書いてるので、まとまっていません。
競技プログラミング自体の説明はこの辺を読んでください。
競技プログラミング - Wikipedia
竸プロは青春
私も途中全くやってない期間とかはあるものの大学時代のかなりの時間を竸プロに捧げたと思います。さすがにゲームとかニコ動の時間の方が長いですけどね。
卒業という良い節目なので、竸プロを通して振り返り、何を学んだかなどをだらだら書こうと思います。
竸プロとの出会い
私が竸プロを始めたのは学部1年の後期くらいからです。
その頃は今ほど竸プロは知られてなく日本のコンテストサイトとして有名なAtCoderがちょうど出来た頃だと思います。
当時の私は、プログラミングに関して授業レベルでは困ることはなかったのですが、外に出たら通用しないのだろうなと漠然とした不安を抱えていました。
そこで、目標にするためと自分のレベル感を測るために、プログラミング系のコンテストを漁っていたときに見つけたのが、竸プロでした。U-20プロコンとかも出てみたかったのですが、アプリを作り切るのは私には無理でした。
(余談ですが、プログラミングでやりたいことがないなら、とりあえず自分の興味に応じてコンテストに出るのが良いと思います。竸プロに限らず、セキュリティ、データ分析、障害対応とか色々な分野のものがあるのでね。http://cocodrips.hateblo.jp/entry/2015/10/11/114212)
初出場コンテストはtopcoderなのですが、レートは942でした。
全体のレート平均のちょい上くらいなので、初めてでこれは結構自分賢いんちゃうと思ったのと同時に、僕はこの程度じゃないだろ(?)と続けるしかなくなりました。
“ある種の”頭の良さを評価されるので、闇が深い。
普通に数学パズルとしても好きだったので、長く続けることになりましたね。
ここまで長続きした趣味は、中学時代にハマってたゲーム以来なのですが、要因として初期段階で周りにやってる人がいなかったのも大きかったと思います。
プライドだけ無駄に高い人間なので、大学とかで同時期に始めた人がいて、負けてたら続けてないですね。おそらく。ライバルがいてめっちゃ成長したって人もいるし、なんとも言えないけど。
自分とのマッチングや周りの環境など色々あるので、この時期に自分に合ったものと出会えたのはなかなか幸運だったなと思います。
それからしばらく
滑り出しはまずまずだったものの、それから1年くらいはレートが全く上がりませんでした。あまりに悔しくてコンテスト終了後に泣いた覚えがあったりなかったり。
この1年くらいが一番情熱があった時期で、再帰を理解できるまで散歩とか、深夜でもコンテストに出るとか、授業中も問題を解くとかやってました。なんだかんだ”やってる感”があって楽しかった。
やってる感に浸って、コンテスト中に解けなかった問題を解き切らずに放置していたのが、伸びなかった原因だと思っています。復習が嫌いなので…
体系的に勉強する必要はないけど、復習はしっかりすべきでしたね。
現状のレベルでは、解かなくて良い難しい問題も存在して、その辺の見極めが難しいですね。
最近は、公開されている解説を読んで意味不明な問題は飛ばす方針でやっています。(この辺は数学系の本も同じだと思っていて、難しすぎる本は飛ばします。)
数年振りに解いてみると解ける問題もあったりしたので、諦めは結構肝心だと感じます。
遮二無二解くことより、適切な難易度の問題を解くのが重要だと思うのですが、適切な難易度の問題を探すには、結局沢山解かないといけない…
思考法
一応、だらだら続けている内にtopcoder, Codeforces, AtCoderでは青コーダー(中堅くらいの実力?)になれました。
これまでに解いた問題数は、900問くらいみたいです。
続ける中でアルゴリズムやデータ構造の知識が増えたのはもちろんなのですが、雑に言うと昔より頭が良くなったと感じます。
頭の良さにもいくつかあると思うのですが、特に問題を整理する力、考察力が向上したと思っています。
私は、下の2つプロセスを意識して問題を解いています。
① 問題の性質を書き出す
② 性質の考察を進める、複数の性質を組み合わせて解けないか考える
①については、例えば、「判定問題として考えると…」、「この部分は貪欲に解けるから…」、「小問題が解けていると仮定すると…」とかです。
こういう具体的なアルゴリズムにまでは至らない考察や、”部分的に問題を解いていく”のが、少し得意になったと思います。前は一気に解ければ解ける、そうでなければ解けないみたいな感じだったので。
②は、問題が複雑になってくると必要だと感じています。難易度としては、AtCoderで500点くらい、これ以上難しいと私も解けないんですけどね。
部分的に問題を解いた後に、全体が解けるように穴を埋めていきます。穴を埋めるには、部分的な考察を広げていく中で、不足している考察をひらめくしかないと思っています。
天啓が来ないで行き詰まると「ここまでは解けてるから考えなくて良い。」みたいな独り言をよく吐きます。考える必要のある部分に集中してるんですかね。
この辺の反復練習から、どこまで理解できていて何を考えないといけないのか整理する能力が上がったと思います。
僕はこれが非常に苦手で既知の部分を何度も考えて空転することがいまだに多いです。
まず、これが苦手だとに自覚したのは最近で、こういうのは得意だと思っていたので、自覚できただけ良いと思っています。
競プロに限らず、大きな問題に直面した時に、小問題に分割できず、フリーズしてしまう癖があるので矯正していきたいですね。
竸プロerは自己評価が低い
に関して二言三言。
知性で殴り合ってる感が強く、レートという形で定量的に能力が測れてしまう竸プロなので、卑屈になってしまうのかなぁと思っています。レート以前に解けなかった問題が異常な速さで大勢に解かれていると悲しいし、悔しいですよね。
定量化しないでいた自分の弱さとか無能さと向き合うことになるので、私のような自分のことをそこそこ賢いと思っている人間には、ちょっとつらい。
こんなのやってるの頭が良い人しかいないんだから、ヘコむ必要は全くないのですが、足ることを知るというのは難しいですね。
悔しさ駆動精進も捗るので、卑下の全部が全部悪いとは思いませんが、ほどほどにね。これは自戒も込めて。
学生を終えて
学生時代を振り返ると競プロがなければ本当に何もせず終えていそうだったなぁと思います。
会社見学やインターン、オンサイトのコンテストなど競プロ経由で様々経験させて頂きました。
学内でLTやったり、ハッカソンやったりしたけど、それも結局、”私は”競プロを通してそういうものがあると知ったのでね。
果ては就活も競プロのおかげと言って過言ではない。
振り返ると、競プロにもっとドハマりした方が良かったかなという想いと、色々と技術的な事やそれ以外も広く浅くやったこのままでもまぁ悪くなかったという想いが半々です。
けど、青コーダー止まりであれば、もう一つ何かしらで青コーダー相当の武器を作った方が気持ち的にも有利に進められそうだったなぁというのが就活等々を終えての所感です。(技術力に限らずコミュ力でもアピール力でも本当に何でも良いのですが)
これから社会人になりますが、学んだことを活かしつつ、けどこだわり過ぎず、バランス感覚を持って視野を広く、色々やっていきたいと思います。
まだ、何か吐き出しきれてないものが見つかれば追記します。
以上、読んでいただきありがとうございました。
P.S.
競プロに情熱ある風でここまで書いてきましたが、最近は熱も冷めてきて何か他のおもちゃを探しているところです。
2018年振り返りと2019年の目標
はじめに
振り返りの時期が来たので振り返ろうと思います.
年々年間記事数が減っていて,そのうち振り返りと目標しか中身がなくなりそう.
2018年振り返り
1~3月
就活に苦しんでいた.自分が何もかも中途半端なのを呪った.
あとは,昨年に引き続き学内でライトニングトークとか開いたりしてた.
コンテンツはしっかりしていたと思うがあんまり人は来なかった.
まぁ地道に盛り上げていきたいですね.
4~6月
この辺で就職先を決めた.
周りが終わりかけてきて焦って就活を辞めたのだが,
今落ち着いて考えても雰囲気は好きだし,まぁ間違ってた選択ではないと思う(働いてみないとわからないが).
単純に能力不足感が否めないので,死なないように勉強していきたい.
7~8月
MUJINのコンテストに出たら会社見学させて貰えた.
ご飯が美味しかった(小並感).英語できるようになりたい.
夏コミ3日目にサークル参加した.
2回目の参加だったので,落ち着いて参加できた.
冬コミも参加登録したが,地獄を見ることになることをこのときはまだ知らない.
9月
某大の松尾研の強化学習講座に出ていた.
講座とかに出てもちゃんと復習しないと何も身につかねぇなと言う感じ(当たり前)
10月
はじめての国際会議(in 宮崎)に参加した.
発表自体は不安でかなり練習したので問題なかったが,質疑応答がゴミだった.
帰ってきて落ち着く暇なく,2月開催の国際会議に提出する原稿を書いていた.
これも無事acceptedされたので,来年ギリシャに行けるようになった.嬉しい.
2019年の目標
- 競プロと英語と数学の勉強は無理のないペースで続ける
- 強化学習をじっくり勉強する
- 社会人を生き延びる
- 何か新しいことに挑戦する
一つずつ焦らず無理のないペースでゆっくり自分のできることを増やしていきたい.
最大フロー問題(循環フロー問題)の双対をとる
はじめに
近似アルゴリズム(V.V.ヴァジラーニ)の12章に最大フロー問題とその双対問題が載っているのだが、どのように変形したらその双対問題の式が得られるのか結構悩んだ。
そこで、未来の自分のために最大フロー問題から双対問題を導出する過程をまとめておく。
最大フロー問題と双対問題
最大フロー問題についてはリンク最大フロー問題 - Wikipediaを参照。
まず、近似アルゴリズム(V.V.ヴァジラーニ)では下記のように定式化されている。
一般的な最大フロー問題に、から始点へ容量が無限大の仮想的な辺を加え、循環フロー問題として考えている。
そうすることで、でもフロー保存則が成り立つ.また、このとき目的関数では、仮想的な辺を流れるフローを最大にすることになる.
制約式の意味は
- 辺を流れるフロー量が容量を超えない。
- フロー保存則(頂点に入ってくるフロー量より出ていく量の方が大きい)
これの双対を取ると下式になるとのこと。
実際に主問題を式変形をして、双対問題を得てみる。
双対をとる
まず、双対問題とは主(最大化)問題の上界を求める問題といえる(詳しくは後述)。
主問題の制約式の1つ目の両辺に、2つ目の両辺にを掛ける。
(3a)と(3b)の和は、、の設定によっては、主問題の上界となる。
この上界を、を上手く設定して最小化するのが、双対問題である。
(4) = (3a) + (3b)
上式が上界になる条件は「(4)左辺のの係数の和が、主問題の目的関数のの係数より大きい」であり、これが双対問題の制約式となる。
(4)(=(3a)+(3b))の左辺のの係数について考える。
(3a)では、がある。
(3b)では、頂点と頂点についての不等式で必ず現れる(元はフロー保存則を表す式なので)。
頂点には、フローが流れこむはずなので、が必ず存在し、
頂点には、フローが出ていくはずなので、がある。
よって、双対問題の制約式は、
となる。(主問題の目的関数にがあると考えれば右辺はわかる。)
目的関数は(4)の右辺を最小化することであり、制約式は(5)なので整理すると、
ここで、目的関数では、が出てくるが、
は無限の容量を持つと定義したので、は0以外の値を取れないことが自明にわかる。
そのため、最初に出てきた双対問題の式とこの式は一致する。
双対問題は主問題の下界(上界)を求める問題
例えば、下記の最大化問題で考える。
この問題の制約式の和を取れば、
上式の左辺は、係数の関係から最大化問題の目的関数より大きい。(は非負なため)
よって、制約式の関係から、解がで上から抑えられることがわかった。
もう少し一般化して考え、制約式の両辺にそれぞれ非負な数を掛けた和を取る。
が上界になるのは、の係数の関係により、下式を満たすときである。
この条件を満たした上でを調整することで、を最小化すれば、上界を最適解に近づけることができる。(実際は最適解と一致する)
それが双対問題である。
あとがき
間違っているところ多そうなので突っ込み貰えると嬉しいです。
双対の取り方とその意味がやっとわかりました。
いちいちLaTeXiTで数式の画像を生成して貼って、さらにサイズ調整とか面倒だったので、LaTeXで全部書いてpdfで上げればよかったと思いました。
「Linuxのしくみ」を読んで
はじめに
gihyo.jp
を読みました。
感想
低レイヤ寄りのことを知りたかったので読み始めました。
基本的な用語でも分かってないことがあったので為になりました。
この仕組みで複雑なアプリケーションが動いてるの凄すぎて気持ち悪い。
7章ぐらいから飽きてきてあんまりきちんと読めていないので、そのうち読み直します。
次は、OSの作り方でも読もうかと思います。
メモ
ただのメモ。
3章 プロセス管理
- fork関数(コピー)、execve関数(丸ごと書き換え)の動き
- デバイスドライバ、OSの仕事
4章 プロセススケジューラ
- スループットとレイテンシ
- プロセスのスケジューリング(niceで優先度設定ができる)
5章 メモリ管理
- taskset(cpu指定(それ以外にも色々機能がありそう)),time,ps(時間計測,ユーザ/カーネルモード)
- OOM killer(Out Of Memory)(メモリが足りなくなった時に適当に要らなそうなやつをkillする機能、vm.panic_on_oom)
- プロセス毎に 物理メモリに割り当て→ページテーブル(カーネルのメモリ上)作成(mmap)
- mmap()でページ単位で確保→mallocは内部でそれを切りわけて使っている
- 無駄なメモリ確保を防ぐデマンドページング(カーネルが初アクセス時に物理メモリへ割り当てる)
- Copy On Writeとは何か(fork()システムコールの時に仮想記憶が役に立っている、fork後が書き換えられた時にコピーする)
- OOMの救済にSwap、メモリ↔ストレージのスワップ領域
- メジャーフォールト(ストレージへのアクセスが発生)←こっちが重い、マイナーフォールト(ストレージへはアクセスしない)
- ヒュージページ(ページテーブルのメモリを減らす機構、まとめるページ単位を大きくまとめる)
- トランスペアレントヒュージページ(自動でヒュージページと通常モードを切り替える、Ubuntu16.04ではデフォで有効)
6章 記憶階層
- ライトバック方式(所定のタイミングでバックグラウンドでメモリに書き込む)、ライトスルー方式(キャッシュラインがダーティになった瞬間にメモリに書き込む)
- L3キャッシュはCPUで共有してたりする
- 参照の局所性(近い場所の又近い時間でデータにアクセスすることが多いので基本的にキャッシュが働く)
- キャッシュでは、物理メモリのページテーブル参照は高速化されない→Translation Lookaside BufferというCPUの機能がある
- ↑トランスレーション・ルックアサイド・バッファ - Wikipedia MMUがやってるらしい
- ページキャッシュ(メモリ↔ストレージ)の話、こっちはキャッシュライン単位でなくページ単位で扱う(キャッシュメモリはCPU↔キャッシュメモリ↔メモリ)
- ダーティページのライトバック周期はvm.dirty_writeback_centisecsパラメータで設定できる
- or vm.dirty_background_bytesの割合が超えた時ライトバック発生
- ハイパースレッド機能(よく分からんから後で調べる)
7章 ファイルシステム
- 容量制限=クォータ(ディレクトリ、ユーザ、サブボリューム等ごとに制限が掛けれる)
- ファイルシステムの不整合を防ぐ方式→ジャーナリング(トランザクションみたいな)、コピーオンライト(アホほどコピーとる)
- それでも駄目な時はfsck、だけど時間かかる割に望んだ結果にならないことが多い
- キャラクタデバイス、ブロックデバイスとは?(よく分かってないから後で調べる)
- tmpfs、メモリ上のファイルシステム、凄そうだけどこれもよく理解できてない
- ネットワークファイルシステム、Windows→cifs、Linux→nfs
- プロセスの情報は/proc以下にマウントされたprocfsで分かる(top,freeはここから採取)
- sysfsはprocfsの濫用を防ぐためにできた
- cgroupでリソース(CPU、メモリ)使用量に制限を掛けられる
- Btrfs、ファイルシステムのすごいやつらしい
あとでやる
- sarの使い方をまとめる
- ふつうのLinuxを読む
- OSの作り方を読む
2017年振り返りと2018年の目標
はじめに
最近,何も書いていないなと思ったらもう年末だったので,振り返りでもしようと思います.
2017年の目標と達成度
年始にふんわり立てていた目標と達成度.
2017年の感想
- 割りと講義とかバイトとか遊び等で忙しくて,思うように動けなかった.
- 気づいたら年末,年々年を取るのが早くなる
- インターンにいくつか参加するとともに,比較的暇な学部3,4年生の内にもっと行くべきだったと思った.
- 学部生にやってきたことを使って,アウトプットをしていたなぁという感じ.
- やりたいことを口にしていると協力してくれる人が結構いる.
2018年の目標
1~4月:研究と機械学習の勉強をメインに.
- 機械学習は何かしらの成果物をブログに上げる.
- 研究は海外学会発表に行く
5~8月:英語ガチ勢になりたい(夏に海外インターンとか行ってみたいので)
- TOEIC 800点以上
9~12月:研究のまとめとやりたい勉強.
Googleカレンダーを見ながら振り返り
1月
適当な学会に出す論文を書いていた.
あと,卒論も書いてたが,ほとんど前に書いたものを再利用したので,あんまやった気がしない.
卒論の発表にほとんど練習しないで望んだら,ぐだぐだ過ぎて怒られるかと思ったが,大丈夫だった.
そういえば,1~3月ぐらいまで36.8~37.5ぐらいの微熱が続いて辛かった.(医者に数回行ったが原因不明,恐らく副鼻腔炎)
それとは別に顎のあたりにしこりがあって,微熱も続くし,死ぬんじゃないかと思った.(実際は,微熱とは関係なくガマ腫というらしい)
2月
毎週遊びの予定が入っているので,遊び呆けていた模様.(微熱が治らなかった原因の1つ)
大阪にも行った.夜行バス+微熱で死にそうだった.
3月
1月に出した論文に一応査読が付いていたので,直し.
先生のコネでF研究所で3週間のインターンシップ.
内容は,詳しくはNDAで言えないが,仮想ネットワークの可視化してた.
知識0で行ったら,初日の説明会で知らない単語が無限に出てきてめちゃ焦ったが,割りとなんとかなった.まあまあ楽しかった.
3月末に卒業旅行で初の広島旅行に行った.
外国の方に「お前,日本人なのに広島も行ってないのかよ」みたいなこと言われたくなかったので,僕の希望で広島へ.
夜行バス+微熱で死にそうだった.
4月
何かをしてた形跡がない.3月まで疲れを癒やす1ヶ月.
5月
1月に投稿した奴のポスター発表のために北九州に行った(初めて本州以外の県に行った)
Yandex Algorithmの参加賞でTシャツ貰ってHappy:)
6~7月
インターンに数社落ちて悲しみにくれていた.
面接で落ちるの最高に精神に来る.
8月
コミケに初サークル参加.
友達4人と技術系記事の載った薄い本を書いた.僕はビットコインの仕組みについて書いてた(我ながら先見の明があると思う).
印刷所とか設営とか初めてなことだらけで大変だったけど,刷った30部が完売した時は感動だった.
冬コミも申し込んだけど,抽選漏れでした,残念!
9月
某社でインターン.やってきたことを評価してくれるし,かなり楽しかった.
初めて劇を見に行ったが,面白かった.
10~11月
アルバイトを新しく始めたら忙しくなってしまった.
DISCO presents Discovery Code Contestの本戦に出れた.
Ponanza開発者とプロ棋士の対談を聞きながら,もっと頑張らないといけないなと思っていた.
12月
学内でハッカソンを運営してた.小成功ぐらい.今後,大きくしていきたい.