ICPC アジア地区予選 東京大会 2014 参加記
結果
5完17位(University rank14位)でした。 Colorful Jumbo ChickenがおそらくWF出場権を得ます。今回の結果を考えると、仮に台湾大会でWF出場権を得てもおそらくWFは辞退することになります。
コンテスト中にしたこと
- 筆箱を忘れる
- .Xmodmapを書く
- .vimrc, .emacsを書く
- テンプレートを書く
- Bをバグらせる
- ゴミ実装力
- Gをバグらせる
- ライブラリをちゃんと整備しておけばここまでバグらなかったはず(データ構造は自分の担当)
- 引退したチームのライブラリを持ってきていて、その中にあった。ちゃんと確認しておかないとダメだった
感想
- なにもかもダメだった
- 引退
昨日の結果がダメダメだったので引退です
— そすうぽよ (@_primenumber) 2014年10月19日
- あまりにも辛いので額にJAGシールを貼って引退宣言。
来年度どうするかはまた考えるとして、一応経験を積むためにとりあえず台湾大会は出る予定です。
ICPC 国内予選 2014 参加記
ICPCの国内予選に出たことについての感想を書きます。
チームと結果
チーム名: Primasta
メンバー: @asi1024 @TakiTakiTakise @_primenumber
6問正答/全7問, ペナルティ: 23875
全体で5位、大学別4位、大学内1位
国内予選が始まるまで
京大から他にAlkachu,Colorful Jumbo Chickenという強いチームが出るので、ツイッターでは
絶対全完して学内一位取ろうな
— そすうぽよ (@_primenumber) 2014年7月10日
起きれたしICPC勝利も同然。
— そすうぽよ (@_primenumber) 2014年7月11日
みたいなことを言っていたが、模擬国内予選の結果を鑑みるにアジア地区予選に出られる望みは薄いなあという感じでいた。
特に前日深夜のTopcoder SRMで0完してしまい気分が最悪な感じな上に、ICPCが始まるまでに起きれるかが不安になる程度に生活習慣も崩れまくっていてダメダメっぽい感じ。
競技開始直前
チーム内で担当をどうするか決めた。私は模擬国内予選の時に他人の書いたコードのバグを見つけるのが上手いらしいことがわかったので主にデバッグ担当をすることに。
デバッグ担当は実装担当が実装してる後ろでバグってそうな場所を突っ込んだりする。ペアプログラミングの要領。
競技中
私が実装した問題のみソースコードを載せます。 asiさんが実装した問題のソースコードはhttp://asi1024.hatenablog.com/entry/2014/07/14/034221から見れます。
A問題
実装: @asi1024 デバッグ: @TakiTakiTakise
私は問題を読んでない。5分程度でAC。この間にB問題を読んでどういうふうにコードを書くか考えた。
B問題
実装: @_primenumber デバッグ: @TakiTakiTakise
制約が緩いので単純にシュミレートするだけだけどちょっとバグりやすかった。15分程度でAC。
C問題
実装: @asi1024 デバッグ: @_primenumber
シルエットの座標が整数しか取らないことを利用すると実装が簡単になることをasiさんが見抜いていたので早かった。10分程度でAC。
D問題
実装: @asi1024 デバッグ: @_primenumber
各文字について変換が高々一回しか起こらないので、候補となる文字列を全列挙できることをasiさんがすぐに見ぬいた。パフォーマンスを重視してmapではなくvectorを使うことにしたが、重複が起こりうることを忘れていてWAしてしまったので裏目に出た。17分程度でAC。
E問題
実装: @TakiTakiTakise デバッグ: @_primenumber
ほぼ同じ問題を解いたことがあったので、解法はすぐにわかった。 実装を楽にするために(辺の重みの3倍)-(葉についている辺の重みの2倍)-(葉を除いた木の直径)という求め方をした。DFSを2回して木の直径を求める方法を忘れていたので各頂点からDijkstraをした。実装をどうするか詰めている間にasiさんにDijkstraのライブラリを写してもらった。
23分程度でAC。それなりに上位にいたが、残り2時間弱あることを考えると十分に抜かされうるので、時間をかけてでも必ずどちらかは通そうという事を考えた。
G問題
実装: @asi1024 デバッグ: @_primenumber, @TakiTakiTakise
Fはサイコロのやばそうな問題に見えたので、まだわからんこともないGを考えた。幾何ライブラリにお世話になりながら、いろいろなバグに苦戦を強いられたが、1時間半弱かけてAC。この間にぼんやりとF問題の解法を思いつく。ACした瞬間のうれしさは半端無かった。ここでアジア地区予選に行けることを確信。
F問題
辞書順とか関係なく、与えられた6つの数を持つサイコロが作れるかがO(t)で判定できれば解けることに気づいたので、asiさんに言ったら作れるかの判定が割と簡単にできるとわかり、実装しようとしたがさすがに時間がなかった。
全体的な感想
今年の問題セットは考えれば実装がかなり楽になる問題が多かったように思う。実装が苦手な傾向のあるPrimastaにとって有利に働いた気がする。
うーん、でもこの結果はさすがにうまく行き過ぎに思えるなぁ。チーム戦略がうまくハマったのも大きそう。
今後について
JAGの夏合宿に参加したかったけど運転免許の教習とかぶってしまったので出れなくて悲しい。
それはともかく、精一杯World Finalに行けるように頑張りたいけど、数学にそろそろ本腰を入れないとやばいので困ってしまう。
Lenovo ideapad s210上のDebian wheezyで無線LANを使えるようにするには
必要な作業は多くないけど、日本語の情報もないので備忘録程度に書いておきます。
症状
無線LANデバイスの型番を調べる
なにはともあれ、とりあえず必要な情報を集めます。
端末上で
$ lspci
と入力すると、PCIにつながっているデバイスがぞろぞろと出てきます。その中に02:00.0 Network controller: Atheros Communications Inc. AR9565 Wireless Network Adapter (rev 01)
という記述を発見。どうもこれっぽい。
※一般に、無線LANデバイスにはPCI接続するもの以外に、USB接続するもの、PCカード接続するものなどがあり、特にノートPCではどれであるかを見分けるのが難しいです。PCIにつながっているデバイスにそれっぽいものがない場合はUSB接続されている場合などがありえます。
HowToIdentifyADevice/PCI - Debian Wiki
HowToIdentifyADevice/USB - Debian Wiki
などでそれっぽいデバイスがないかどうか調べましょう。どれにもない場合、そもそもOSがデバイスの存在を認識していない可能性があります。その場合は多分結構大変です。頑張ってください。
ググる
とりあえず無線LANデバイスの型番がAtheros AR9565であることはわかったので適当にググります。
すると、
Debian User Forums • View topic - [SOLVED] Getting Atheros AR9565 wireless to work
要は「Atheros AR9565を動くようにしたい」という内容で、症状もほぼ同じです。
どうやらLinuxカーネルを新しいものにするとデバイスドライバが入って使えるようになるよ、という話らしい。
Linux kernelのバックポート
DebianはLinux Kernalがメジャーアップデートされてもそれに追随せず、今入っているバージョンのマイナーアップデートとバグフィックスが適用されるだけなので、新しいバージョンを入れるためには少し作業が必要になる。
リポジトリの追加
/etc/apt/sources.listに次の行を追加する。(管理者権限が必要)
deb http://dennou-k.gfd-dennou.org/debian/ wheezy-backports main
(http://dennou-k.gfd-dennou.org/ は自分の使っているミラーサーバーに変えたほうが良い)
さらに、端末上で、
$ sudo aptitude update
$ sudo aptitude -s install linux-image-3.11-0.bpo.2-amd64
としてやると新しいカーネルがインストールされる。このとき、依存関係の問題でなにか質問されるので、一回目はn、二回目はyと答えると正しくインストールされたはず。
このあと再起動してやればちゃんと無線LANに接続できます。
参考文献
Debian User Forums • View topic - [SOLVED] Getting Atheros AR9565 wireless to work
ブラウザ上でBrainf*ckを実行･デバッグできるサービスを作りました.
デバッグモードをONにして,｢1ステップの実行時間｣を0より大きい値にするとプログラム実行中のメモリの様子や今どこを実行しているかがリアルタイムでわかります.コード中に@があると,そこでプログラムが一時停止するので,簡易的なブレークポイントとして使えます.｢追跡するメモリのサイズ｣で先頭から何バイト目までトレースさせるかを調節できます.あまり大きくすると実行が遅くなります.
デバッグモードがONで｢1ステップの実行時間｣が0だと@に到達するまでの状態は表示されませんが,高速に実行されます.
デバッグモードをOFFにすると@を無視して最後まで実行します.
｢入力の形式｣はテキストエリアに入力した文字列をそのまま入力として扱うか16進数のデータ列とみなすかを選択できます.16進数を選択するとキーボードからは入力できないデータも入力として与えることができます.
このインタプリタは特に最適化などは施していないのであまり速くありません.とてもたくさんのステップ数のかかるプログラムを入れると固まります.それから,括弧の対応がおかしい場合も無限ループにはまって固まるかもしれません.
これでみなさんも快適にBrainf*ckプログラミングを楽しみましょう!
実用Brainf*ckプログラミング
高校生の頃にBrainf*ckでFibonacci数を計算して表示するプログラムを書いて以来,何度かBrainf*ckのコードを書く機会があった.受験生の頃には,受験勉強をするふりをしてHanoiの塔を解くBrainf*ckのコードを書いた.
京大生になってKMCに入って,いろいろな面白いことをしている人はいたけど,Brainf*ckのコードを書く人は見当たらなかったので,自分の持っているテクニックをまとめてみたら面白いのではと思って,KMC内で「実用Brainf*ckプログラミング入門編」という内容でBrainf*ckの初歩的な内容を発表したら,わりとウケたので入門編だけでなく全編作ることにした.
projectpn - brainf*ckでbrainf*ckインタプリタ
とかはこのために書いたもので,今のところ初級編で扱う予定.
一応Brainf*ckである程度のプログラムが書けるくらいには網羅的に様々なトピックを取り扱いたいと思っているが,一人で書いているので色々と抜け落ちていそう.
