超初心者が競プロに挑む

初心者からの競プロ練習記録

ABC025C解いてみた

ゲームの問題は初めてなので解いてみた。ゲーム木と呼ぶらしいですね。こういうの初見で解けるようになりたい。

#include <cstdio>
#include <algorithm>

using namespace std;

int b[2][3];
int c[3][2];
int allscore=0;

int getState(int state,int i, int j) {
  int index=i*3+j;
  return (state>>(index*2)) & 3;
}

int setState(int state, int value,int i, int j) {
  int index=i*3+j;
  return (value << (index*2)) | state;
}

int getMaxScore(int state, int side) {
  bool maximize = side % 2 == 0;
  int buffer = maximize ? -10000: 10000;

  if (side==9) {
    int score=0;
    for(int i=0;i<3;++i) {
      for(int j=0;j<3;++j) {
        if (i!=0) {
          if (getState(state,i,j) == getState(state,i-1,j)) {
            score += b[i - 1][j];
          } else {
            score -= b[i - 1][j];
          }
        }
        if (j!=0) {
          if (getState(state,i,j) == getState(state,i,j-1)) {
            score += c[i][j-1];
          } else {
            score -= c[i][j-1];
          }
        }
      }
    }
    return score;
  }

  for(int i=0;i<3;++i) {
    for(int j=0;j<3;++j) {
      int s=getState(state, i,j);
      if (s!=0) continue;
      if (maximize) {
        buffer = max(buffer, getMaxScore(setState(state,1, i, j),side+1));
      } else {
        buffer = min(buffer, getMaxScore(setState(state,2, i, j),side+1));
      }
    }
  }

  return buffer;
}

int main() {
  for(int i=0;i<2;++i) {
    for(int j=0;j<3;++j) {
      scanf("%d", &b[i][j]);
    }
  }
  for(int i=0;i<3;++i) {
    for(int j=0;j<2;++j) {
      scanf("%d", &c[i][j]);
    }
  }
  for(int i=0;i<2;++i) {
    for(int j=0;j<3;++j) {
      allscore += b[i][j] + c[j][i];
    }
  }
  int score = getMaxScore(0,0);
  printf("%d\n", (allscore + score) /2);
  printf("%d\n", (allscore - score) /2);
  return 0;
}