Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ICFPC 答え合わせ

早速,解法について書かれていたので参照させて頂きました。

ありゃ?ゲートの解析までは全く同じ考え方のようです。

ゲートはカルノー図で表される(ステートレス)であろうと想定し,入力と出力の組み合わせが分かっているので,カルノー図の全通りで探索すれば良いと「3^9=19683(片ピンのカルノー図パターン数)の二乗(L,Rピンの組み合わせ)×3(ループ接続したピンの初期値:0/1/2)」で探索をかけたのですが・・・解が見つかりませんでした。上の記事によればカルノー図でいけそうですね???

どうやらcircuit構文の解釈に間違いがあった・・・ようですが,まだよく分かっていません。なにせ,同じ入力シーケンスでありながら異なる出力値が出るという結果を得てしまっていましたので。もう少し,色々な方の記事をウォッチしてみます。

結局,ゲート解析の結論として「ゲートは何かレジスタを持ったステートマシンだ」という方向に走ってしまいました。これが敗因のようです。いま冷静に考えると,ここまで問題を難しくされることももないのかなぁとも思います。


7/7追記

どうやら,circuit構文の'X'の解釈を完全に間違えていたようです。
'X'表記のゲートは「a special "external" gate」だと誤解してました・・・。「'X'はspecial gateの接続点を示す」が正解だったようです。 この解釈でゲート解析を実行したら無事にカルノー図を得られました。

しかし・・・key circuitの例を見れば,自分の間違いに気づいてもよさそうですが。そのときは,'X'はNCを示すと思い込んでしまっていました。

このため,直列に接続したと思い込んでいた回路は実際にはフィードバックを含む回路となっていて,先の記述の通り「同じ入力シーケンスでありながら 異なる出力値が出る」という事態を起こしていました。

スポンサーサイト

ICFPC 2010

今年のICFPコンテストは,まったく良いところなく終わってしまいました・・・

言い訳じみれば,昼間は息子からの“かまって”攻撃(キーボードへのアタック)が頻繁に繰り返され,土曜と月曜は我が家の新築プロジェクトで急遽時間を取られてしまった等々・・・ICFPに割ける時間が少なかったかと。去年は完全にフリーな3日間を確保できましたが,そんなことは滅多にあることではなく。

まぁ実際のところは,時間があったとしても今年の問題は解けなかったようにも思います。初めのステップであるCircuitの構文を理解するのにはエラく時間がかかってしまいましたし(気付けば,どうということもないものでしたが),次のステップの鍵に至っては難しさに心が折れました・・・

なんとなく薄々と,たくさんのCircuitをWebサーバに投げてレスポンスを見るゲーなのかと思い始めるにつれ,簡易にHTTPを投げる環境がないことから,段々とモチベーションが下がっていったという感じでした。何かscript言語を一つはマスターしようとRubyの本を買ってはいたのですが,今のところ手付かずで・・・

なにか思いもよらない解法があるのか,他の人の解法を見るのが楽しみです。

しかし・・・ここのところプログラムコンテスト関係は絶不調です。Google Code JamはRound1でNG,TCOはSRM,Marathonともに初戦落ち・・・もう少しこっち方面に時間を取りたいところですが,しばらく難しそうです。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。