読者です 読者をやめる 読者になる 読者になる

真面目なノート

こまめにその日の進捗などをメモしておく。

朝起きられなかった

今日のまとめ

  • 絵の練習
  • プログラミング
    • 48時間でSchemeを書こう
    • 競技プログラミングの勉強
  • 研究
    • 論文を一本流し読みした

プログラミング

48時間でSchemeを書こう

48時間でSchemeを書こう/評価: 第一部 - Wikibooks

ここ!

競技プログラミング

流石にコーディング力がダメダメすぎるのでちまちま競技プログラミングをして鍛えることにしました。
とりあえずAOJで色々問題を解いていく。今日はコレ。

0-1 Knapsack Problem | Aizu Online Judge

Python3で書いて通ったプログラムはこれ。

l = input().split()
N = int(l[0])
W = int(l[1])
products = []
for i in range(N):
    l = input().split()
    products.append([int(l[0]),int(l[1])])

DP = [0 for _ in range(W+1)]
for i in range(N):
    new_DP = [DP[j] if j < products[i][1] else 0 for j in range(W+1)]
    for j in range(products[i][1], W + 1):
        product_in = DP[j - products[i][1]] + products[i][0]
        if product_in >= DP[j]:
            new_DP[j] = product_in
        else:
            new_DP[j] = DP[j]
    DP = [v for v in new_DP]
print(DP[W])

通ったは通ったけど、若干気になる、というかスマートじゃないかな、というところがある。

new_DP = [DP[j] if j < products[i][1] else 0 for j in range(W+1)]
range(products[i][1], W + 1)

これはナップザックに入れるものの重さについての境界条件に関わる部分だけれど、ここをrangeで分けちゃったせいでその上のリスト内包表記がちょっと気持ち悪い気がする。
もっと綺麗な書き方がきっとあるはず……だけど思いつかないので、明日辺りいくつか他の人のコードを見ながら考えたいと思う。

研究

スポーツとかのゲームバランスを取るためのハンデ設定の論文を読んだ。
正直う〜んって感じで、あまり自分の研究に役に立たなさそうなので、テキトーに流し読みして済ませた。