TLE 2015というプログラミングコンテスト http://felicity.iiit.ac.in/contest/tle/ で香風智乃さんが優勝されました。 春休みの宿題の良い息抜きになったそうです。
記事を言付かっておりますので、ここに掲載させていただきます。
雑感
Twitterにリンクが流れてきたのでやってみたのですが、割と面白かったです。
Distinct Substrings
与えられた文字列に対して相異なる部分文字列の数を数えるだけの問題なのですが、 スコアが「提出したソースコードの異なる部分文字列の数 / 提出したソースコードの長さの2乗」で計算されます。 なんだこの問題…。
適当に書いたコードの後ろにランダムな文字列をくっつけて送ったら、 理論値の0.5に近いスコアが簡単にでたので、そのまま放置です。
Find the GCD
2000桁ぐらいの整数2つが与えられるのでそのgcdを求める問題でした。 ただし、入力に妙な制約があって、答えは2^16以下の2の累乗になります。
これだけだと普通の問題ですが、追加の制約として、+, -, *, /, % の文字を使わずに書けというものがあって、 ちょっと面倒だなと思いました。 さらにソースコードが短いほうがスコアが高くなります。苦手なゴルフです。
最初の方はまじめにビット演算で足し算するコードを書いていたのですが、 それでも十分良いスコアがでていたので、放置していました。 しばらくしたらダブルスコアぐらいで負け始めたので、まじめに考え始めました。
よく考えたら、C++なら演算子が使えなくても、 std::plus
次に、多倍長整数を読み込む部分を、最初一ケタずつ読んで10倍して足すというのを書いていたのですが、 よくよく考えたら、2^16 って 10^16 の約数になるんですね。 まじめに1ケタずつ読む必要なんてなかったわけで、 結局 cin から string で一気に読み込んで、後ろ16ケタぐらいを切り出して、 atol に入れるという残念なコードになりました。
最後に入力の整数の下位ビットの0の数を数えないといけないのですが、 これはgccなら__builtin_ctz()という関数を呼ぶだけです。
結局、std::plus() などの関数も使わないほど単純なコードになりました。 なんだこの問題…。演算子縛りとは。
Life, the Universe and Everything
一行ごとに整数がやってくるので、それをそのまま出力せよ、ただし42が来たらそこで終了する。 という問題です。これもなるべく短いコードを提出しなければいけません。
ただ、これだけではあまりにも簡単すぎるからかどうかは知りませんが、 この問題ではソースコードが -nostdlib というオプションを付けてコンパイルされます。 なんだこのフラグ…。
どうやらCの標準ライブラリなしでコンパイルされるので、 printfやscanfはおろか、read/writeのシステムコール、main関数呼び出し、 プログラム終了のためのexitシステムコール呼び出しをすべて自力で行わないといけないようです。 実行環境は64ビットLinuxのようでしたが、 64ビットLinuxで動くプログラムをスクラッチで書いた経験がなかったので、 システムコールを自力で呼び出す方法からお勉強です。
いろいろ調べた結果、rax レジスタにシステムコール番号を入れて、 あとは rdx, rsi, rdi などのレジスタに引数を渡してから、 syscallという命令を実行すれば良いことがわかりました。 64bit gccの呼び出し規約で使われるレジスタやその順番がシステムコールのものと違うので、 普通にインラインアセンブリで書くと値を移動するためにコードが増えてしまうので、 呼び出す側でシステムコールの順に引数を渡してやるようにすると、 最終的に、必要な移動は rcx -> rax だけになりました。
初めてでうまくやれるか不安でしたが、 なんとかそこそこの点数が取れました。 あとで聞いた話ですが、入力が固定だったらしく、 出力を止める位置を決め打ちで出来てしまったらしいです。 台無しです…。
ASCII Weaving
指定されたアスキーアートを、なるべく小さなコードで表示するという問題です。 画像圧縮系はあんまり得意ではないので、 単純なランレングスでお茶を濁すしかありませんでした。 もっと精進しなければ。
Halting
プログラムが与えられるので、それが停止するかどうかを判別するという問題です。
プログラムは main 関数ひとつからなっていて、int型の変数を3つ持って、関数呼び出しはなく… など、それっぽいことが書いてあるのですが、肝心の文法の定義がどこにも書いてありません。 セマンティクスの定義もありません。 そもそも与えられたプログラムがCのサブセットだということも書いてません。
ということは、これはプログラムの停止性を判定する問題では無いということですね。 もっとも、一般のプログラムに対する停止性の判定アルゴリズムは存在しないということは あまりにも有名ですが、そのサブセットを書く必要もなさそうです。
ということは、おそらく問題は決め打ちのはず…。 と思ってジャッジに投げながら先頭から順番に解答を確定していこうと思ったのですが、 どうもおかしいです。同じ入力でスコアがかなりバラつきます。 やっぱり決め打ちではないのかな…って思って、 でも全部yesを返した時のスコアは何回やっても同じです。 考えられる理由としては、停止するプログラムと停止しないプログラムの数を決めて、 それぞれ生成しているか、あるいは問題セットが同じでシャッフルされているかぐらいですが、 問題をランダム生成するには、かなり荷が重い問題だと思いますし、 そもそもそれでは誰も解けなくなってしまうので、 やっぱりシャッフルしてるだけだろう、とあたりをつけてやってみると、 あっさり解けてしまいました。
この問題で苦労したのは、どういうわけかわからないのですが、 rand() を呼び出すと問答無用でエラーもなく0点にされてしまうところでした。 これに気づくまで、自分のコードが間違っているのか、方針が間違っているのか、 判断がつかなくて大変でした。
Reverse Quine
自分自身を反転したものを、自分自身の長さ回繰り返し出力するプログラムをできるだけ短く書くという問題です。
クワインは苦手です。 それに、順位表を見ていると、クワインのプロの方がいっぱいいらっしゃったので、 これは勝てないだろうなあと思っていました。 すごく苦労しましたが、なんとか正の点数がもらえるコードが完成したので満足です。