ABC 60-D Simple Knapsack

こんにちは。今日はABC60でしたね。

D問題はナップザックだと思って以下のようなコードを書いたのですが、WAだったので自分のコードがWAするテストケースを考えました。

public static long solve(int index, long weight, long value) {
    String s = index + "," + weight;
    if (w < weight) {
        return Integer.MIN_VALUE;
    } else if (memo.containsKey(s)) {
        return memo.get(s);
    } else if (index == n) {
        return value;
    } 
    
    long temp = Math.max(
            solve(index + 1, weight, value),
            solve(index + 1, weight + weights[index], value + values[index])
    );
    memo.put(s, temp);
    
    return temp;
}

こんなテストケースを考えてみます。

4 3
1 100
1 2
2 3
9 10

このテストケースではこのプログラムは5を返します。間違ってます。

問題点

どこが問題なのかを探るために、この関数が呼ぶすべての引数を図にしてみます。 f:id:ilovehugeworld:20170430002410p:plain

問題が起きる箇所まで戻り値とmemoを埋めてみます。 f:id:ilovehugeworld:20170430003347p:plain

問題点が見つかりました。solve(2, 1, 100)でカバンのなかにすでに100の価値があるのに、memoから5を返しているのです。これは間違ってます。つまり、このコードの問題点は現在のカバンの中にある価値を考えずに、すでに探索したことがある場合その最大値を返しているところです。

改善案

valueを関数に渡すのではなく、戻ってきた値に足しましょう。

public static long solve2(int index, long weight) {
    String s = index + "," + weight;
    if (w < weight) {
        return Integer.MIN_VALUE;
    } else if (index == n) {
        return 0;
    } else if (memo.containsKey(s)) {
        return memo.get(s);
    }
    long temp = Math.max(
            solve2(index + 1, weight), 
            values[index] + solve2(index + 1, weight + weights[index])
    );
    
    memo.put(s, temp);
    return temp;
}

これで、ACがもらえます。教訓はDPを書くときは戻り値にコストを加えるということです。 問題点は@eiyaさんに指摘してもらいました。ありがとうございました!

ABC 22-C Blue bird

重りつきのグラフが与えられ、スタート地点から出発しスタート地点へ戻ってくる最短の道のりを答える問題。 C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder

最初はダイクストラに通った道を記憶させ、それを通らないようにするんだと思って実装するも、探索する量が多くなりTLE。そこから考えてもわからなかったので、解説をみてちょっと実装。TLE。結局、最後まで解説をみてACできました。

グラフだし、最小パスを求めるからできると思いましたが、出来ませんでした。悔しい。この問題から一般的な知識を得るとしたら何になるんでしょうか。

  • 閉路とは、どの点をとっても2つの点で結ばれてる。
  • 最小の閉路の中で同じ点を2度訪れることはない

こんな感じですかね。一つ目がわかってれば、始まりの点から繋がってる点を順繰りに試して短いものをキープしてけばいいんだという発送に繋がりそうです。C問題も自力で解ける問題がなくなってきました。これからは、2,3日かけて考えてわからなかったら解説をみるという流れになりそうです。

蜜蜂と遠雷 〜感想〜

蜜蜂と遠雷を読みました。

この本はたしか、どこかで「他の作家が嫉妬する」や「音楽を文章でこんなにも表現できるとは!?」みたいな折込文句を見かけて購入したのですが、折込文句通りでした。読み終えて心地よい感動に包まれております。

面白いのは、音楽家たちのコンサートという短い時間での出来事を取り扱っているのに、ものすごく広い世界が広がっていることです。それぞれが演奏で表現したい世界、登場人物である亜夜の気持ちの移り変わり、権威側になった審査員たちの揺れ、そしてコンサート後の未来。これらがつぶさに表現されることで、ものすごく明度の高い世界が作り上げられてます。あまりにも鮮明に表現されるので、ほかの漫画シーンが頭のなかに浮かんできて、ここはこんな感じだな、これが漫画化されたらこんな感じかなとも楽しめました。勝手な妄想ですが、風間塵は「ボールルームへようこそ」に出てくるたたら、栄伝亜夜は「王様達のバイキング」にでてくるValkyrja、マサルはこれまた「ボールルームへようこそ」の仙石さんのビジュアルイメージです。まるで、音楽の歴史とこれからの未来を、精工な箱庭に落とし込んだような小説でした。

僕が好きなシーンは、社会人としてコンサートに出場した高島明石の第2次予選です。凡人を自称する彼の音楽家としての第一歩にあたるここのシーンは鳥肌がたちました。また、彼の「何かが上達する時というのは、階段状だ。」というセリフにも、こういう風に捉えればいいのかと感心しました。

何かが上達する時というのは、階段状だ。緩やかに坂を登るように上達する、というのはあり得ない。 弾けども弾けども足踏みばかりで、ちっとも前に進まない時がある。これがもう限界なのかと絶望する時間がいつ果てるともなく続く。 しかし、ある日突然、次の段階に上がる瞬間がやってくる。

また、亜夜、塵、マサル、奏が4人で外出してるシーンでは、天才でもウィンドーショッピングするよねと親しみを感じました。まとめると、ものすごく引き込まれる小説です。天才たちの共鳴、ピアニストが見せる世界、そして散りばめられる未来の断片。没入感間違いなしです。ぜひ読んでみてください。蜜蜂と遠雷を読んで、ここまでの情景を見せるクラシック音楽に興味が湧いてきました。クラシック音楽はイマイチ鑑賞できませんでしたが、NAXOS Japanから蜜蜂と遠雷に登場する楽曲を収めたアルバムがでるので、購入して勉強してみたいと思います。

箱庭のような世界だと僕は感じましたが、読んだ方はその感想を知りたいので気軽にコメントしてください〜。ではでは