SRM 667 Div1 Easy - OrderOfOperations

問題

TopCoder Statistics - Problem Statement

問題概要

メモリの領域が個あるコンピュータがあり、そのそれぞれの領域にまでの番号を付ける。そのコンピュータを使って個のプログラムを実行することを考える。1つのプログラムは文字で構成されており、その文字目はそのプログラムが番目のメモリ領域を使用するか否かが書かれている。個のプログラムはどのような順番で実行しても構わない、またそれぞれのプログラムは1回ずつ実行する。

コンピュータはキャッシュを備えており、一度番目のメモリ領域へのアクセスがあれば、その領域へのアクセスは時間遅延なしで行うことができるが、現在のキャッシュ状態と比べて新しいメモリ領域へのアクセスが個ある場合にはの時間遅延が発生する。

個のプログラムを実行する時の時間遅延の合計の最小値を求めよ。

アイデア

まず、すでにキャッシュが全て埋まっていれば、どのプログラムにも実行時間がかからないのは明らか。ここからは、キャッシュを埋めていくことを考えてみる。ただし、全てのプログラムで使用されないメモリ領域があるケースも存在しうるので、正確には全てのキャッシュではなく、個のプログラムで使用されるメモリ領域のキャッシュ全てということになる。この状態をend_maskと表すことにする。

問題文より、キャッシュにまだのっていないメモリ領域にアクセスするプログラムを実行するときはそのようなメモリ領域が個ある時に時間遅延がだけ発生するとある。ならば、新しいメモリ領域へのアクセスがある、つまりこのプログラムはまだ1回も実行されていないということを表している。もしなら、そのプログラムがまだ実行されていない可能性もあるが、結局実行に時間がかからないので、既に実行したものであると見なすことが出来る。

そして、dp[mask]=キャッシュの状態がmaskにたどり着くために必要な時間遅延の合計の最小値を保存しながら、全ての状態に対して、個のプログラムの実行を試すことによって最小値を更新していくことが出来る。これによって時間計算量はによって実現できる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

class OrderOfOperations {
    public:
    int minTime(vector<string> s) {
      int i,j;

      int n=s.size();
      int m=s[0].size();

      //最終状態
      int end_mask=0;
      //それぞれのプログラム
      int s_mask[50];

      rep(i,n){//n個のプログラム
        s_mask[i]=0;
        rep(j,m){
          if(s[i][j]=='1') s_mask[i]+=(1<<j);
        }
        end_mask |= s_mask[i];
      }

      int INF=10000;
      int dp[1234567];
      fill(dp,dp+1234567,INF);
      dp[0]=0;

      int mask;
      rep(mask,1<<m){//キャッシュ状態がmaskの時
        rep(j,n){
          //j番目のプログラム実行によりキャッシュの状態はnext_maskになる
          int next_mask = mask|s_mask[j];
          //新しくアクセスするメモリ数、つまり時間遅延
          //__builtin_popcount :立っているビット数を返す
          int k = __builtin_popcount(next_mask-mask);
          dp[next_mask]=min(dp[next_mask],dp[mask]+k*k);
        }
      }

      return dp[end_mask];
    }
};