Hatena::Grouptopcoder

tanakhの日記 このページをアンテナに追加 RSSフィード

 | 

2010-02-19

TLE

03:01 | TLE - tanakhの日記 を含むブックマーク はてなブックマーク - TLE - tanakhの日記 TLE - tanakhの日記 のブックマークコメント

http://felicity.iiit.ac.in/tle/judge/index

http://felicity.iiit.ac.in/tle/judge/ranks

密かに参戦。なんだか7位。ゴルフ力を鍛えたい。

PALIN1

(n^n)%p を出力するプログラムを書け。n,p<10^18。ただしプログラムはxを文字列をして (x[1 : (length(x)-1)])(x)(Reverse(x)) のような形をしていること。

n^nとかは普通にやってたらTLEなので、ビットのたってるところだけ書けてlognでやるあれで。入力がでかいのでそのままかけ算できないので、掛け算を足し算で代用。そのままやると遅いので、ビットのたってるところだけ足すあれで。そうすると、累乗と乗算が同じコードになる。やったー、と思ったときは一位でしたが、最終的にはゴルフ負けした。それと、結局このプログラムの形にさせることになんの意味があったのかはわからずじまい。みんな単に二個目以降をコメントにしてるだけで、だれも謎を解けず。想定解を知りたい。

PALIN2

PALIN1と同じだが、n,p<10^5で、プログラムの形がxを文字列として xxx になっていること。値が小さいので線形ループで間に合う。かけ算すると微妙にintをあふれるので途中long longで計算する必要あり。これもまあ普通にいけてるなあと思ったけど、最後にはゴルフ負け。gets()を無引数で渡しても落ちないとか分からない。forループの融合もやってみたけど、とんとんが精一杯でした。この問題も同じコードを三回繰り返すことの意味はわからず。想定解が知りたい。

PREP

プリプロセッサでFizzBuzzを1000まで出力せよという問題。マクロでの改行の入れ方がわからずに、どうすればまともなスコアが出せるんだ、とゆっくり考えると、なんとか#include __FILE__ を思いついたので、ぎりぎりなんとか。#line が式を受け入れられたらもっといろいろできたのになあとか、__LINE__の値が実際に使われるまで遅延されるとか、いろいろなアイデアをことごとく潰され続けた。結局__INCLUDE_LEVEL__とか、__COUNTER__とか、知らんがなという感じの答えがトップでした。もっとプリプロセッサ勉強しないとなあ。

CARM

制限時間内にカーマイケル数をなるべくたくさん出力せよという問題。この問題はトップがずっとダントツで、ずっと方針に自信がもてなかった。まず、小さい方の奇数からカーマイケル数かどうかを全部調べるという方針でやったら、だいたい200個ぐらい出力できて、スコアが0.01ぐらい。完全にだめ。次に、素数の三つ掛け合わせを全列挙して、カーマイケルすうかどうか調べるというのをやるとだいたい1万個ぐらい出せるようになった。これで2-3点ぐらい。どうにもダメなんで、Wikipediaのリンク先とかで調べると、(6k+1)(12k+1)(18k+1)のそれぞれの項が素数ならこれはカーマイケル数だというのがあったので、これにkをいろいろ入れてやると10点近くになった。そのへんで時間切れ。素数判定を素数で割っていくよりも、ミラーラビンテストの方がはやかったのだけど、ふるいで予め素数判定テーブルを作っておく方がはやかった。1億要素で1秒ぐらいで終わる。で、最終的にはそこから3倍ぐらいは高速化された。トップにはまだ3倍ほど差があるが、もっと時間を使って頑張れば追いつけないことはなかったと思う。

COMP

与えられた文字列を出力するプログラムを書け。なるべく短く。

これもまあよくわからないけど、とりあえず圧縮と聞くとLZ77かなと思ったので、LZ77作る。途中アスキーアートが入ってるので、ランレングスでもいいのかなあと思ったが、LZ77でも縮むだろうと。符号化がちょっと悩んで、文字列に含まれない文字種で、かつCの文字列に含めてエスケープが必要ない文字を列挙すると36文字ぐらいあったので、それで24+12ぐらいに分けて、位置と長さをエンコード。イマイチな結果。トップのコードはCの文字列にバイナリを含めたりしているのだけど、バイナリを含める方法がわからなかった。あんまりわからんわからん言っててもあれなのだけども。バイナリ含めるんだったら、大幅に使える文字種が増えたので、だいぶ短くなっていたはずではある。あと、MTFとかエントロピー圧縮もできたのかなあ?

SHORTEN

与えられたプログラムと同じ動作をするプログラムを作れ。なるべく短く。

与えられるプログラムはよく読んでないが、()(()) みたいなかっこのみで構成された文字列が与えられるので、それが左右の対応が取れているかどうか調べるというもの。もとのプログラムはツリーを使ってごちゃごちゃやっていたが、普通に毎回なめるプログラムが通ったので、大幅に短くなる。うほお短くなった、とサブミットしたときは余裕の1位でほくほくだったが、終盤にはやっぱりゴルフ負けする。もうだめぽ…。

KEY

ある数のサブセット(ビットを倒した数の集合)のうち、ビットを左右反転させた時のビットの違いの箇所がp以下の物の数を求めよ。ただし、プログラム中の予約語とか、セミコロンとか、空白に対してすごいペナルティーがかかるので、なるべくそれらを使わないで書くこと。

問題文の難しさが半端ない。三時間ぐらいずっと読んで、結局わからなかった。フォーラム検索して、reverseって書いてあるのが、ずっと01反転だと勘違いしていたことに気づく。なんというわかりづらさ。プログラム自体はすぐ。それで、とりあえずforを潰すためにプログラムを末尾再帰な関数呼び出しに変えて、return書きたくないので、CPSぽくして、とりあえず予約語は全部消したが、なんかあんまり楽しくなかったので、それ以降は手をつけず。

CQUINE

nに対して、それを超えない最大の2^aな数を出力するという問題Aと、それを超える最小の2^aな数を出力するという問題Bがある。プログラムAは、問題Aをとき、かつ、-1が入力されたときはプログラムBを出力する。プログラムBは、問題Bをとき、かつ-1が入力されたときはプログラムAを出力する。プログラムAをサブミットせよ。

山手線クワインとかと同じような感じで、あれ見たとき完全に変態だなあと思ってたのに、まさか自分が書くことになるとは思いもよらなかった。クワインただでさえ苦手なのに、さらにループさせて、ゴルフもしないといけないのは相当厳しいと思われたが、やってみると意外と楽しかった。とりあえずintの変数が0か1かでそれぞれのプログラムを表すことにして、プログラム出力するときにそれを切り替えればいい。あとはひたすらゴルフゴルフで、文字列出力の際にエスケープしたくないから、%と、"を全部消去。%を消去するために文字列をintにしたりした。まあでも所詮はクワイン初心者で、ゴルフもアマチュアレベルなので、トップには遠く及ばず。

まとめ

二日目の最初のあたりまではトップで、あれ、結構いけるんじゃないかなと思ったけど、二日目寝ておきたら7位になってて、もうだめぽな感じだった。ある程度まで短くするのは問題ないのだけど、最後の1バイト2バイトの勝負になってくるともう勝てる気がしない。練習を積むしかないなあ。しかしこういうのは言語仕様の重箱をつつく結構いい勉強になるので楽しかった。今回も知らないテクニックを沢山知ることができた。とくにcppの仕様は今までほとんど気にしたことがなかったので面白かった。来年もあるかもしれないので、それまでゴルフ場でトレーニングすることにする。

トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20100219
 |