2020-09-08に更新
動的計画法（ダイナミック・プログラミング）をやろうぜ☆（＾～＾）？
「 ↓ 動的計画法を効率的かつ高速に習得したかったら、 Educational DP Contest の例題をやれだぜ☆」
Educational DP Contest / DP まとめコンテスト - 問題
「 じゃあ お父んのブログなんか読まなくてもいいじゃないか☆？」
「 でも AtCoder の参加者のソースは ライセンス が不明だから パクれないのよ」
「 ソースコードの著作権は参加者に帰属するみたいな感じの １ミリも同意できない文 が書いてたので
わたしが 一から MITライセンス で書き直すことにするぜ☆」
「 再車輪か☆」
「 再……、車輪の再発明な☆ どうせ 再 なら 素早くやろう☆」
problem
1-- 4-- 8-- 5-- 3-- %
| | | | | |
| | | | | |
0-- 2-- 3-- 4-- 2-- 2
| | | | | |
| | | | | |
7-- 1-- 1-- 2-- 3-- 1
| | | | | |
| | | | | |
3-- 1-- 9-- 3-- 1-- 2
| | | | | |
| | | | | |
5-- 2-- 6-- 5-- 2-- 5
| | | | | |
| | | | | |
@-- 3-- 4-- 0-- 8-- 6
「 ↑ これが問題で、時計回りに４５°回転させるぜ☆」
high-score 0
pos
[Next 1 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +-- 8
| | | | | |
+-- 3 +-- 1 +-- 3 +-- 5
| | | | | | | |
+-- 5 +-- 1 +-- 1 +-- 4 +-- 3
| | | | | | | | | |
@ +-- 2 +-- 9 +-- 2 +-- 2 +-- %
| | | | | | | | | |
+-- 3 +-- 6 +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
「 ↑ これがゲーム画面だぜ☆
@ が君だぜ☆ 階段 % を目指せだぜ☆」
「 ％ がなんで階段なんだぜ☆！」
「 操作は 上に行くか、下に行くか 選ぶのみ☆ 強制右スクロールだぜ☆
途中に落ちている数を足していって、ハイスコアを目指せだぜ☆」
「 そんなん簡単よ」
「 やってみろだぜ☆
上に行くのは do u、 下に行くのは do d だぜ☆」
do u
pos
[Next 2 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +-- 8
| | | | | |
+-- 3 +-- 1 +-- 3 +-- 5
| | | | | | | |
+-- @ +-- 1 +-- 1 +-- 4 +-- 3
| | | | | | | | | |
+-- 2 +-- 9 +-- 2 +-- 2 +--
| | | | | | | | | |
+-- 3 +-- 6 +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
score 5
「 下じゃなくていいのかだぜ☆？」
「 ど真ん中の 9 と、４５°上の端っこの 8 を狙えばしまいよ！」
do d
pos
[Next 3 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +-- 8
| | | | | |
+-- 3 +-- 1 +-- 3 +-- 5
| | | | | | | |
+-- +-- 1 +-- 1 +-- 4 +-- 3
| | | | | | | | | |
+-- @ +-- 9 +-- 2 +-- 2 +--
| | | | | | | | | |
+-- 3 +-- 6 +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
score 7
「 他にもあるかも知れないのに……☆」
「 ぱっと見た感じ こんなでかい数、落ちてないわよ！」
do d
pos
[Next 4 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +-- 8
| | | | | |
+-- 3 +-- 1 +-- 3 +-- 5
| | | | | | | |
+-- +-- 1 +-- 1 +-- 4 +-- 3
| | | | | | | | | |
+-- +-- 9 +-- 2 +-- 2 +--
| | | | | | | | | |
+-- 3 +-- @ +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
score 13
「 目先の利益ばかり 追いかけていくな……☆」
「 一番いいところに行く途中に 良いもんが落ちてんのよ！」
do u
pos
[Next 5 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +-- 8
| | | | | |
+-- 3 +-- 1 +-- 3 +-- 5
| | | | | | | |
+-- +-- 1 +-- 1 +-- 4 +-- 3
| | | | | | | | | |
+-- +-- @ +-- 2 +-- 2 +--
| | | | | | | | | |
+-- 3 +-- +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
score 22
「 ↑ 9 取った！」
「 こんなゲームで ダイナミック・プログラミング やるまでもないよな☆」
do u
pos
[Next 6 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +-- 8
| | | | | |
+-- 3 +-- 1 +-- 3 +-- 5
| | | | | | | |
+-- +-- 1 +-- @ +-- 4 +-- 3
| | | | | | | | | |
+-- +-- +-- 2 +-- 2 +--
| | | | | | | | | |
+-- 3 +-- +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
score 23
「 ↑ 次は 8 行くわよ！」
「 迷いがないぜ☆」
do u
pos
[Next 7 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +-- 8
| | | | | |
+-- 3 +-- 1 +-- @ +-- 5
| | | | | | | |
+-- +-- 1 +-- +-- 4 +-- 3
| | | | | | | | | |
+-- +-- +-- 2 +-- 2 +--
| | | | | | | | | |
+-- 3 +-- +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
score 26
「 夢美は ちゃんと 探索したのか☆？」
「 でかい数を取りゃ いいのよーっ！」
do u
pos
[Next 8 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +-- @
| | | | | |
+-- 3 +-- 1 +-- +-- 5
| | | | | | | |
+-- +-- 1 +-- +-- 4 +-- 3
| | | | | | | | | |
+-- +-- +-- 2 +-- 2 +--
| | | | | | | | | |
+-- 3 +-- +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
score 34
「 8 取った！」
「 もう後は 下に行くだけだな☆」
do d
pos
[Next 9 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +--
| | | | | |
+-- 3 +-- 1 +-- +-- @
| | | | | | | |
+-- +-- 1 +-- +-- 4 +-- 3
| | | | | | | | | |
+-- +-- +-- 2 +-- 2 +--
| | | | | | | | | |
+-- 3 +-- +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
score 39
「 これより 良い経路があるんなら 選んでみなさいよ！」
「 オッカムのカミソリは無いんで、最後まで続けてくれだぜ☆」
pos
[Next 10 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +--
| | | | | |
+-- 3 +-- 1 +-- +--
| | | | | | | |
+-- +-- 1 +-- +-- 4 +-- @
| | | | | | | | | |
+-- +-- +-- 2 +-- 2 +--
| | | | | | | | | |
+-- 3 +-- +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
score 42
「 つら……」
do d
pos
[Finished]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +--
| | | | | |
+-- 3 +-- 1 +-- +--
| | | | | | | |
+-- +-- 1 +-- +-- 4 +--
| | | | | | | | | |
+-- +-- +-- 2 +-- 2 +--@
| | | | | | | | | |
+-- 3 +-- +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
score 42
update
high-score 42
「 終わった！」
「 ４２点より 良い点は 取れないのでは？」
「 ほら見ろ！」
「 本当に無いか 調べてみようぜ☆？」
```plain
resolve
[Resolve / Next 1 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +-- 8
| | | | | |
+-- 3 +-- 1 +-- 3 +-- 5
| | | | | | | |
+-- 5 +-- 1 +-- 1 +-- 4 +-- 3
| | | | | | | | | |
@ +-- 2 +-- 9 +-- 2 +-- 2 +--
| | | | | | | | | |
+-- 3 +-- 6 +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
cur = [0]
cur = add_max(cur, [5,3])
= [5,3]
[Resolve / Next 2 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +-- 8
| | | | | |
+-- 3 +-- 1 +-- 3 +-- 5
| | | | | | | |
+-- 5 +-- 1 +-- 1 +-- 4 +-- 3
| | | | | | | | | |
+ +-- 2 +-- 9 +-- 2 +-- 2 +--
| | | | | | | | | |
+-- 3 +-- 6 +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 4 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
cur = [5,3]
cur = add_max(cur, [3,2,4])
= [8,7,7]
[Resolve / Next 3 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+-- 7 +-- 2 +-- 8
| | | | | |
+-- 8 +-- 1 +-- 3 +-- 5
| | | | | | | |
+---+ +-- 1 +-- 1 +-- 4 +-- 3
| | | | | | | | | |
+ +-- 7 +-- 9 +-- 2 +-- 2 +--
| | | | | | | | |
+---+ +-- 6 +-- 3 +-- 3 +-- 2
| | | | | | | |
+-- 7 +-- 5 +-- 1 +-- 1
| | | | | |
+-- 0 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
cur = [8,7,7]
cur = add_max(cur, [7,1,6,0])
= [15,9,13,7]
[Resolve / Next 4 column(s)]
+-- 1
| |
+-- 0 +-- 4
| | | |
+--15 +-- 2 +-- 8
| | | | | |
+---+ +-- 1 +-- 3 +-- 5
| | | | | | | |
+---+ +-- 9 +-- 1 +-- 4 +-- 3
| | | | | | | | |
+ +---+ +-- 9 +-- 2 +-- 2 +--
| | | | | | | | |
+---+ +--13 +-- 3 +-- 3 +-- 2
| | | | | | | |
+---+ +-- 5 +-- 1 +-- 1
| | | | | |
+-- 7 +-- 2 +-- 2
| | | |
+-- 8 +-- 5
| |
+-- 6
cur = [15,9,13,7]
cur = add_max(cur, [0,1,9,5,8])
= [15,16,22,18,15]
[Resolve / Next 5 column(s)]
+-- 1
| |
+--15 +-- 4
| | | |
+---+ +-- 2 +-- 8
| | | | | |
+---+ +--16 +-- 3 +-- 5
| | | | | | |
+---+ +-- +-- 1 +-- 4 +-- 3
| | | | | | | |
+ +---+ +--22 +-- 2 +-- 2 +--
| | | | | | | | |
+---+ +---+ +-- 3 +-- 3 +-- 2
| | | | | | | |
+---+ +--18 +-- 1 +-- 1
| | | | |
+---+ +-- 2 +-- 2
| | | |
+--15 +-- 5
| |
+-- 6
cur = [15,16,22,18,15]
cur = add_max(cur, [1,2,1,3,2,6])
= [16,18,23,25,20,21]
[Resolve / Next 6 column(s)]
+--16
| |
+---+ +-- 4
| | | |
+---+ +--18 +-- 8
| | | | | |
+---+ +---+ +-- 3 +-- 5
| | | | | |
+---+ +-- +--23 +-- 4 +-- 3
| | | | | | | |
+ +---+ +---+ +-- 2 +-- 2 +--
| | | | | | | | |
+---+ +---+ +--25 +-- 3 +-- 2
| | | | | | |
+---+ +---+ +-- 1 +-- 1
| | | | |
+---+ +--20 +-- 2
| | |
+---+ +-- 5
| |
+--21
cur = [16,18,23,25,20,21]
cur = add_max(cur, [4,3,2,1,5])
= [22,26,27,26,26]
[Resolve / Next 7 column(s)]
+--
|
+---+ +--22
| | | |
+---+ +---+ +-- 8
| | | | |
+---+ +---+ +--26 +-- 5
| | | | | |
+---+ +-- +---+ +-- 4 +-- 3
| | | | | | |
+ +---+ +---+ +--27 +-- 2 +--
| | | | | | | | |
+---+ +---+ +---+ +-- 3 +-- 2
| | | | | | |
+---+ +---+ +--26 +-- 1
| | | |
+---+ +-- +-- 2
| |
+---+ +--26
| |
+---+
cur = [22,26,27,26,26]
cur = add_max(cur, [8,4,3,2])
= [34,31,29,28]
[Resolve / Next 8 column(s)]
+--
|
+---+ +--
| | |
+---+ +---+ +--34
| | | | |
+---+ +---+ +---+ +-- 5
| | | | | |
+---+ +-- +---+ +--31 +-- 3
| | | | | | |
+ +---+ +---+ +---+ +-- 2 +--
| | | | | | | |
+---+ +---+ +---+ +--29 +-- 2
| | | | | | |
+---+ +---+ +---+ +-- 1
| | | |
+---+ +-- +--28
| |
+---+ +---+
| |
+---+
cur = [34,31,29,28]
cur = add_max(cur, [5,2,1])
= [39,33,30]
[Resolve / Next 9 column(s)]
+--
|
+---+ +--
| | |
+---+ +---+ +---+
| | | | |
+---+ +---+ +---+ +--39
| | | | |
+---+ +-- +---+ +---+ +-- 3
| | | | | | |
+ +---+ +---+ +---+ +--33 +--
| | | | | | |
+---+ +---+ +---+ +---+ +-- 2
| | | | | | |
+---+ +---+ +---+ +--30
| | |
+---+ +-- +--
| |
+---+ +---+
| |
+---+
cur = [39,33,30]
cur = add_max(cur, [3,2])
= [42,35]
[Resolve / Next 10 column(s)]
+--
|
+---+ +--
| | |
+---+ +---+ +---+
| | | | |
+---+ +---+ +---+ +---+
| | | | |
+---+ +-- +---+ +---+ +--42
| | | | | |
+ +---+ +---+ +---+ +---+ +--
| | | | | | |
+---+ +---+ +---+ +---+ +--35
| | | | | |
+---+ +---+ +---+ +--
| | |
+---+ +-- +--
| |
+---+ +---+
| |
+---+
cur = [42,35]
cur = add_max(cur, [0])
= [42]
[Finished]
+--
|
+---+ +--
| | |
+---+ +---+ +---+
| | | | |
+---+ +---+ +---+ +---+
| | | | |
+---+ +-- +---+ +---+ +---+
| | | | | |
+ +---+ +---+ +---+ +---+ +--42
| | | | | |
+---+ +---+ +---+ +---+ +--
| | | | | |
+---+ +---+ +---+ +--
| | |
+---+ +-- +--
| |
+---+ +---+
| |
+---+
cur = [42]
max-score 42
「 説明がめんどくさいんで、心で感じろだぜ☆」
「 くそっ☆」
「 ゴールから スタートへ必ず戻れるんで、すきな経路で帰れだぜ☆」
＜書きかけ＞
何度でもクリック！→
光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位
Crieitは個人で開発中です。
興味がある方は是非記事の投稿をお願いします！ どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか
また、「こんな記事が読みたいけど見つからない！」という方は是非記事投稿リクエストボードへ！
こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください！