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

AOJ0595 - Schedule

AOJ プログラミング 動的計画法

DPが出来なさすぎてつらいので練習

AOJ0595(Schedule)

コード

// 8種類の選び方 N日のスケジュール
int dp[8][1010];
const int mod = 1e4 + 7;

int getid(char c)
{
  if (c == 'J') return 0;
  if (c == 'O') return 1;
  return 2;
}

// 責任者が居ない場合を除外
void exclude(int now, int id)
{
  REP(i, 8) {
    if ((i & (1 << id)) == 0) {
      dp[i][now] = 0;
    }
  }
}

signed main()
{
  int N;
  string s;
  cin >> N >> s;

  REP(i, N) {
    // 一日目はJの参加が必須
    if (i == 0) {
      REP(j, 8) dp[j][i] = 1;
      exclude(i, 0);
    } else {
      REP(j, 8) {
        REP(k, 8) {
          // 前日に居た人が一人でも居なければ飛ばす
          if (j & k) {
            dp[k][i] = (dp[k][i] + dp[j][i - 1]) % mod;
          }
        }
      }
    }
    exclude(i, getid(s[i]));
  }
  int ans = 0;
  REP(i, 8) {
    ans = (ans + dp[i][N - 1]) % mod;
  }
  print(ans);

  return 0;
}

メモ

分からなかったのでJOIの解説を見ながら実装した.
dp[出席状況][何日目] = スケジュールの場合の数 を表す.
dp[k][i] = (dp[k][i] + dp[j][i - 1]) % mod は前日までの場合の数( dp[j][i - 1] )を足していく処理.
REP(j, 8) REP(k, 8) の部分で昨日の出席状況に合わせ,ありうる今日の出席状況を全列挙している.(ここでは責任者がいない場合は考慮していない)
そのあとのexclude(i, getid(s[i])) で責任者がいない出席状況のときの場合の数を0 にしている.

出席状況をbitで管理するのは面白いなぁと感じた.

こんな感じで1 が立ってるところは出席していると判断する.

I O J
0 0 0 0
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1

exclude() の中で責任者がいない場合を判断するために論理和を使っている.
if (j & k) は前日に居た人が居なかったら飛ばす(鍵が無いので出席できないから)ところでも論理和を使って上手く判定している.

また配るDPは最後に足す処理があることが多いらしい.覚えておこう.