つーさのくーかん

http://codegolf.stackexchange.com/questions/12664/implement-superoptimizer-for-addition

今Y個の0/1の2値のいずれかを取る変数x[0]...x[Y-1]がある。
こいつらの和がXになるかどうか を判定する論理式を作るプログラムを作る。
論理式には括弧 と and or not が利用できる。
論理式のスコアは、x[?]が評価された回数で定まる。

F(Y = 2, X = 1) := (x[0] & !x[1]) | (!x[0] & x[1]) ならば スコア は 4。

入力 Y,X に対して最もスコアが低くなるような論理式を生成して返すプログラムを書け。

おおみそかだよどらえもん

2013.01.01 本記事の取り消し線部分は誤り。追記を参照してください

今日はPCにまつわる時計の話。時計と言うよりはタイマの話。
時間が正確に測れないパソコンがある。
というか、僕のメインマシンであるデスクトップがそう。
(2013.01.01 訂正)PCの時計の進みが遅くなるという現象に遭遇したので記録しておく

症状は VSyncな60fpsゲームでFPSを表示させると61.8fpsと出るというもの。
オーバークロックによってベースクロックを103%にしているが、60*1.03=61.8 である。
音ゲーしててもBGMとキー音がずれる。
時計の進み方が遅い。考えたこともなかったが、それは本当か？

実際、DateTime.Now の値を画面に表示して手元の腕時計と比較してみると、
なんと1分に2秒ずつ遅れていくことに、今回初めて気がついた。
進みが遅い時計もひどいが、今まで気づかなかった自分もなかなかひどいなぁ……。
# このままだと、システム時計が1日48分遅れる計算になるが、それはさすがに気づくはずだし、
# 今まで気がつかなかったのは、裏で時刻がよしなに同期されてるんだろうなぁ。

(2013.01.01 追記ここから)

PCのベースクロックを変更した後、Windowsを"再起動"していなかったのが原因。
と、書くとあほかと思われるので事情も弁明しておく。

上で挙げた時計の進みが現実時間に合わなくなる問題は、
シャットダウン → 電源ON → クロック変更 → そのまま起動 した場合に発症し、
再起動 → クロック変更 → そのまま起動 すると 発症しないようだ。

追検証として、発症後の再起動も試してみた。
シャットダウン → 電源ON → クロック変更 → そのまま起動 → 発症 → 再起動 → 解消

そう、もうおわかりですね！
Windows8では高速スタートアップ機能が新しく搭載された。
「再起動」コマンドを選ばない限りはずっと休止状態のような状態になるのだ。
シャットダウンだけでは、Windowsは変更されたベースクロックに気づかないようだ。

ちなみに、筆者は(再インストールがめんどくさくて)Windows 8のRPを未だに使い続けているので、
もしかするとRTMではこの問題は起こらないかもしれない、起こるかもしれない。
ちょうど期限も切れるので、入れ替えてみて追検証をしたいと思う。

また、「クロックを上げたのに時計が遅くなっている」というのは完全に勘違い。
今回の症状は103%に設定していたクロックを一時的に100%に戻したことが原因。
正しくは「クロックを103→100に落としたから、進みが100/103に遅くなった」だった。
FPSが61.8になる理にかなっている。訂正してお詫びする。

(2013.01.01 追記ここまで)

チップセットの仕様なのかマザーの仕様なのかわからないが、
さしあたっての問題は、音楽ゲームを遊ぶときBGMとキー音がじゃんじゃかずれていくことである。
ドラムが120bpmで演奏してるのにギターが126bpmで進んでいけば、それはもちろん聴くに堪えない。

さて、どこかに正確な時計はないものかー

(2013.01.02 追記)解決したのでここより下は完全に冗長な情報になってしまった

続きを読む

煽り気味のタイトルつけたった

世の中便利になった。それはもう超便利。

ことに情報端末に関しては「スマートフォン」とか言うものがここまで一般化するなんて、
僕が初めて「スマートフォン」と呼ばれるものを５年前に手にした頃には想像もしていなかった。

スマートフォンの世界には超たくさん、超便利なアプリがいっぱいある。
それらをほいほい入れることに何のためらいもない子たちが増えてきたと思う。

彼らは、ソフトを作った人を信じすぎてると思う。
そこに、信じるという行為を行わなくてはいけないことにすら無自覚無頓着なのではないかと思う。
大人でも少ないかも知れない。こういう教育、必要なのでは？

僕が恐がりなだけだろうか。

続きを読む

何気なくツイッターに流れてきたURLをクリックしたとき、その先に書かれているものが意図せずしてプロコン的問題だった場合、瞬間、突然、強制的に、脳内のストップウォッチをスタートさせられてしまう。えっ　えっ。これは、恐怖以外の何物でもない……！

— ルバン・ガイバンサ・サーツさん (@ttsuki) 10月 13, 2012

というわけで。

テトロミノ認識〜 横へな 2012.10.6
http://nabetani.sakura.ne.jp/hena/ord4tetroid/

せっかく解いたし記事にしとけ的な。

10x10のグリッドスペースにぽつんとテトロミノ(かもしれないもの)が置かれるので、
それがなんであるか判定せよ！　という問題。

答案とテスト結果。 http://ideone.com/ws2SB

コード量たいしたことない割に40分とか掛かった。

ぱっと見スマートな実装方法が思いつかないので、
なんとか実装したろうという気概が試されそうな問題ですね。

実装方法は色々ある気がしますが、
左上に持ってってパターンマッチングしちゃうのが楽かなーと思って採用してみました。
左上に持ってくループと、パターンマッチングに文字列を使ってるところとかは横着。

コーディングの40分のうち20分は、パターンデータベース()の生成と確認に費やした気がする。
これを生成するのにもうちょっと楽で間違いにくい方法とか思いつければ良かったなぁ。
この手のデータベースはバグの温床になるわけで生成には細心の注意が必要なんですけど。

ネットだらだらしてたら辿り着いたのでやってみた、系。

makeplex salon：あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定
http://www.itmedia.co.jp/enterprise/articles/1004/03/news002.html

モニター最速40分だと、競技プログラマーの血がさわぐぜー！

というわけで、回答した。

続きを読む

スーパーテンパズル http://shindanmaker.com/198886

今回はこれを解いてみたくなったんだ。

さて、どうやって解くか……。

注意：プロコン系の話です。

続きを読む

参加した。14ptの1614位 泣いた。

Aは読むのが大変で、なんとか15分くらいかけて読み終わってDPすりゃ解けんのかなーと思ったけど、
いや、普通に一番遠くにたどってけば行けるかどうか判定できるのかって勘違いしてdijkstra書いた。
incorrectもらって、1分考えて反例に思い至って、多重化dijkstraに改造したら、当然ノード数爆発。
各つるで前に探索した時より遠くにreachできるなら続行みたいな改造したので、
Best First Searchじゃなくなっちゃった。largeの計算が終わらず……。辛抱して待つこと4分。
プロンプトに戻ってきた。提出。おお怖い怖い。通った。

Bが今までやったことないタイプの問題だった。
敷き詰める。5倍かー。結構広いんだなと思ったけど、コーナーケース考え出すとキリがない。
フィールドも広いからデータ構造作るのも大変だし。うー、どうしよう。
つーか、この広さなら貪欲でもたぶん大丈夫なんじゃねーの、自信ないけど。
3回出したがincorrectだった。smallだけでもほしい。N10ならモンテカルロで行けるんじゃね？
あと15分。今の貪欲をなんとか直すべきか、迷ったがデバッグの道を選択して、そのまま時間切れ。
一瞬脳裏をよぎった声に従って、乱択で行けばよかったのだが、SRM脳は乱数使う勇気がなかった。
ローカルで答えが合ってるかどうかわかるんだから、探索が終わるかおわんないかの運試し。
N<=10^3の方だってどっちにせよ運ゲーだった。
Aをもうちょっと早く解いて「この調子この調子」でBに取りかかれればまた違ったんだろう。

というか、こうやって振り返るとAもBも不正解じゃねーか。

Tシャツが欲しかった。可能性はあったと思う。つくづくTシャツには縁がないなぁ。

最近TopCoderのレーティングも立て続けに落としてるし、競技プログラミングがスランプ気味。
書くコードも汚くなった。僕のプログラマ人生はぼちぼち終わりかけてるのかもしれんとちょっと思う。

例によって、自宅サーバならぬ自宅NAS。
今回はASP.NETを動かそう。これが動くと、
Visual StudioとC#で簡単にWEBアプリが作れる。
そいつぁやばい。是非やってみようじゃないか。

続きを読む