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を送るくらいが精一杯かなぁ…
ゲートの動作でつまづいて時間を食い過ぎた…

2009年10月29日木曜日

東大助教 アニリール・セルカン氏の件が凄いことになっている

よいしょ。そろそろここで書きますか。

楽天研究開発シンポジウム2008ではまつもとゆきひろ氏と並んで基調講演をするなど,精力的な講演活動を行っている,宇宙エレベーターの考案者・宇宙物理学者・元宇宙飛行士候補・スキー金メダリストという信じられない肩書を持った東大助教のアニリール・セルカン氏という人物がいるそうです。

ところが,2ちゃんねるの理系全般板で業績の一つのPRLを起点にして,その経歴・業績のほとんどに対して虚偽や捏造,剽窃・盗用などの疑いが提示されています(まとめWiki, まとめBlog, 英語Blog)。

そして先日,2スレ781(お知らせブログ)のコテハンを使っていた人が,その調査結果をまとめて東京大学競争的資金の不正利用窓口に通報したとのこと(/.Jへのタレコミ記事)です。


ということで,サマーウォーズの栄おばあちゃんの言葉「落ち着いて,一つ一つ自分にできる,自分にしかできない」ことをやっていこうと思って,tineye検索の自動化ツールを提供しました。まだあまり有効に活用できていないですけど。

まだまだ全貌のはっきりしない事件ですが,東大が対処することはもちろん,それ以外の各方面でも変化が起きるのではないでしょうか。

2009年10月20日火曜日

サマーウォーズの世界の「電話」

どこぞに向けて。黒電話は電話線から供給される電源があります。

あそこまでインフラをOZに独占されている世界であれば,電話交換網も既にOZにおきかえられているのでしょう。携帯で電話するにもアカウントが必要なのですから。

・・・小説版で栄おばあちゃんがメールしてたのは,黒電話で入力したのだろうか・・・音声入力?


あと,ちょっと別のことやってるのでサマーウォーズ関連のエントリ作成が滞っております。
しばらくお待ちください。