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

裏紙

ほぼ競プロ、たまに日記

SRM 667 Div1 Easy - OrderOfOperations

programming SRM

問題

TopCoder Statistics - Problem Statement

問題概要

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

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

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

イデア

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

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

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

実装(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];
    }
};