今日も今日とて、一番得意な？言語であるschemeで、ちょくちょくAtCoderの問題を解いています。
さて、今回はタイトルの通り、AtCoderのシステム内でなんとかschemeをコンパイルして使う、ということについてです。
それをやろうと思ったきっかけはこの問題。
AtCoder Beginner Contest #06 B問題 トリボナッチ数列
この回は確か、初めてBeginner Contestで時間内に3問解けた回です。嬉しい。
ただ、このB問題は、1つ目のコードを提出した時にTLE(=制限時間(=2sec)オーバー)になっていました。
そのコードは以下のものです。
(define nn (read)) (define (trib an ann annn count limit) (cond ((< limit 3) 0) ((= limit count) an) (else (trib (modulo (+ an ann annn) 10007) an ann (+ count 1) limit)))) (define answer (trib 1 0 0 3 nn)) (display answer) (newline)
tribという関数は、引数として、an、ann、annn、count、limitを持っています。
それぞれ順に、a_(n)、a_(n-1)、a_(n-2)、n、目標を表しています。
多分、この問題をschemeで解こうとするには割と妥当なコードだと思うのですが・・・
これがTLEとなってので、かなり焦りました。まだ経験の少ない僕にとって、絶対解けると思っていたものがTLEになると焦るものです。
そして、この問題で与えられるnのサイズが最大で1000000であることから、何回も呼び出される関数tribのどっかの手間をなくしたらいいのかな、と思いました。
というわけで、少し改善した結果がこちら。
(define nn (read)) (define (trib an ann annn count limit) (cond ((= limit count) an) (else (trib (modulo (+ an ann annn) 10007) an ann (+ count 1) limit)))) (define answer (if (< nn 3) 0 (trib 1 0 0 3 nn))) (display answer) (newline)
初めに提出したものだと、tribの引数limitが3より小さいかどうかを毎回判定していますが、これはかなり無駄なことなので、それを省きました。
その代わり、答えを表すanswerというものを求めるときに、その条件分岐が入っています。
このコードを提出すると、ACとなりました。よかったよかった。
しかし、このコードで通ったものの、かかった時間は1947ms。制限が2sec(=2000ms)なので、ギリギリなんてもんじゃないです。
このコンテストが終わってからも、ずっと気になっていました。これってなんとかならないのかと。
AtCoderのルールではschemeコードはコンパイルなしで使われるんです。仕方ないですかね。連絡してお願いしてみたいですが、なかなかschemeユーザーもいないので、無理かなぁ・・・
そして、じゃあコンパイルをなんとかやるプログラムを作ろう、となったわけです。
MIT/GNUschemeのドキュメントには、"cf"というコンパイルの関数があるとのこと。
よく分からないけど、やってみよう、ということで、色々試しまくりました。
ルール内にある、AtCoderシステムに対する攻撃、になっていないとは思うのですが、もし何か分かる方がいれば連絡を頂けると嬉しいです・・・。
さて、方針は次のようなものです。
1,まず、向こうのサーバで、新しい .scm ファイルを作る。
2,そこに、コンパイルして使いたい関数を書き込む。
3,それを "cf"コマンドでコンパイルし、"load"で読み込み、使う。
1でファイルを作るには、まず
(define port (open-output-file "func.scm"))
とします。これで、("func.scm"というファイルがないので)新しく"func.scm"というファイルが作られ、変数portにそれへの出力用ポートが入ります。
そして、S式を書き込むには以下のようにすればOKです。
(display '(ここに定義とか) port)
'をつけましょう。
そして、
(close-output-port port)
で、ポートを閉じます。
最後にコンパイルとコンパイルしたものを読み込むには
(cf "func") (load "func")
でOKです。".scm"は不要です。
そして、出来たコードがコチラ。
(define nn (read)) (define port (open-output-file "func.scm")) (display '(define (trib an ann annn count limit) (cond ((= limit count) an) (else (trib (modulo (+ an ann annn) 10007) an ann (+ count 1) limit)))) port) (close-output-port port) (cf "func") (load "func") (define answer (if (< nn 3) 0 (trib 1 0 0 3 nn))) (display answer) (newline)
さて、このコードを"compile.scm"という名前で保存し、手元のターミナルで確認。
MIT/GNU schemeを起動してやってみると・・・
*************-no-MacBook-Air:scheme_study **********$ scheme MIT/GNU Scheme running under MacOSX Type `^C' (control-C) followed by `H' to obtain information about interrupts. Copyright (C) 2011 Massachusetts Institute of Technology This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Image saved on Wednesday May 21, 2014 at 12:46:49 PM Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118 Edwin 3.116 1 ]=> (load "compile.scm") ;Loading "compile.scm"...100000 ; Generating SCode for file: "func.scm" => "func.bin"... done ; Compiling file: "func.bin" => "func.c"... ; clang -DHAVE_CONFIG_H -DMIT_SCHEME -I/usr/local/include -O3 -Wall -Wundef -Wpointer-arith -Winline -Wstrict-prototypes -Wnested-externs -Wredundant-decls -Wextra -Wno-sign-compare -Wno-unused-parameter -Wold-style-definition -isysroot //Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.9.sdk -fconstant-cfstrings -DSIGNAL_HANDLERS_CAN_USE_SCHEME_STACK -frounding-math -DENABLE_LIARC_FILE_INIT -I/usr/local/Cellar/mit-scheme/9.1.1/lib/mit-scheme-c/include -o /Users/fujiiryousuke/Desktop/scheme_study/func.o -c /Users/fujiiryousuke/Desktop/scheme_study/func.c ; clang -isysroot //Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.9.sdk -fconstant-cfstrings -DSIGNAL_HANDLERS_CAN_USE_SCHEME_STACK -Wl,-syslibroot,//Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.9.sdk -framework CoreFoundation -bundle -bundle_loader /usr/local/Cellar/mit-scheme/9.1.1/bin/mit-scheme-c -o /Users/fujiiryousuke/Desktop/scheme_study/func.so /Users/fujiiryousuke/Desktop/scheme_study/func.o ; ... done ; Loading "func.so"... done 7927 ;... done ;Unspecified return value 1 ]=>
トリボナッチの100000番目(を10007で割った数)、7927が求められました！
おぉ！すごい！
ということで提出。
しかし、WA・・・なんやねん・・・
サンプルの全てがWAでした。
ここで絶望しましたが、なんとか考えて、無駄な書き込みがあるのでは、となりました。
関数を別のファイルに書き込んで、"cf"でコンパイルせずに"load"で読み込んで使う、というプログラムを書いて提出してみたところ(つまり、上のプログラムの
(cf "func")
を取り除いたもの)、それはACとなりました。
ってことは、コンパイルするときに出るメッセージがダメなんだな・・・へっへっへ・・・ということで、なんとか防ぐ方法を考えました。
んで、またドキュメントを色々読んで、見つけました！
set-notification-output-port!
というやつを使えばよい！
これの引数としてportを与えると、警告メッセージとかがそっちに出るようになります。
だから、"cf"を使う前でこれをして、使い終わったらそのportを閉じればいいですね。
そして、書いてみたコードがコチラ。"output.txt"というファイルを作って、コンパイルメッセージはそっちに出すようにしました。
(define nn (read)) (define port (open-output-file "func.scm")) (display '(define (trib an ann annn count limit) (cond ((= limit count) an) (else (trib (modulo (+ an ann annn) 10007) an ann (+ count 1) limit)))) port) (newline port) (close-output-port port) (define port2 (open-output-file "output.txt")) (set-notification-output-port! port2) ;(load "func.scm") (cf "func.scm") (load "func") (close-output-port port2) (define answer (if (< nn 3) 0 (trib 1 0 0 3 nn))) (display answer) (newline)
そして提出すると・・・AC!!
ついに！やったぞ！
そして、時間は526ms！コンパイルなしだと同じコードで1947msだったことを考えると、大分な進歩です。
あー、頑張ってよかった。
前の記事のやつに至っては、コンパイルして初めてACとなるようなものだったので、これからもこのテクニックは使っていこうと思います。ただ、AtCoderというシステムがどうやって動いているのかは分かりませんが、何かしら迷惑をかけてしまっていないかだけが心配です。何せファイルを新しく2個作っているわけですから・・・
というわけで、AtCoderシステムにてschemeコードをコンパイルする方法でした。
今回は以上です。
