■
TLE 2015 だった。
最初は 2/7 にやるよ！って書いてあったような気がするんだけど、いつのまにか 2/11 → 2/12 → 2/27 → 2/28 にどんどん延期されていってやばかった。そのせいか参加者少なすぎ。
問題一覧はここを見るとよい
http://d.hatena.ne.jp/ku-ma-me/20150302
提出したコードはここ
https://gist.github.com/kik/ba7f3ba6699932539913
Distinct Substrings
やるだけ。どうやったら点数が変わるのか分からなかったので通しただけだったけど、98点あったので放置。どうやったら点数が減るのかが逆にわからない。たぶん、点数を最大化する方法をkinabaさんが解説してくれるんじゃないかな。
Find the GCD
5人しか通せてない。見たところみんなやり方が違って面白い。
- 多倍長を使う派
- 互除法使う派
- x & -x派
- 1bitずつシフトする派
- 多倍長しなくていいじゃんに気づいた派
- __builtin_ctz派
- 1bitずつシフトする派(無限ループ)
最初は多倍長＋互除法で実装して通した。最初のはldiv()で割り算してた。一度通ってしまうと改造するのも楽ちん。
ldiv()で互除法はめんどくさいし、足し算を書いてたので x & -x のほうがいいかなと思って通らない。
gcd(x, 1<<R)
と
x = x & -x min(x, 1<<R)
って同じに見えるじゃないですか！でもサブミットしたら通らないし、実行に差がでる場合を全探索した結果、x = 0 のときだけ結果が違いました！なので、
x = x & -x x ? min(x, 1 << R) : 1<<R
みたいなくそコードになったんですが、よく考えたら
x |= 1 << R x & -x
でできました。orとってビット演算する方式は__builtin_ctzするチノちゃんのコードと同じですね。ffsじゃだめだったのかよく知りませんが。
Life, the Universe and Everything
これはさらに通してる人が少ないわけですが、みんなだいたい同じです。みんな当然のように'\n42\n'と比較してたんです。これだと、最初に"42\n"が来たときに困るなあと思って、わざわざバッファの先頭に'\n'を置いたり、終端を検査したり、まじめコードを作ってたんです。サブミットしたらそんな真面目に書かなくても通ることが分かったので、これは答も定数になってるんじゃねと思ってやってみたら、やっぱりマジックナンバー917を当てる問題でした。
なので、stdinから917バイト読んでstdoutに917バイト書いてexit(0)
ASCII Weaving
去年のしょぼい圧縮コードを持ってきて、そのままコピペしました。shinhさんと同じくらいの点数になったしそれでいいや。
Halting
最初は適当に全部yesにして4点。
先頭だけnoにするところころ点数が変わる。あと、問題は30問あるっぽい。
ってのがわかったので、yesを17個、noを13個をランダムにシャッフルしてみたんだけど全然点数にならない。
ということで、問題がシャッフルされてるぽいってことはわかった。というわけで、問題をテキスト順でソートして、その順番にyesとnoを固定で割り当てて、元の順に戻して出力するってのを書いたつもりだったんだけど、どっかバグってたのかうまくいかなかった。チノちゃんはこれで満点だったっぽいので、何かをどっかで間違えたっぽい。
しかたないので、諦めてテキストの適当な性質で分岐していくことにした。whileの数とかifの数とかで分岐して、各分岐を何回通ったかを数えて、1回しか実行されないコードにがんがん分割していって、yesとnoを割り当てていく作戦にした。これをやっていっても最終的には満点になるはずだったんだけど時間が足りない。
Reverse Quine
まず、コードが通らない。通らないのはなぜかというと、問題文にとちゅうにある改行は消すよって書いてあったから。よくみたら最後の改行しか消してない。なので、本当に基本的な、printf(p, 34, p, 34) 型でなんとか通す。本当は一昨年からずっと使われてるマクロを使うべきだったのに時間が足りない。
まぼろしの残り3問
SNUSP http://esolangs.org/wiki/SNUSP というesolangで書けというのが3問あった。起きたら無くなってた。
[ICFPC] ICFPC 2013 の記録
初日
問題だけ読んで、/myproblemsを送ってみるのを試して仕事に行く。23時ごろから作業開始。
とりあえず、JSONとかHTTPとかをCとかで書きたくないので、Rubyで適当に書いたドライバとopen3で通信するソルバ群にしようということにする。
最初のソルバは「xor, and, shift」だけの問題を解ける簡単なのを作ってみる。すなわち、線形なので(1 << i)に対応する値だけで答ができるやつ。
すぐにできたんだけど、解ける問題が少なかったのでお蔵入りして、HTTPとJSON部分のテスト用にしか使わなかった。
簡単な問題をまず全探索で解こうということになり、式の生成方法を考える。変数の数は1個か3個の場合を考えればいいかなと勘違いをする。最後のぎりぎりまでこの問題に気づいてなかった。「tfold」のときは変数が一個隠蔽されるので、2個の場合も作っておけば枝が減ってた。
サイズが1の式をまず列挙する
// terms[サイズ][使う変数の数: 0は1個。1は3個] terms[1][0] << "(0)" terms[1][0] << "(1)" terms[1][0] << "(x)" terms[1][1] << "(y)" terms[1][1] << "(z)"
サイズがS-1の式まで列挙できたら、サイズSの式を列挙する
foreach (s1 + s2 == S - 1)
foreach (v1 in [0, 1])
foreach (v2 in [0, 1])
foreach (t1 in terms[s1][v1])
foreach (t2 in terms[s2][v2)
terms[S][max(v1, v2)] << "(plus t1 t2)"こんな感じ。簡単だね。実際のコードもこんな感じ。まんまそのまま簡単だね。
# if0
1.upto(s - 3) {|s1|
1.upto(s - s1 - 2) {|s2|
s3 = s - s1 - s2 - 1
2.times {|v1|
2.times {|v2|
2.times {|v3|
v = [v1, v2, v3].max
$terms[s1][v1].times {|t1|
$terms[s2][v2].times {|t2|
$terms[s3][v3].times {|t3|
gen_if0(s, v, [s1, v1, t1], [s2, v2, t2], [s3, v3, t3])
}
}
}
}
}
}
}
}で、生成した大量の式の保存先はどうしようかと考えたんだけど、一番お手軽なやり方を思いついたので(すぐに破綻する)やってみる
// ばばーーん
#include "bf.h"
Term t_s2_v0_0 = { NOT, &t_s1_v0_0, 0, 0 };
ull f_s2_v0_0(const ull *v)
{
return run_NOT(f_s1_v0_0(v));
}
Term t_s2_v0_1 = { SHL1, &t_s1_v0_0, 0, 0 };
ull f_s2_v0_1(const ull *v)
{
return run_SHL1(f_s1_v0_0(v));
}
Term t_s2_v0_2 = { SHR1, &t_s1_v0_0, 0, 0 };
ull f_s2_v0_2(const ull *v)
{
return run_SHR1(f_s1_v0_0(v));
}
Term t_s2_v0_3 = { SHR4, &t_s1_v0_0, 0, 0 };
ull f_s2_v0_3(const ull *v)
{
return run_SHR4(f_s1_v0_0(v));
}
Term t_s2_v0_4 = { SHR16, &t_s1_v0_0, 0, 0 };
ull f_s2_v0_4(const ull *v)
{
return run_SHR16(f_s1_v0_0(v));
}
Term t_s2_v0_5 = { NOT, &t_s1_v0_1, 0, 0 };
ull f_s2_v0_5(const ull *v)
{
return run_NOT(f_s1_v0_1(v));
}
Term t_s2_v0_6 = { SHL1, &t_s1_v0_1, 0, 0 };
ull f_s2_v0_6(const ull *v)
{
return run_SHL1(f_s1_v0_1(v));
}
Term t_s2_v0_7 = { SHR1, &t_s1_v0_1, 0, 0 };
ull f_s2_v0_7(const ull *v)
{
return run_SHR1(f_s1_v0_1(v));
}
Term t_s2_v0_8 = { SHR4, &t_s1_v0_1, 0, 0 };
ull f_s2_v0_8(const ull *v)
{
return run_SHR4(f_s1_v0_1(v));
}
// まだまだ続くこれのすごいところは、実行時の式の評価がネイティブコードなので凄い速いところだ！
このあたりで寝る。
二日目
昨日書いたコードで巨大なCのソースを吐き出してコンパイルを始める。
簡単な問題は瞬殺できるようになったので、自動ポストを1時間ほど動かして160点ゲットする。
送信した答えを見てたら、ほとんどの問題が簡単な式で解けているので、実はサイズが大きくても簡単な問題がいっぱいあるんじゃないかってことに気づく。これにより、ソルバの最終バージョンで最終日に全問題特攻すればかなり点数が伸びそうなことが分かった。
調子に乗って生成する式のサイズを少し増やしてみたら、大変なことに気づいた。Cのソースが大きくなりすぎて、コンパイルが全くおわらない。確かに2000万行あるソースを2GBのメモリでコンパイルするのは無理がある。gccはやめてclangにしてもだめで、tccも試したけどあんまりよくなかったので、新しい64bitVMを作ることにする。
とりあえずLinux Mintにしてみたんだけど、ミラーサイトが遅くてなかなか落ちてこないとかで、3時間ぐらいこの辺で使ってた気がする。
でも、8GBのVMはさくさく動いて快適だった。
けど、やっぱり2000万行のソースは無理ぽだったので、ツリーだけ吐いて関数部分は吐かないようにしてみたりしたんだけど、やっぱりコンパイラがネックになって全然サイズが増やせないし、これもうツリーだけ吐くんならバイナリファイルに保存すればいいんじゃねってことになって、そうした。
// これはディスクに残ってたやつ。PLUSとXORだけで1000万行ある。
// 問題ごとにこんなのをコンパイルして万全の体制で挑もうとしてた。
#include "bf.h"
static Term t_s3_v0_0 = { XOR, &t_s1_v0_0, &t_s1_v0_1, 0 };
static Term t_s3_v0_1 = { PLUS, &t_s1_v0_0, &t_s1_v0_1, 0 };
static Term t_s3_v0_2 = { XOR, &t_s1_v0_0, &t_s1_v0_2, 0 };
static Term t_s3_v0_3 = { PLUS, &t_s1_v0_0, &t_s1_v0_2, 0 };
static Term t_s3_v0_4 = { XOR, &t_s1_v0_1, &t_s1_v0_2, 0 };
static Term t_s3_v0_5 = { PLUS, &t_s1_v0_1, &t_s1_v0_2, 0 };
static Term t_s3_v1_0 = { XOR, &t_s1_v0_0, &t_s1_v1_0, 0 };
static Term t_s3_v1_1 = { PLUS, &t_s1_v0_0, &t_s1_v1_0, 0 };
static Term t_s3_v1_2 = { XOR, &t_s1_v0_0, &t_s1_v1_1, 0 };
このあたりで寝る。自動ポストをしかけて寝たので、起きたときには220点ぐらいになってた。
三日目
昨日のツリー生成をRubyでやると遅いので、C++でやることにした。そうすればいちいちファイルを読み書きしなくてもいいし。
コードもどうせforループが10個ぐらい入れ子になったのをコピペしてくるだけだし。
そのあと、もう少し頭いい方法はないものかと色々試行錯誤するも全然うまくいかなかった。仕方がないので、bonus問題ぐらい解けるようになろうと思っていじってたんだけど、完全に体力の限界で何を書いてるのかさっぱりわからんぐらいだったので諦めた。「if test then else」の「then」か「else」かのどっちかに当たる部分は大体一発で生成できてるから、あとはヒントを元に残りの部分を埋めるだけだったんだけど、どんどんコードがぐちゃぐちゃになっていって４時になっちゃったので諦める。
今までできたぶんで、自動ポストを走らせて寝る。
最終結果
{
"easyChairId":"370",
"contestScore":992,
"lightningScore":0,
"trainingScore":103,
"mismatches":333,
"numRequests":3100,
"requestWindow":{"resetsIn":11.065,"amount":1,"limit":5},
"cpuWindow":{"resetsIn":11.065,"amount":0.8,"limit":20},
"cpuTotalTime":3072.344
}まあ一人でやったらこんなもんだよね。
最終コード
https://gist.github.com/kik/6209891
結局、起動するごとにツリーを作ってるしぐだぐだやね。
ひとりアドベントカレンダー三日目
圏論で可換図式をおっかけて証明するようなときに、合成とか並べていたら読みにくくてしょうがないというのは実はみんな思ってることらしい。たまたま読んでたNorthcott「ホモロジー代数入門」に分かりやすい記法が載っていました。
AとBとCを対象として、射A->Bや射B->Cがコンテキスト中に一つしかでてこないときは、その射をABやBCと書くことにする。合成は普通とは反対向きに並べて、(AB)(BC)のように書く。さらにその合成をABCと書く。
さらに射が写像のときは、元aの像をaABとかaABCとか書く。
というように書くとどう見ても証明が読みやすいです。本当にありがとうございました。
この本によると、元ネタは Yoneda, N. "On the Homology Theory of Modules" J. Fac. Sci. Univ. Tokyo, Sect.I.7 (1954), 193-227 だそうです。ぐぐってみたら米田の補題の初出だとキマイラ日記に書いてありました。おわり。
情報幾何
[数学] ひとりアドベントカレンダー二日目
なんだか、確率とか統計とか幾何的なイメージが出てこないから難しいし、情報幾何とか先に知っておくと分かりやすくなるんじゃね。知らんけど、たぶん。
確率測度の族を多様体だと思って微分幾何をやろうって話。PRMLとか突然KLダイバージェンスとか出てくるけど意味わからんし、時々幾何学的な直観だとこうだよとか出てくるけど意味わからんし、やっぱりちゃんと知っておきたい。とりあえず今のところ読みたいものリスト。
http://staff.aist.go.jp/s.akaho/papers/infogeo-sice.pdf 情報幾何と機械学習
たぶん最初に読むべきなのはこれかなあ
http://ci.nii.ac.jp/naid/110003892293 講座 情報幾何とその応用-I : 情報幾何とは何か-入門編
http://ci.nii.ac.jp/naid/110003892312 講座 情報幾何とその応用-II : 凸解析と双対平坦空間
http://ci.nii.ac.jp/naid/110003892247 講座 情報幾何とその応用-III : 統計的推論の情報幾何
さらにIXまであるから長い。
これって、アドベントカレンダーじゃなくて、ただの積読リストじゃね？
D問題
めんどくせー。格子点の方向にだけ光線を飛ばせばいいのはすぐにわかった。でも四角との交点の座標が有理数になる。めんどくせえー。
最初はboostの有理数ライブラリを使って、直線と直線の交点を求めたりくそ複雑なコードを書いてみたんだけど、遅すぎるうえに計算が間違ってる。
しかたがないので、めんどくさくない方法を考えて、光線の方向が決まったら有理数が発生しないように空間をスケールしておけばいいじゃん。
ついでに、縦横のスケール比を変えれば８方向だけの移動しかなくなるじゃん。やったー。これで方程式解かなくても一歩ずつぶつかるまで歩いていけばいいじゃん。
https://gist.github.com/2391863
やったー実装できた。しかもかなり速くなったー。
C問題
非常にやるきがないので適当
