クリスマスの過ごし方 2019年版
クリスマス予定ある人〜〜〜〜！
あるの？
こんな記事見てんじゃねえ
帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ帰れ
（この記事はクリスマスに特によていがない人向けのやつです）
クリスマスの過ごし方 初稿 2019年版
1.本記事の概要
陰者のひがみ
その日にとるべき最適行動の解析を簡便にとる手法についててきとうに考えて書いた。
2.理論
2-1. ナップザック問題
重さw、価値vを持つ荷物を重さが合計Wまでしか入らないナップザックに詰め込む際に、詰め込む荷物の価値の総和を最大化する問題。動的計画法で解くのが一般的。
dp[i][j]を、「i番目の荷物まで見た時、詰め込んだ荷物の重さの総和がjになる時の、詰め込んだ荷物の価値の総和の最大値」と定義する。
初期値は0
dp[i+1][j]=max(dp[i][j], dp[i+1][j])
dp[i+1][j+w]=max(dp[i][j]+v, dp[i+1][j+w])
として更新する。
見ての通りだが、O(NW)の計算量を要する。
2-2. 経路復元
もともとは最短経路問題の最短経路を復元するためのテクニックである。基本的に他の動的計画法でも応用できる。今回は価値最大で詰め込んだ時の選んだアイテムが復元できる。
dp[i][j]=dp[i-1][j-w]+v
または
dp[i][j]=dp[i-1][j]
であるようなjを順番に探索していくことで復元できる。
最低O(N)の計算量を要する。
2-3. 量的功利主義
ベンサム曰く、快楽は定量的に計算できるらしい。よく知らない。
3.実践
3-1. 使うもの
好きなプログラミング言語（ここではPythonを使っています）
3-2. することリストをつくる
することをまとめる。１日でとても終わらない量でもいいので、思いついたものをてきとうに書く。かかる推定時間と得られる推定快楽をてきとうに書く。
サンプル：
（すること名, かかる秒数, 得られる快楽 になっている）
すること数 20
"ねる", 7200, 334
"惰眠", 7200, 334
"あさ風呂", 1200, 220
"だめ押しの二度寝", 7200, 334
"ごはんを食べる", 600, 100
"外食", 1800, 200
"ひる寝！笑", 3600, 334
"精進", 4000, 100
"ばちゃ", 6000, 150
"おやつ食べる", 300, 50
"惰眠", 1800, 334
"Youtubeをみる", 1800, 90
"レポートやる", 7200, 1
"ごはんを食べる", 600, 100
"外食", 1800, 200
"おふろ", 1200, 150
"ごはんを食べる", 600, 100
"外食", 1800, 200
"べんきょう！", 7200, 1
"おねんね", 3600, 334
リストを作るときは頭を空っぽにして作ると丁度いいのだが、ひとつ気をつけておくべきことがある。後で経路復元する際、この順番で出力されるので1日の流れを少しだけ考えてリストを作ると良い。
3-3. ナップザックDPと経路復元を書く
重さを時間、価値を推定の快楽として見てナップザック問題を解く。
試しに書いてみた。
4.結果
3-2.で作ったサンプルを3-3.のコードで処理した。
試しに12時間の予定を組んでみた。秒単位のスケジュールとなっている。
サンプルの出力：
ねる 予想時間： 7200 予想快楽： 334
惰眠 予想時間： 7200 予想快楽： 334
あさ風呂 予想時間： 1200 予想快楽： 220
だめ押しの二度寝 予想時間： 7200 予想快楽： 334
ごはんを食べる 予想時間： 600 予想快楽： 100
外食 予想時間： 1800 予想快楽： 200
ひる寝！笑 予想時間： 3600 予想快楽： 334
精進 予想時間： 4000 予想快楽： 100
おやつ食べる 予想時間： 300 予想快楽： 50
惰眠 予想時間： 1800 予想快楽： 334
ごはんを食べる 予想時間： 600 予想快楽： 100
外食 予想時間： 1800 予想快楽： 200
おふろ 予想時間： 1200 予想快楽： 150
ごはんを食べる 予想時間： 600 予想快楽： 100
外食 予想時間： 1800 予想快楽： 200
合計予想時間： 40900
合計予想快楽： 3090
か、完璧だ・・・！（AC）
と思ったけどごはん食べ過ぎでは？むずかC
5.まとめ
みんなもこんな感じで予定を作って人生破壊しよう！
