K2NR.ME

このエントリーをはてなブックマークに追加 Tweet

続・Google Code Jam Japanに参加してみた

この話の続き:Google Code Jam Japanに参加してみた

しかし、計算量を減らすためにはもっと簡単な方法がある。
「何をしなくてもよいか」を考えることだ。

Vichromeの開発してたりドラマ見てたり寝てたりしてたら見着手だった問題Bを解くのを忘れてたのでチャレンジしてみた。

まずは問題を確認してね。

予選の本番では問題だけ読んでヤバそうだからスキップした問題だったが、やってみるとやっぱり難しかった。実際、予選の結果でもこの問題だけ解けてる人が少ない。

さっそく問題に移ろう。
はじめに最も効率的な飲み方とはどのようなものなのかを考えてみる。まず、当然満足度の高いコーヒーを飲まずに賞味期限を迎えるのはダメだ。これは当たり前。しかし、満足度の最も高いコーヒーが比較的賞味期限まで余裕がある場合、これを先に飲んでる間に次点で満足度の高いコーヒーが賞味期限を迎えて飲めなくなる可能性がある。こういう場合は次点のコーヒーを先に飲んで最も満足度の高いコーヒーはその後で飲むべきだろう。この考え方を突き詰めていくと

  1. 最も満足度の高いコーヒーを賞味期限ギリギリで全部飲み終わるように、賞味期限当日から1日目に向かって連続で満足度の最も高いコーヒーを飲む日とする。カレンダーに予定を埋めていく様子を想像しよう。手順1の時点で満足度の最も高いコーヒーを飲む日は予定が埋まってしまっていることになる。
  2. 次に満足度の高いコーヒーを賞味期限ギリギリで全部飲み終わるように飲む。最も満足度の高いコーヒーを飲む日は既に予約が埋まっているので、そこ以外の日を賞味期限当日から1日目に向かって埋めていく。

。。。。

この手順を延々と続けていき、1日目からK日目までの予定が全部埋まるか、飲むコーヒーが無くなったら処理終了。あくまで概念的な話なので、実際には「予定を埋める」というのはコーヒーの満足度を足し合わせるという処理になる。

言葉にすると比較的シンプルなイメージだが実際にプログラミングすると意外にややこしい。説明するのも逆に分かりにくくなりそうなので、実際のコードをコピペすることにする。

#include <vector>
#include <algorithm>
#include <utility>
#include <stdio.h> using namespace std; struct Coffee { int64_t c; // number of cups int64_t t; // limit date uint32_t s; // satisfied }; vector<Coffee> coffees; uint32_t N; bool coffeeSort(const Coffee& a, const Coffee& b) { return (a.s > b.s); } uint64_t drinkDeliciousCoffee(int64_t start, int64_t end) { int64_t total = 0; int64_t p = end; int i; for( i=0; i < N; i++ ) { if( coffees[i].c > 0 && coffees[i].t >= start ) break; } if( i == N ) return 0; p = min( p, coffees[i].t ); int64_t consumed = min( p - start + 1, coffees[i].c ); total += coffees[i].s * consumed; coffees[i].c -= consumed; if( p < end ) total += drinkDeliciousCoffee( p + 1, end ); if(p - consumed >= start ) total += drinkDeliciousCoffee( start, p - consumed ); return total; } int main() { int T; // number of testcases scanf("%d", &T); for(int t=0; t < T; t++) { int64_t K; scanf("%d %lld", &N, &K); coffees.resize(N); for(int i=0; i<N; i++){ scanf("%lld %lld %d", &coffees[i].c, &coffees[i].t, &coffees[i].s); } sort(coffees.begin(), coffees.end(), coffeeSort); printf("Case #%d: %lld\n", t+1, drinkDeliciousCoffee( 1, K )); } return 0; }

63行。なかなかコンパクトかつエレガントに収まったのではないかと思う。関数名は僕の一流のジョークなので素人は真似しないように。

実装のキモはdrinkDeliciousCoffeeがrecursiveな呼び出しになっていることだ。1種類のコーヒーについて処理したら、埋めた予定より後と前の空き予定についてrecursiveに処理を行なっている。イメージとしてはクイックソートのアルゴリズムに近い。このような実装にすることで断片化してコマ切れになった空き予定を考慮する必要がなくなり、常に連続している空き予定だけを考えることが出来る。

このアルゴリズムでは、今日はAを飲んで明日はB明後日はCというように毎日飲むものが違うような場合に最も遅くなる。最悪計算量はよくわからないが、Nが最大で100であることから、1日目からK日目までほとんどの部分で連続して同じ種類を飲むと考えられるため平均計算量は非常に小さい(はず)。いずれにしてもKではなくNに依存するアルゴリズムなので、問題Bには非常に適したアルゴリズムといえるだろう。

ちなみに、僕は問題Bを解くのに3時間くらいかかった。この程度の問題に3時間もかけているようではGoogle Tシャツ(200位以内ね)なんか夢のまた夢なのだろうか。よくわからない。

comments powered by Disqus