2014年6月25日水曜日

まさか「しりとり 論文」でぐぐって自分の名前がすぐに出るとは思っていなかった

2014年4月28日月曜日

echo off

ふと、cmd.exeで「off」と表示させるにはどうしたら良いのか気になってあれこれ調べた。
まずは、普通の使い方

C:\>echo off

 とやるとechoが切り替わる。
MSDN(原文を見るべし)を見ると「空白行を出力するには"echo."とタイプすること」とある。これか

C:\>echo. off

とやると 「 off」と出力される。もう少しだ。

C:\>echo.off

望みの出力が得られた・・・って、どういう構文なんだこれ。

2014年3月21日金曜日

魔方陣

 リンクは貼りませんが、魔方陣の全列挙について、高校生がスパコンで解いたり、それを大人気なくPCベースで実行したりGPGPUやXeonPhiに移植したりしているそうですね。

 さて、ここでは0-1整数線形計画問題に落とし込んで、GLPKで解いてみましょう。全列挙じゃなくて解を一つでも見つけるというだけです。mahoujin.modです。コメント・空行を抜かすとたった20行で表示まで込みで書けました。こういう問題を定式化するにはGLPKのGNU MathProgは非常に強力ですね。実行すると8秒ほどで解が一つ表示されます。もうちょっと頑張って「既に見つけた解以外で」とやることもできるんですが、解の総数が回転・対称解を除いて2億7530万5224通り(Wikipediaより)あるとあって諦めモードです。

 先ほど、8秒と書きましたが、これは--minisatオプションを付けたときの時間です。オプションなし(分枝限定法で解く)と212秒ほどかかります。--minisatオプションは、目的関数が無い実行可能解の探索問題でかつ、0-1整数変数しかないときにしか使えません。しかし、このような問題は魔方陣、数独、ピクロスなどパズル系の問題の定式化に代表される割り当て問題の変形で多く見られます。minisat凄い。

  さて、これだけだと余り面白くないので少しは役に立つことを。
親子方陣というものがあるそうです(Wikipedia:魔方陣、ことバンク参考ページ)。5×5の魔方陣の内側の3×3が魔方陣として成立しているというものです。Wikipedia、参考ページなどによると中心格(要は真ん中)が(1~25の)中心値13のものが知られており、作成法も確立されているそうです。

  しかし、本当に中心格は13じゃないといけないのでしょうか? それ以外の親子魔方陣は無いのでしょうか? 証明はされていないんじゃないでしょうか(書籍までは手を出していないので未確認)。
 というわけで、解いてみました結果は存在しない、ですね。整数線形計画問題やSATではこういう存在しないことの証明も手軽なところが良いですね。

GitHubはじめました(今更)

http://github.com/kounoike/で始めました。まともに使うか分からないけど。

2011年1月3日月曜日

SPOJ SHORTEN

http://www.spoj.pl/SHORTEN/ をお試し中。といってもKAMILとSIZECONの2問解いただけ。
うーん。
  • CodeGolfのように出力が表示されないのがいらつく
  • KAMILみたいなんはまあまあ。題意をcoverしたinputが出題されているんだろうなあ,というのが推測でしかできないのでいらつく
  • 1行目がnumber of test casesで,余分なtest caseが入ってる入力があるとかいうのにいらつく
  • scoreがexcept symbols with ASCII code <= 32.ってなってるせいか上位陣が変態(多分それ系だよね?)
  • SLEXSORTなんてnumber of test casesで各テストケースに行数か。うっとうしい…
ということでイマイチ乗り気になれないので終了にしよう。shinhさんにSIZECON勝ったことだし。

2010年6月29日火曜日

ICFPC 2010 (2)

無駄にじっくり時間をかけた回路ゴルフが終わり,車と燃料の仕様をkuma-な方のとこをカンニングさせて頂,
ようやく本番に入ることができました。なるほどなるほど…

「素因数分解だ」って話が出てきたのも納得。非線形整数計画問題という話も。
さて,一応専門なわけだし,定式化頑張って線形に落としてみるかな…と考え中。見込みアリ。

しかし,http://wiki.freaks-unidos.net/weblogs/azul/icfp-2010のLogを使って線形化っていうのが話としては面白そうだなー。
でもソルバーは今時lp_solveはないよなー。

2010年6月21日月曜日

ICFPC 2010

どこぞでこっそりやってるぞということを宣言しているのですが,あまり時間が取れずfuelのtritsを送るくらいが精一杯かなぁ…
ゲートの動作でつまづいて時間を食い過ぎた…