37.50.48

%20 の ブログ

yukicoder No.502 階乗を計算するだけ

この記事は、yukicoder No.502 階乗を計算するだけ の解説というより、自分が書いたコードの解説です。

 

作問者による解説にもある通り、この問題は、予め一部の値を計算しておいて、それを埋め込むことで解ける。作問者は「例えば1000個を埋め込む」と解説しているが、速い言語であればそこまでたくさんの値を埋め込む必要はない。

n が 10^9+7 未満の場合について、10^8 毎に区切って 11 個の値(0!, 10^8!, 2*10^8!, ..., 10^9!)を埋め込むと 500ms ほどで AC ということが tails さんの提出したコードから分かっていたので、ほぼ同じようなコードを提出したところ、なぜか TLE だった。

原因を探ったところ、m=1e9+7;s=1e8; という部分に問題があった。

これは何なのかというと、普通にコードを書くと 1000000007, 100000000 という値が 2 回ずつコード中に出現し、それだとコードが長くなるので、グローバル変数(型名を省略すると int 型になる)を初期化して(このとき暗黙の型変換が行われる)、それらの変数を 2 回ずつ使うことでコードを短くしようとした結果生まれたものである。

これを使うと何が悪いのかというと、(実際には初期化した以降で変数の値が書き変わらないものの、)変数で剰余をとると定数で剰余をとるよりも遅いという問題がある。

const を使うとこの問題は解決できる

 

というわけで、ここからコードを縮めるにはどうすれば良いかというと、まず埋め込みを減らしたい。最大で 10^8 回のループを回して 500ms より少し遅いということから、2*10^8 回のループを回すと TLE することが予想される(実際に TLE だった)。

なので、166666668 毎に区切って 6 個の値(0!, 166666668!, 333333336!, ..., 833333340!)を埋め込むことにした(ここでもし 166666667 毎に区切ってしまうと埋め込む値が 7 個(0!, 166666667!, 333333334!, ..., 1000000002!)になってしまい、最後の 1 個が邪魔になる)。

埋め込む値の中に 500000003 という値があったのでそれを 5e8+3 と書くなどして 167B まで縮んだもののまだ長い。

 

そこで、文字定数を使って 156B まで縮めた。文字定数というのは、通常は 'a' のように 1 文字をシングルクォートで囲って使うものだが、複数文字を囲って使うこともできる(コードゴルフでは、1 文字を囲う使い方は基本的にしない。例えば 'a' より 97 の方が短いので 'a' を使う理由が無く、'z'122 では長さが同じなので 'z' を選ぶ必要が無い)。

複数文字を囲った場合、ビッグエンディアンで 4 バイトの値が得られる。例えば、'(.&F' は (((40*256)+46)*256+38)*256+70 = 674113094 となる。

 

文字定数はコードを縮めるには確かに強力だが、'', が何回も出てきて長い。そこで役立つのが、文字列リテラルである。文字列リテラルが持つ値は文字列の先頭のアドレスなので、これを int* 型のポインタ変数に代入すれば、int[] 型の配列と同様の使い方ができる。

int 型の値は、リトルエンディアンで 4 バイトで表されるので、例えば、((int*)"****F&.(****")[1] は 70+256*(38+256*(46+256*40)) = 674113094 となる。

これで 144B まで縮んだが、文字列リテラルの中の \r がウザい(例えばタブは \t という表現を使わずに直に書けるのに対して、\r\n はそういうことができない)ので、166666668 毎に区切っていたものを 166666669 毎に区切るようにして、\r が不要な値を使うようにして 143B

 

繰り返す回数を表すのに使っていた変数 i が必要なかったのでそれを削って 136B

s の初期化は文字定数を使った方が短くて 135B

文字定数を直に使えばそもそも const m,s は必要なかったので 132B

n<mm は文字定数を使うよりも 1e9+7 の方が短くて 131B

xlong 型である必要が無かったので、long ni を削った時に空いた main 第 1 引数に入れて 130B

*a="\x01\x00\x00\x00M\xfb#\x07O\x0f\xed9`\x1d\xe17\xa6\xcbp%?y\x8d\x0e";
x;main(long n){
    scanf("%ld",&n);
    for(n<1e9+7?x=a[n/'\x09\xef!\xad']:0;n%'\x09\xef!\xad';)
        x=x*n--%';\x9a\xca\x07';
    printf("%d",x);
}

赤で示したものは実際には十六進数で表された文字コードの文字そのものであり、コピペでは正しく動かない。例えば \xed99 がエスケープシーケンスの一部と誤解され、\xd9 のような扱いになるからである。

 

この記事の公開後、lpha_z さんが 129B で AC した。