Comments
Description
Transcript
mosa資料 - CORESERVER.JP
mosa
東大講義2011/ 06/04
榎本悠介(mosa)
1
• mosa
• 経歴
2007年
2007年
2008年
2009年
2010年
2011年
筑駒 卒業
東大理一 入学
駒場祭委員長
理学部物理学科(3年) 進学
工学部計数工学科(3年) 転学部 （おや･･･？）
工学部計数工学科(3年)
(え･･･)
• twitter:mosa_siru
• skype:mosa_siruo
東大講義2011/ 06/04
榎本悠介(mosa)
2
第一部
第ニ部
プログラミングの基礎が
どうやってプログラミン
わかれば、色々できる！
グに慣れるの？→TopCoder
• 作業の効率化
• プログラミングコンテ
スト
• 例：BOTの作成
• 簡単な問題でプログラ
• 武器：UWSC
ミングに慣れて、難し
• ちょっとした研究
い問題で楽しもう
• ポーカーにおけるラ
• 具体的な問題に挑戦し
ンダムウォーク
てみよう！
東大講義2011/ 06/04
榎本悠介(mosa)
3
(1)なぜプログラミングを学ぶのか？
(2)UWSCと活用例
(3)研究への活用例
東大講義2011/ 06/04
榎本悠介(mosa)
4
1.
(1)
• 面倒なことはパソコンに任せてしまおう！
人間味のない、ゕホらしい作業はやめよう！
例：データ入力 流しこみ 単調作業
• 少なくともPC上の問題は、ググれば大抵解決する。
あなたが悩んで先人が悩んでいないはずがない！
気合と根性はやめよう！
現実はそうもいかない。金や友人で解決しよう。
その素養(ベース)として、プログラミング(という概念)を
知っておくと便利！
東大講義2011/ 06/04
榎本悠介(mosa)
5
1.
(2)
• 道具があると、解決策が生まれる！
数学の問題を解く時に、道具なしではゕプローチが全然違う。
ベクトルや座標なしに幾何の問題を解くと考えれば…。
「7099011111111108107204503330990の9で割った余りは？」と聞い
て、「mod」という道具があるとないとでは雲泥の差。
• 道具があると、問題が生まれる！
道具がないと、日常に転がっている(解決できるはずの)
問題を見ても、問題とさえ認識しないかもしれない。
問題→道具→発想・解決→新たな問題発見→道具→・・・
が理想
何も疑問をもたずにこなすのではなく、「怠けたい」と思うべし！
きっとそこに問題は転がっているはず。
あなたが今している作業、見る人が見れば気合と根性なのかもしれ
ません。
東大講義2011/ 06/04
榎本悠介(mosa)
6
「怠けたい」と思って、ググると楽になった例。
• mosaが所属団体のパンフレット制作(企画情報表示)の現
場を見たところ…
せっかくウェブ上のフォームで情報を集めてデータベースにし
ているのに、わざわざ1つ1つIndesign(制作ツール)にコピペして
いる！
企画数は400以上、それぞれ入力欄は10個程度。ミスしないはず
がない。
校正も全ての欄をいちいちチェックしなければならない。
• ググったところ、やはり自動で流しこむ方法を発見。
東大講義2011/ 06/04
榎本悠介(mosa)
7
ポント：作業を楽にする道具を紹介！
2.UWSC
2-1.UWSCとは？
2-2.ドラクエのレベル上げBOT
2-3.ボンバーマンのオート動作
2-4.あるMMOの不正者対策対策
東大講義2011/ 06/04
榎本悠介(mosa)
8
2-1.UWSC
• 非常に多機能な作業効率化ツール。
毎日のメールチェックの自動化
ゲームBOTの作成
• windows上の操作を記録でき、簡単に再生できる。
• 簡単な独自言語で動き、複雑な操作も可能。ネット上に
例：if else文/for,while ループ/配列/関数 etc...
ラブラリも多数。
これと用意されている「色を取ってくる関数」「画像が一致
するか判定する関数」「マウス座標をとってくる関数」
「キーボードを押す関数」などを組み合わせる！→BOT作成
「専用の言語とか面倒くさい」←プログラミング言語は、１つ
さえ覚えてしまえば、2つ目以降はすんなり学ぶことができる。
東大講義2011/ 06/04
榎本悠介(mosa)
9
UWSC(
)
例：マウスの乗っている色と座標を表示する
While True
x = G_MOUSE_X; y = G_MOUSE_Y
c = PeekColor(x, y)
Fukidasi("赤="+r(c) +",緑="+g(c) + ",青="+b(c)+"座標：("+x+","+y+")"+, x, y, 3)
Sleep(0.5)
Wend
function r(c)
Result = c and $FF
fend
function g(c)
Result = (c and $FF00) / $100
fend
function b(c)
Result = (c and $FF0000) / $10000
fend
東大講義2011/ 06/04
榎本悠介(mosa)
10
2-2.
• 人間味ある、清く正しいゲームライフを！
• 例えばドラクエなら・・・
フゖールド：「く
指定座標の色を
ちぶえ」で敵を呼
とってきて、バト
ぶ
ルを認識
東大講義2011/ 06/04
メタルキングの銀
色を判別→「まじ
A連打。
んぎり」になるよ
うにする
榎本悠介(mosa)
11
2-3.
• 精密動作をBOTにやらせるとどうなるか？
東大講義2011/ 06/04
榎本悠介(mosa)
12
2-4.
MMO
• MMO：大規模オンランゲーム。FF11など。
• M君が、呑気にBOTを使っていたところ・・・新機能
が！ピンチ！！
「怪しい動きをしているプレヤーを見た場合、不正申告でき
る」機能。申告された側は、人間であることを120秒以内に
CAPTCHAで示さねばならない。
BOTが使えなくては
他の追随を許してしまう…
東大講義2011/ 06/04
榎本悠介(mosa)
13
• 正攻法なら・・・
画像解析 OCR(文字認識)やOpenCVで処理
しかし素人には厳しい。背景色と被ってくると絶望的。
そもそも画像のサンプル数が少ない。
→手で入力するしかなさそう。
• 「申告された」事をどう読み取るか？
画像判定しようにも、毎回の表示位置がランダムで難しい。
ンストールフォルダに、先ほどの画像が生成されることを発
見！
東大講義2011/ 06/04
榎本悠介(mosa)
14
フォルダ内のフゔル数を5秒
ごとにチェック
増えた場合：Beep音を鳴
らし続ける！
しかしニートといえども
外出はしたい・・・
東大講義2011/ 06/04
榎本悠介(mosa)
15
フォルダ内のフゔル数を5秒ごとに
チェック
増えた場合：画像を添付して携帯にメール。
受信フォルダ確認モード。新規メールにつ
いている●(未読マーク)を画像判定する
返信メールの内容をゲーム画面にコピペし、
「転送」を押す。
東大講義2011/ 06/04
榎本悠介(mosa)
16
ポント：プログラミングの基礎がわかれば、こ
んなことがわかっちゃう！
3.
(
)
3-1.ポーカーって？
3-2.実力測定のためのランダムウォーク
3-3.リスク分散研究のためのランダム
ウォーク
東大講義2011/ 06/04
榎本悠介(mosa)
17
3-1.
(1)
• テキサスホールデムは世界的に人気。
2011年度の世界大会は賞金総額145億円。
オンラン上で年間1億円以上稼ぐプロも。
• これはチャンス！とM君は意気揚々に乗り込んだ！
東大講義2011/ 06/04
榎本悠介(mosa)
18
3-1.
(2)
• ゲームの5回に4回は、何も賭けずにベタ降りのクソゲー。
• 多重窓が前提
→BOT化できないか？
• レートは倍々で増やしていける
実力さえあれば、指数的に増えていくのですぐに稼げる！
実力ってどう測るの？指標Rとかないけれど・・・
実力があるとして、どうすれば効率的に稼げるの？
東大講義2011/ 06/04
榎本悠介(mosa)
19
BOT
• 時間があれば紹介
• 画像認識→手札,場のカードなどを認識
UWSCでの画像認識では精度が悪いので、一度C++で白黒二値化
させた画像を認識させた。
技術的にはwindows hookなどでゕプリケーションから直接情報
を取るべき。
• 統計値により分岐
レズ率5%と30%の人では、同じレズでも観測されるハンド
の強さが全然違う！結果として対応も異なってくる。
いかにFISH(数学的な定石を知らない、明らかに参加しすぎな者)
から奪うか
東大講義2011/ 06/04
榎本悠介(mosa)
20
3-2.
今勝っているのは運で勝っているのか、
実力で勝っているのか？
もし実力と断言できるとしたら、安心してゲームを続け、持ち
金を増やすことができる。
今負けているのは運の範疇で説明できるだろうか？説明できな
いなら、今すぐポーカーをやめるか低レートの卓に戻るべきで
ある。
例：1$持参したゲームを10万試合行い、100$儲けることが
できた。
→勝率は50%を越えたと言えるか？
まだまだ「運の範疇」で説明できるか？
東大講義2011/ 06/04
榎本悠介(mosa)
21
上の赤線が結果分。5$のゲームなので、2万試合で
37回分多く勝ったことになる。
東大講義2011/ 06/04
榎本悠介(mosa)
22
p
x=1
確率p
p
1-p
x=0
確率1-p
1-p
x=-1
東大講義2011/ 06/04
榎本悠介(mosa)
23
• 勝率p=,….0.48,0.5,0.52 …-をいくつか用意し、
x=0でスタート。
確率pで＋1、1-pでー1と、ふらふら動くことを考える。
if(Math.random<=p){x++;}
else{x--;}
• ある程度の歩数tにおいて、xの終値の統計を取る。
歩幅は1でいいか？
小競り合いはあるが、基本戦術は全賭けによるダブルオゕナッシング
なので大丈夫。
何試合につき1歩か？
統計データを見るに、300試合ごとに全賭けしている
東大講義2011/ 06/04
榎本悠介(mosa)
24
t/p
0.44
0.46
0.48
0.50
0.52
0.54
0.56
σ
σ/√t
300
-35.96 -24.08 -11.93
-0.1
12.05
23.99
36.03
17.25
1.00
600
-72.01 -48.09 -24.03
0.03
24.05
47.96
71.94
24.42
1.00
-119.86 -60.05
-0.18
60.00
119.91 179.98
38.63
1.00
-359.8 -240.05 -120.04
0.06
120.06 239.76 359.86
54.61
1.00
1500
3000
-180
• 一見、σはt(歩数)N倍で√N倍に増えているように見える。
• しかしσ/t(＝ブレ密度)は単調減少。
tがN倍になると、√N倍で減少。どんどん収束する！
• さきほどの例なら、2万試合(t=600)で+37なので、期待勝
率は53%、片側2.3%の水準で勝率49%-57%が約束される。
東大講義2011/ 06/04
榎本悠介(mosa)
25
勝率と平均終値の関係
400
300
200
平均終値
100
10000
0
20000
0.4
0.5
0.6
-100
50000
100000
-200
-300
-400
勝率
完全に線形！
東大講義2011/ 06/04
榎本悠介(mosa)
26
3-3.
全財産が100$である時に、
100$を1度に賭けるべきか？
• 10$なら安全か？1$なら？
• 0.01＄である必要は？
運で破産せずに、
時間もかからない賭け方は？
東大講義2011/ 06/04
榎本悠介(mosa)
27
(1)
• 開始HPを設定して、「HPが一定以下になれば死亡」の
ランダムウォークと考えれば良い！5%を賭けるなら、
HPは20。
• 何回かランダムウォークさせて、生存確率を出せばよ
い。
東大講義2011/ 06/04
榎本悠介(mosa)
28
(2)
• 勝率pが与えられたとして、持ち金の何%を賭けるのが適
正だろうか？
運でレートダウン(持ち金半分)しない賭け方は？
その中で、早くレートゕップ(持ち金2倍)できる賭け方は？
(1)開始値(startHP)を..20,50,100,..などで設定
(2)歩数Tでランダムウォークを実行し、
HP＜startHP/2（t≦T）：死亡
HP＞startHP*2（t≦T)：生存(ダブルゕップ)
HP＞startHP/2（t=T）：生存
この時の死亡/生存/ダブルゕップ率は？
東大講義2011/ 06/04
榎本悠介(mosa)
29
T=600(2万試合)
T=1500(5万試合)
100
100
80
70
60
50
90
勝率45%生存
勝率45%ダブルゕップ
80
勝率45%ダブルゕ
勝率48%生存
70
勝率48%生存
勝率48%ダブルゕップ
60
勝率48%ダブルゕ
50
勝率50%生存
40
勝率50%ダブルゕ
30
勝率52%生存
20
勝率52%ダブルゕ
10
勝率55%生存
勝率50%生存
40
勝率50%ダブルゕップ
30
勝率52%生存
20
勝率52%ダブルゕップ
10
勝率55%生存
BR4%
BR3% BR2.5% BR2%
BR5%
BR1%
T=3000(10万試合)
100
90
勝率45%生存
80
勝率45%ダブルゕップ
70
勝率48%生存
60
勝率48%ダブルゕップ
50
勝率50%生存
40
勝率50%ダブルゕップ
30
勝率52%生存
20
勝率52%ダブルゕップ
10
勝率55%生存
BR4%
BR3% BR2.5% BR2%
BR1%
勝率55%ダブルゕ
BR4%
BR3% BR2.5% BR2%
BR1%
(1)p=0.5未満はカス
(2)p=0.55は強すぎて考察の余地なし
(3)p=0.52が運で死なないためには
勝率55%ダブルゕップ
東大講義2011/ 06/04
0
BR5%
0
勝率55%ダブルゕップ
0
BR5%
勝率45%生存
確率(%)
90
安定を求めるなら1%だが、5万試
合でもレートゕップ20%
2%も悪くない。10%強レートダウ
ンするが、5万試合でレートゕッ
プ70%
ていうか、手数料の3-4%ってク
榎本悠介(mosa)
ソでかくね？？→やーめた 30
(1)勝率55%は非常に強く(非現実的？)、あまりポートフォリオ考察
の必要がない
2万handでさえ、BR2.5%以上なら90%ダブルゕップする
(2)勝率50%のダブルゕップ率は33% レートダウンは67%に収束する
BR2倍で生存確定
BR0.5倍で死亡の定義上。(ごまかせるのは収束時間のみ)
(3)勝率48%は非常に弱い
ダブルゕップはBR5.0%でさえ10%程度 ほぼ不可能
2万hand：BR2.0%以上では70%以上レートダウン
10万hand：100%レートダウン
(4)勝率45%は論外
ダブルゕップは不可能、10万handで100%レートダウン
→勝率50%未満はバンクロール管理以前の問題。いつか死ぬ。
以上から、勝率52%をメインに見るべき。
安定を求めるなら1%だが、5万handでダブルゕップ20%
10%強レートダウンするが、5万handでダブルゕップ率70%を目指せる2%も
悪くない
東大講義2011/ 06/04
榎本悠介(mosa)
31
4.
• 時間があれば紹介
• 文章をメタ的に分析、変換
改行などの特殊文字も変換できる
東大講義2011/ 06/04
榎本悠介(mosa)
32
第一部
第ニ部
プログラミングの基礎が
どうやってプログラミン
わかれば、色々できる！
グに慣れるの？→TopCoder
• 作業の効率化
• プログラミングコンテ
スト
• 例：BOTの作成
• 簡単な問題でプログラ
• 武器：UWSC
ミングに慣れて、難し
• ちょっとした研究
い問題で楽しもう
• ポーカーにおけるラ
• 具体的な問題に挑戦し
ンダムウォーク
てみよう！
東大講義2011/ 06/04
榎本悠介(mosa)
33
1.TopCoderって？
2.問題例：如意棒
3.問題演習1：素数(1)
4.計算量
5.問題演習2：素数(2)
6.問題演習3：ant
34
1.TopCoder
1-1.プログラミングの学び方
1-2.TopCoder(ルール)
1-3.TopCoderの何がおすすめ？
東大講義2011/ 06/04
榎本悠介(mosa)
35
1-1.
(1)まず、本当に基本的なところを網羅する。
型 if文 and/or ループ 配列 関数あたり。
あとは必要に応じてググったり人に聞いたりする。
(2)受験勉強でもそうだったように、やはり演習＝自分で組
む ことが大切。
じゃあ何を作るか？目的があればいいけど・・・
本のサンプルコードを写してもつまらない・・。
→そこでおすすめなのが
勿論すでに何か作りたいものがあれば、それに向かって進めば
良い。授業で演習などをしてくれるなら儲け物。
東大講義2011/ 06/04
榎本悠介(mosa)
36
TopCoder(
)
色々な長さa[]の如意棒がN個与えられます。
それぞれを必要なだけ伸ばして、
全て同じ長さにしたいです。
合計でどれだけ伸ばす必要があるでしょう？
(1≦a<1000, 2≦N≦50)
SRM506 div2 easy
• 例： N=3,a={100,900,500} → 1200
C++/C#/JAVA/VB
で書いてください。
東大講義2011/ 06/04
榎本悠介(mosa)
800
100
900
400
500
37
1-2.TopCoder(
)
• プログラミングコンテスト
• 3問75分(easy,medium,hard)で問題を解く。
とはいえmediumが解ければ十分。
早く解けば解くほど点数が増える。
• 最後に「Challenge Phase」が15分あり、他の人のコードのエ
ラーを指摘する。
成功すると点数プラス、失敗するとマナス。
• 最後に全員の点数を比較して、レーテゖングが決められる。
• レーテゖングで自分の実力がわかる！
1200以上になると問題が難しくなる
DIV1 R1200～ (難しい) １軍。
DIV2 ～R1200 (簡単) ２軍。 ←mosaは今ココ
HNの「色」も変わる。赤(R2200-)は神。chokudaiは神。
東大講義2011/ 06/04
榎本悠介(mosa)
38
1-3.TopCoder
ポイント：楽しみながらプログラミングに慣れていける！
(1) 時間を競うので、コーデゖング速度があがる！
自然とキレなコードになる！
(2) ChallengePhase(他人のバグを探すフェズ)で、人のコードを
読むのにも慣れる！
自然と他言語のコードにも慣れる！
(3) スゴい人のコードを読んで、美しいソースコード・知らない
書き方に触れ放題！
同じ解法でも書き方を工夫している 整然としている
そもそも解法が全然違う！何これ！
(4)計算量の考え方がつき、ゕルゴリズムの勉強になる！(後述)
2秒以内に計算しないと0点。
東大講義2011/ 06/04
榎本悠介(mosa)
39
2.TopCoder(
)
色々な長さa[]の如意棒がN個与えられます。
それぞれを必要なだけ伸ばして、
全て同じ長さにしたいです。
合計でどれだけ伸ばす必要があるでしょう？
(1≦a<1000, 2≦N≦50)
SRM506 div2 easy
• 例： N=3,a={100,900,500} → 1200
C++/C#/JAVA/VB
で書いてください。
東大講義2011/ 06/04
榎本悠介(mosa)
800
100
900
400
500
40
(1)まずは全部の中から、最も長い如意棒を選ぶ。その長さ
をmaxとする。
(2)それぞれの棒について、maxからの差分を足していく。
東大講義2011/ 06/04
榎本悠介(mosa)
41
(VB)
Public Class SlimeXSlimeRancher2
Public Function train(a() As Integer) As Integer
Dim res As Integer=0 '結果
Dim l As Integer=a.Length ‘如意棒の数
Dim max As Integer= a(0) ‘最大値をいれたい！
Dim i As Integer
For i = 1 To l - 1
If max < a(i) Then
max = a(i) '最大値をいれていく
End If
Next
For i = 0 To l - 1
res = res + (max - a(i)) '最大値からの差分を足していく
Next
train = res ‘結果を返す
End Function
End Class
東大講義2011/ 06/04
榎本悠介(mosa)
42
(JAVA)
public class SlimeXSlimeRancher2 {
public int train(int[] a){
int res=0; //結果
int l=a.length; //如意棒の数
int max=a[0]; //最大値をいれたい！
for(int i=1;i<l;i++)max=Math.max(max,a[i]);
//まずは最大値を出す
for(int i=0;i<l;i++)res+=(max-a[i]);
//最大値からの差分を足していく
return res; //結果を返す
}
}
東大講義2011/ 06/04
榎本悠介(mosa)
43
• 必要な知識は・・・
配列の取り扱い
ループの書き方
max(大きい方を取り出す)の使い方
関数の返し方
• これだけ簡単な問題で基本的なことがおさえられる！
東大講義2011/ 06/04
榎本悠介(mosa)
44
3.
1
1から1000までの素数を返してください
• 考えてみよう！
東大講義2011/ 06/04
榎本悠介(mosa)
45
1
• 「ある数Mが素数かどうか」さえ判別できれば良さそう。
あとは1-Nまでそれぞれ調べるだけ。
これを「全探索」といいます。
• 「ある数Mが素数かどうか」は、どう判別するか？
2～M-1の全ての数で割り切れないかどうか調べればいい！
やはり全探索。
実際は√Mまで調べればよさそう。M=100は50で割り切れるけれ
ど、2で割り切れたことで判定済み。
東大講義2011/ 06/04
榎本悠介(mosa)
46
1
(JAVA)
static int n;
static int[] primes;
void run(){
n=1000;
primes=new int[n];//素数を入れる配列
int now=0;
for(int i=2;i<n;i++){
if(check(i)){
primes[now]=i;
now++;
}
}
}
boolean check(int M){//素数判定する関数
for(int i=2;i*i<=M;i++){//√Mまで調べれば十分
if(M%i==0) return false;//2から√Mまでの数で割り切れたらfalse
}
return true;
}
東大講義2011/ 06/04
榎本悠介(mosa)
47
(2)
1から10000000までの素数を返してください
• あれ、何が変わった？
範囲が1000までから1000万になった！
• さっきと一緒で大丈夫？
東大講義2011/ 06/04
榎本悠介(mosa)
48
4.
(1)
ポント：TopCoderは計算時間2秒以内にしないと0点！
→きちんと計算時間を見積もれるようになろう。
• 「理論上解けるかどうか」と「実際解き終わるかどう
か」には大きな違いがある！！
• 同じ問題でも、解き方によって計算時間は全然違う！
家庭用PCで0.1秒で済む問題が、まずい解き方をするとスーパコ
ンピューターでも地球の年齢以上に時間がかかってしまうケー
スも…
TopCoderはコードを書くスピード勝負なので、「試しに
書いてみて2秒以上かかるからやり直し」はできない！
きちんと事前に見積もれることが必要。
東大講義2011/ 06/04
榎本悠介(mosa)
49
4.
(2)
見積もり方：ループや再帰に注目！
• 1回の演算(足し算など)につき、計算量は1回。それをn回
ループするなら計算量はn回。2重ループならn^2回。
• 計算量のオーダーをO(n)やO(n^2) 、O(logn) などであらわ
す。
強い者のみ考える。O(n)+O(n^2)→O(n^2) 定数倍は無視。
このように、あまり厳密に見積もらずとも大丈夫な場合が多い
• 言語や環境にもよるが、1000万-1億回の計算で1秒程度
かかる。
TopCoderは、2秒までに計算しないと0点。
例題：素数の全探索は、だいたい計算量どれくらい？
東大講義2011/ 06/04
榎本悠介(mosa)
50
4.
(3)
素数の全探索なら、
「Mが素数かどうか」で√M回
「1-Nが素数かどうか」でN回
M≦Nなので、たかだかO(N√N)回の計算量。
N=1000ならN√N≒30000回で大丈夫だが…
(1000万-1億回の計算で1秒程度)
N=10^7(1000万)なら、N√N=10^10.5≒300億回
最悪30-300秒程度かかる！
TopCoderは、2秒までに計算しないと0点なので、解法(アルゴリ
ズム)を変えなくてはならない！
東大講義2011/ 06/04
榎本悠介(mosa)
51
5.
2
• 有名な「エラトステネスの篩」を用いる。
素数を見つけ次第、素数の倍数を消していく動作を繰り返す。
• boolean primes[N] の配列を用意。初期値は全てtrue。2か
らNまでのすべての数に対し、以下の操作を繰り返す
1.
2.
3.
4.
5.
2→primes*4+,*6+,*8+…をfalseにする
残ったうちの最小のtrueな数である3は素数であり、
3→primes*6+,*9+,… をfalseにする
次に残った最小のtrueは5。primes*10+,*15+,…はfalse
次に残った最小のtrueは7。primes*14+,*21+… はfalse
東大講義2011/ 06/04
榎本悠介(mosa)
52
(JAVA)
static int N;
static boolean p[];
void run(){
N=10000000;
p=new boolean[N+1]; //配列は0から始まるので、個数はN+1用意
int i,j;
for(i=2;i<=N;i++)p[i]=true;//最初は全部が素数の候補
for(i=2;i<=N;i++){//素数の倍数を消していくループ。
if(p[i]){// iは素数
for(j=2;i*j<=N;j++){//Nを越えない範囲で、倍数
を消す
p[i*j]=false;
}
}
}
}
東大講義2011/ 06/04
榎本悠介(mosa)
53
• 計算時間は0.38秒！安心して提出できる。
ちなみに先ほどのゕルゴリズムでは、8.0秒程度かかってしまっ
た。
理論的には、計算量はO(NloglogN)であることがわかっている。
O(N√N)に比べれば、√とloglogの勝負なので、Nが大きければ大き
いほど圧倒的に早くなる！
• もう一工夫できないか？
素数 i の倍数を消す時、2倍から消す必要はあるか？
i より小さい素数の倍数は消されている！ i 倍から消せばよい！
iが素数かどうか、Nまで調べる必要はあるか？
√Nの倍数を消した時点で、全ての素数は特定される！
i*i > N となるため。
東大講義2011/ 06/04
榎本悠介(mosa)
54
(JAVA)
static int n;
static boolean p[];
void run(){
N=10000000;
p=new boolean[N+1]; //配列は0から始まるので、個数はn+1用意
int i,j;
for(i=2;i<=N;i++)p[i]=true;//最初は全部が素数の候補
for(i=2;i*i<=N;i++){//素数の倍数を消していくループ。√Nまでで
十分。
if(p[i]){// iは素数
for(j=i;i*j<=N;j++){//消すのはiの自乗から
p[i*j]=false;
}
}
}
}
計算時間は0.38→0.20秒に改善
55
6.
•
••
•
•
3
長さL cmの棒の上に、N匹の蟻が秒速1cmで歩
いています。蟻は棒の端に達すると落ちてい
きます。
あれ、何が変わった？
棒は狭いので、蟻同士がぶつかると、2匹の蟻
は逆方向に進んでいきます。
蟻の左端からの距離x[]は与えられますが、ど
ちらを向いているかわかりません。
全ての蟻が落ちるまでの最大/最小の時間を求
めてください。
1≦L,N≦10^6
0≦x≦L
PKU1852(ant)56
東大講義2011/ 06/04 榎本悠介(mosa)
ant
N=3
x[0]
L
x[1]
x[2]
どちらを向いているかはわからない！
例：N=3 L=10 x={3,7,8}
min:誰もぶつからずに3秒で落ちる
max:？ぶつかりまくるケース？ (答えは8秒)
東大講義2011/ 06/04
榎本悠介(mosa)
57
ant(
…)
• それぞれの蟻について、「右を向いているケース」「左
を向いているケース」で場合分け。
その後実際に歩かせてみて、衝突のたびに向きを変えさせる。
• 計算量は？
場合分けだけで2^N通りある。
N≦10^6…ってあれ？ 2^30≒1億とかなんですけど…
• 別のアルゴリズムが必要！
東大講義2011/ 06/04
榎本悠介(mosa)
58
ant
• よーく考えてみよう！
東大講義2011/ 06/04
榎本悠介(mosa)
59
ant
• よく考えると、衝突って･･･
通り過ぎるのと本質的に等しい！
東大講義2011/ 06/04
榎本悠介(mosa)
60
ant
結局全てのゕリはまっすぐ歩くだけ！
• min：端からの距離が一番近くなるような方向
• max：端からの距離が一番遠くなるような方向
結局、その時に一番遠いゕリの距離が答えになる！！
min：x[i],L-x[i] の小さい方の最大値
max：x[i],L-x[i]の大きい方の最大値
東大講義2011/ 06/04
榎本悠介(mosa)
61
ant
(JAVA)
public class Ant {
public int[] antWalk(int L,int[] x){
int[] res = new int[2];
int min=L; int max=0;
int N=x.length;
for(int i=0;i<N;i++){
min=Math.max(Math.min(x[i],L-x[i]),min);
max=Math.max(Math.max(x[i],L-x[i]),max);
}
res[0]=min; res[1]=max;
return res;
}
}
東大講義2011/ 06/04
榎本悠介(mosa)
62
2^N
時間があれば解説。
• 2進数表示を用いる。
• 0～2^N-1 までのすべての数をforで回し、for(i=0;i<2^N;i++)
「2進数表示のk桁目が1ならk匹目は左、0なら右向き」と定義すれ
ば、ありうる場合を網羅できる。
例：N=5の時、10001 なら、1,5匹目が左 2,3,4匹目が右。00000か
ら11111まで、2^5=32通りありうる。
具体的には、iを2^kで割った数について、2で除した余りが1か0かで判別する。
for(i=0;i<2^N;i++){
for(k=0;k<n;k++){
if((i/(2のk乗))%2==1){muki[k]=true;}
else{muki[k]=false}
}
}
DFS(深さ優先探索)でも書けたりする。
東大講義2011/ 06/04
榎本悠介(mosa)
63
TopCoder
(1)「Topcoder 登録」でググろう！
英語だし、とにかく導入法がわかりにくいので、日本語の解説
サトを見たほうが早い。(わからなかったら僕にskypeでも)
(2)「 Practice room」で適当にDIV2 easyの過去問を解こう！
慣れてきたら、週1の本戦に参加したりDIV2 mediumへ。プログ
ラミングに親しみたい人はこのレベルまでで十分。
(3)面白くなってきたら、勝つためにゕルゴリズムの勉強を
しよう！
幅優先探索/深さ優先探索/貪欲法/動的計画法/メモ化再帰/二分
探索… 色々なゕルゴリズムがある！
日本のredcoder3人衆が書いた、「プログラミングコンテスト
チャレンジブック」が神。antもこれから取ってきました。
東大講義2011/ 06/04
榎本悠介(mosa)
64
第一部
第ニ部
プログラミングの基礎が
どうやってプログラミン
わかれば、色々できる！
グに慣れるの？→TopCoder
• 作業の効率化
• プログラミングコンテ
スト
• 例：BOTの作成
• 簡単な問題でプログラ
• 武器：UWSC
ミングに慣れて、難し
• ちょっとした研究
い問題で楽しもう
• ポーカーにおけるラ
• 具体的な問題に挑戦し
ンダムウォーク
てみよう！
東大講義2011/ 06/04
榎本悠介(mosa)
65
• mosa
• 東大生
工学部 計数工学科3.5年
• twitter:mosa_siru
• skype:mosa_siruo
一緒にTopCoderやボン
バーマンしましょう！
東大講義2011/ 06/04
榎本悠介(mosa)
66