Entries

スポンサーサイト (この記事を編集する[管理者用])

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

昔,どこかで見かけた問題. (この記事を編集する[管理者用])

2組の鉄砲隊 (鉄砲隊A,鉄砲隊B) が勝負をします.
少なくても一方の鉄砲隊が全滅するまで勝負は続けられ,
 生き残りのいる鉄砲隊が勝利,または
 両方全滅したら引き分け
とします.

各ターン,全ての鉄砲隊の隊員は同時に,敵鉄砲隊に向かって,鉄砲を発射します.
自分の鉄砲隊に当たった鉄砲の数だけ,自分の鉄砲隊の人数が減ります.(鉄砲隊の人数はマイナスにはなりません)
鉄砲隊Aは最初100人いて,各隊員の命中率は1%です.
鉄砲隊Bは最初10人いて,各隊員の命中率は100%です.

鉄砲隊Aが勝つ確率と,鉄砲隊Bの勝つ確率はどちらが大きいでしょうか?

DPの良い練習問題かも知れません.
直感的に自明なら,それが答えでも良いと思います.(勿論,答えがそうなることは直感的に説明できるはずです)

twitter (この記事を編集する[管理者用])

なんとなくtwitterのアカウント取ってみた.
http://twitter.com/laycrs
使い方とかが全然わかってないけど,そのうち分かるといいな的なノリでのんびりと.

ぼやき (この記事を編集する[管理者用])

TopCoderニコ生Open 第1回のタイムシフト見たけど,やっぱり診断人先生とchokudai先生はエンターティナーだなぁと思った.

chokudai先生の連載の動的計画法・メモ化再帰チェックシートの1問目と3問目は実際プログラミングコンテストで出題されると,

1000兆円以下の金額が与えられる。日本の硬貨/紙幣で支払いをする時、支払う合計枚数の最小値を出力しなさい
コインを100万枚投げたとき、表になっている枚数が49.8万枚以下である確率を求めなさい

とかになったりするんだろうなぁ,とか思ってしまった.

公式Vアレンジ (この記事を編集する[管理者用])

Atlach=nacha~Going on~の公式ボーカルアレンジきた.
月イチペースらしい.これは期待せざる終えない.

トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター (この記事を編集する[管理者用])

という名前の,chokudai先生の連載の最新記事. 二分探索の話.
最後の方に,二分探索の終了条件を書くときに while(high-low<1e-9) と書くと丸め誤差のせいで止まらないことがあるから,定数回回しなさい的なことがやんわり書いてあります.
これを押しつけるのは危険な考え方かな―という気がします.
まぁ,そもそもchokudai先生本人は,超頭柔らかで,定数回ループじゃない方が良い場合は,さくっとそっちで書いちゃう気がするのですが,読者はどうだろうか,ということで.
というか,そもそも,chokudai先生は,定数回ループじゃないとダメ的なことは考えてないと思うのですが,文章はそう言ってるようにも見えるという意味で.

そもそも,TopCoderで要求される精度は,絶対誤差が10^-9以下または相対誤差が10^-9以下.
while(high-low<1e-9) が悪いのは,丸め誤差が悪いんじゃなくて,絶対誤差しか考えていないこと.
相対誤差も考えて, while(high-low<1e-9 && high-low<1e-9*max(abs(high),abs(low))) と書けば良いし,定数回のループを回すよりはこっちの方が自然だと思うわけで.

ただし,TopCoderはあくまで競技プログラミングであって,実行時間が制限時間内に終わるならば,より簡潔でより悩みどころの少ないアルゴリズムを書くべきだと思います.
そういう意味では,定数回ループが正解ですね.
取り敢えず,定数回ループとかぬるいこと言ってるとTime Limit Exceededになる可能性のある問題として,LiveArchive 4412 - The Great Gameを紹介してみます.単純な二分探索の問題ではないですが.
(LiveArchiveって最近サーバ速くなった? そうだったら普通に通りそうな気もする)

まぁ,そもそも自分はプログラミング的な思想とか基本的にはわからないのですが,こういう風に思いましたってことで.

TopCoderで解いた問題の記事を書こう (この記事を編集する[管理者用])

OnlineJudgeの問題とか,TopCoderの問題とか解いたらログ残そうって宣言してたはずなんだけど,全然TopCoderの問題解いてもログ残してないことに気づいた.
これではいかんので,ちゃんと書こう….

OnlineJudgeの問題は,自分のブログに載せたコードがそのままコピペされてAcceptもらってるのを見て,これはどうなのかな?と思ったので,最近はコードは載せなくなった.
後,考えると面白い問題とか,日本語で説明するのが難しい問題とかはヒント程度しか書いてない.
ので,TopCoderの問題は,ちゃんとコード書いて載せようと思う.説明もできれば詳しめに.(死亡フラグですが…)

ちなみに,左のリンクのOnlineJudge記事まとめ (競技プログラミング系記事まとめに名前変えた)とか,全然更新してなかったので,少しだけ更新した.
取り敢えず,去年書いた記事は全部リストアップ完了.

本日メッセでつぶやいた一言 (この記事を編集する[管理者用])

エウシュリーとTriangleはもっと主題歌に気を使うべきだと思うんだ!

M-1グランプリ 2009 (この記事を編集する[管理者用])

パンクブーブーおめでとう.
確かに,今回が決勝初めてなのが不思議だよなぁ.
少なくても,去年の敗者復活は電気カミソリのクレームのネタで面白い奴だったと思うし.
今年の決勝のネタは,1個目は隣人騒音クレーム,2つ目は陶芸家の弟子で,両方ともある程度は知ってるやつだったんだけど,面白くなってた.

New TopCoder eXchange (この記事を編集する[管理者用])

僕は現状(でも),実力より遥か上のratingが付いている思うので,僕を買うと損すると思うんだ…

TopCoder (この記事を編集する[管理者用])

今日の午前2時からのSRM454は初めて日本人の参加者数が3桁だったっぽい.(otinn.com)
126人.過去の最高記録はSRM452の98人.
chokudai先生の連載の効果かなー?

みるくくるみメドレー / Rirykaメドレー (この記事を編集する[管理者用])

ちょい古い動画だけど,みるくくるみメドレー(sm2235768)とRirykaメドレー(sm2247950, 2008年01月分まで).
風の継承者の虹の向こうって,くるみさんだったのか….今聞けば明らかにRirykaさんだけど当時気づいてなかった.
みるくくるみ時代は曲調幅広いけど,名前変わってから格好良い曲一筋なのがよくわかる(Still youが浮いて聞こえるし,まぁ年代的にも浮いてるが).
みるくくるみ時代も,後半になるに従って格好良い曲増えてくるなぁ….
最初に聞いた曲が,Rock On Youだったこともあって,電波系な曲もまた歌ってほしいなぁとか願ってみる.
まぁ,声が格好良いので,格好良い曲を歌うのは大歓迎.Rirykaさん格好良い歌詞も書くし….

流石に知らない曲は殆どなかったけど,夏神のみだれ髪を知らなかった,不覚過ぎる.
これかなり良い感じだぞ.
音遣い的に一瞬Elements Gardenっぽく聞こえたけど,そんなことはなくて,Angel Noteだった.ってか,不知火さんGJ.
Angel Noteの曲の提供先が微妙にマイナーなのが多くて困る….

Rirykaさんがアニソン歌ったのって,たぶん,GIRLSブラボーと,Venus Versus Virusだけだよね….
前者はAngel Noteで後者はElements Garden.
また,歌ってくれれば良いのに.てか,Angel Noteもっとアニメに曲提供すれば良いのに….
VVVのOPはとても直球な曲で凄い好きです.

色褪せた旋律がねぇぞー,と思ったら,2008年03月発売だった….

電気式華憐音楽集団 (この記事を編集する[管理者用])

デンカレ,Princess Party (無印)の挿入歌も歌ってたことを今更知る.
OPのIOSYSの印象が強かったからなぁ….
デンカレ,こんな曲もいけるのかー,結構幅広いよね.
ってことで,今日のTCのBGMはデンカレメドレー(sm7572554)で.
でも,やっぱりデンカレはブサイクが良く似合う….

11eyes (この記事を編集する[管理者用])

アニメ11eyesのOP/EDはゲーム(PC)と同じメンツ.shortしか聞いてないけど.

OPはTatsh,彩音.
これはゲームOPの方が好きだったかなー.
てか,十分良い感じだと思うんだけど,ゲームOPが良すぎた.

EDはAsriel.
こっちは格好良いなー.良い感じだなー.ゲームEDも良かったけど.
相変わらずAsrielはいい仕事する….

片霧烈火 / fripSide / Riryka (この記事を編集する[管理者用])

2009-08-20 Thu 18:30の記事で触れたけど,Aliceの新作のOPはやっぱり烈火さんだった.
Full聞いてみたけど,2番終わりから間奏への移り方が多少強引な気が….
間奏後,サビを単純に繰り返すだけじゃなくて,捻りまくるのはShadeさんっぽい.良い感じ.
Shadeさん×烈火さんだと,烈火さんにしては,全体的に音が高い曲になるのかなー.
関係ないけど,DJ C++さんの音遣いとか時々Shadeさんっぽくてドキっとする.
でも,Shadeさんの方が断然格好良いよなぁ…,まぁ,比べる相手が悪すぎる.

アニメの真・恋姫無双はfripSideがnaoさん抜けちゃったのでOPとかどうなるのかと思ってたら,烈火さんが歌うのね.
ゲームと同じくってことか.でも,たくまるさんじゃない!
格好良いけど,ちょいとインパクトが薄いかな.

で,fripSideは新ボーカル決まってたのね.
南条愛乃さん….名前は見たことある気がするけど誰だっけ?って感じでした.(ごめんなさい)
fripSideは,とある科学の超電磁砲のOPを歌ってるみたい.
正直naoさんの方が良かった気もするけど,これはこれで有りだと思った.
歌い方の違いもあるのかもしれないけど,いつものfripSideの曲に比べて音域が狭い気がした.
fripSideの曲は音域が広いのが特徴の1つだと思うので,そういう曲も聴いてみたい.
後,NAO project!が好きだったんだけど,そういうのもこれから作るのかな…?
(それとRitaさんはもう歌わないのかな…? 音が低くて(というか1オクターブ落として歌ってて?)少し歌いにくそうな感じだったけども…)

みるくくるみ時代の曲だけど,RirykaさんのIn the DarkのFull聞いた.
相変わらず格好良いよなぁ.

最強最速アルゴリズマー養成講座 第3回 (この記事を編集する[管理者用])

chokudai先生の連載3回目.
[ Link ]

相変わらず面白い問題を選んでくる.
初見で,1ページ目の問題はほぼ一瞬で答えはわかったのだけど,フラクタルの問題は答え見るまで全く気付かなかった問題.

1ページ目の問題のヒントとしては,問題文では人間とモンスター分けてごちゃごちゃ書いてますが,人間とモンスターは全く区別する必要がないということ.
後は,最終的にどういう状態に収束しうるかを考えれば….
とまぁ,僕はそんな感じに考えて解いた問題でした.

次回からは典型アルゴリズムの解説になるっぽいですが

これはDPですー、でおしまいの問題を貼り付けても何にも面白くないよね

ってことなので期待してます.

金田一少年の事件簿 (この記事を編集する[管理者用])

金田一少年の事件簿のCase 5 露西亜人形殺人事件で,有頭の部屋の壁に書いてある,角度によって見えたり見えなかったりする文字列.

+2BYGQYLLM
-3VDWXMLQKD
-1GVLBOPVIBOABJ
+3EFKQLEX
-2MQPQMCKPK
+1ZQH

典型的なやつですぐ読めるけど読んでなかった.
ヒントが書かれていたのね.漠然としすぎているけども….

THE BMS OF FIGHTERS 2009 -revolutionary battles- (この記事を編集する[管理者用])

今年ももうこんな季節になったらしいです.
全部固めてtorrentにしてくれるとダウンロード楽だなぁ.
取り敢えず落としたので,1年(以上)かけてのんびり楽しもう.

Another HTML-lint gateway (この記事を編集する[管理者用])

Another HTML-lint gatewayでこのブログのトップページを採点するとマイナス90点ぐらいという悲惨な結果になった….
これからは少しは気をつけていこうかな….

片霧烈火 (この記事を編集する[管理者用])

hyon先生のtwitterで見つけたけど片霧烈火のワールドイズマイン(ニコニコ動画)
かわいかっこいい.
烈火さん,CLOSED/UNDERGROUNDとして歌ってるときは,一段と荒く,弾けてて,聴いてて楽しい.
つうか,これ,動画,神藝工房コンビだ.なつかしい(?)

Aliceの新作のデモムービー公開されてたけど,今回もOPがとても烈火さんっぽかった.(確証はない)
Shadeさんの編曲はぱすちゃOPみたいなポップ系.
そのせいで薄められてる気がするけど,地味にメロディが格好良かった.
ボーカルはこっちはちゃんと纏めてきてるけど,地味に声色を使い分けてて,心地よく格好良く,といった感じ.

悦楽カメリア (この記事を編集する[管理者用])

とても直球な曲調なんだけど,純粋に恰好良くてテンションあがる.
プログラミングコンテスト用BGMに良い感じ.

Waterlooとかの問題概要と解法(?)書いたけど,今投下するとimosコンテストとSRMが流れるので金曜ぐらいにまとめて投下する予定.
SRMについては書いたら投下するつもりだけど.

メモを残す方向 (この記事を編集する[管理者用])

Online Judgeで問題解いても昔解いた問題とか覚えてないので, 取り敢えず解いた問題の概要と解法を,できるだけ全部,ログを残しておこうと考えてみる.
できれば,難易度は問わないので,1日平均1問位解きたいなぁ.書くときはまとめて書くと思うけれども.

いつ頃飽きるだろうか….

fripSide (この記事を編集する[管理者用])

全然知らなかったんだけど,いつのまにかnaoさんがfripSide卒業していた….
なんかRitaさんが歌ってるなぁとか思ったのはそういうことかー.

音域が広い曲を高い声で歌うnaoさんの声,地味に好きだったりしたんだけどなぁ….

続UVa (この記事を編集する[管理者用])

サイト自体はIEで見れるようになったんだけど,問題文中の絵がFirefoxじゃないと表示されないのでダメダメだった…orz
Marriage Ceremony Contestは普段UVaでは見かけない超強い人たちが見えたけどKMCに去っていったみたいでした.

オクターブ高く (この記事を編集する[管理者用])

EDかわいいよED (*ノノ
みょんみょん

UVa (この記事を編集する[管理者用])

いつのまにかUVa Online Judgeがサーバー移転してる.
Firefoxじゃないと見れなかったのがIEでも見れるようになった.わいー.

しかし,どこぞやでPKUのグラフが描かれるようになってからPKUばっかりだけども.

2009-05-13 20:00追記
IEで見れるようになったのはIE 7からIE 8にバージョンアップしたのが原因でした.

今更だけども (この記事を編集する[管理者用])

Studio e.goどうなるんだろう.
というか,キャッスルファンタジアの新作はー?

OnlineJudge記事まとめ (この記事を編集する[管理者用])

OnlineJudge記事まとめを作ってみた.
http://rsujskf.blog32.fc2.com/blog-entry-174.html

ケアレスミス (この記事を編集する[管理者用])

2週間ぐらい前からコーディングの時,ケアレスミスをやらかすことがやたらと多い.
半年前ぐらいからはケアレスミスなんて殆どしなくなったんだけどなぁ….
一行書く場所を間違えてTopCoderで840点失うとか凹むので何とかしたい….

#include<math.h> (この記事を編集する[管理者用])

面白い現象で嵌ったのでメモしておく.
KMCoder SRM67 950pt問題 [ Link ] でWAもらっていたのだけど,
#include<math.h>
を書き足しただけでACをもらえた.

コンパイラ#include<math.h>を書いたか結果
C書いたAccept
GCC書いたAccept
C書かないWrong Answer
GCC書かないAccept

多分,ceilやfloorが変な動作したんだろうなぁ….
とりあえず,これからはちゃんと#include<math.h>を書くようにしよう….

ACM/ICPC Japan(Aizu) 2008 (この記事を編集する[管理者用])

の問題セットがLiveArchiveに追加された.
[ Link ]

G問題(Search of Concatenated Strings)がようやく通ったー.
残りの問題は暇なときにまたやろうっと.

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。