MM148 last submit

Frogs.cpp

#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <vector>

using namespace std;
typedef long long ll;

const ll CYCLE_PER_SEC = 2700000000;
double TIME_LIMIT = 9.8;

unsigned long long xor128() {
  static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123;
  unsigned long long rt = (rx ^ (rx << 11));
  rx = ry;
  ry = rz;
  rz = rw;
  return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
}

unsigned long long int get_cycle() {
  unsigned int low, high;
  __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
  return ((unsigned long long int) low) | ((unsigned long long int) high << 32);
}

double get_time(unsigned long long int begin_cycle) {
  return (double) (get_cycle() - begin_cycle) / CYCLE_PER_SEC;
}

const int MAX_H = 30;
const int MAX_W = 30;
const int GRID_SIZE = 32;
const int MAX_T = 1000;
const int MAX_FROG_NUM = 5;

int calc_z(int y, int x) {
  return y * GRID_SIZE + x;
}

const char OUTSIDE = 'X';
const char BEACH = '#';
const char WATER = '.';
const char LOG = '=';
const char SLOG = 'S';
const char VLOG = 'V';
const char WLOG = 'W';
const char ZLOG = 'Z';
const char FROG = '@';
const char COIN = 'o';

const int DZ[5] = {-GRID_SIZE, 1, GRID_SIZE, -1, 0};
const string DS[4] = {"U", "R", "D", "L"};
const int RIGHT = 1;
const int LEFT = 3;
const int STAY = 4;
const int EXP_TIME = 6;

int H;
int W;
int F;
int KL;
int KW;
double PC;
int g_flow_directions[GRID_SIZE];
bool g_is_danger_line[GRID_SIZE];
int g_frog_positions[MAX_FROG_NUM];
int g_dead_time[MAX_FROG_NUM];
int g_coin_ids[MAX_T + 1][GRID_SIZE * GRID_SIZE];
int g_coin_values[GRID_SIZE];
char g_grid[MAX_T + 1][GRID_SIZE * GRID_SIZE];
int g_slide_counter[MAX_T + 1][GRID_SIZE * GRID_SIZE];
short g_positions[EXP_TIME + 1][MAX_FROG_NUM];
int g_schedule[MAX_T + 1][MAX_FROG_NUM];
ll g_visited_each_time[MAX_T + 1][GRID_SIZE * GRID_SIZE];
ll g_visited[GRID_SIZE * GRID_SIZE];
ll g_checked[GRID_SIZE * GRID_SIZE];
ll g_vid;
ll g_cid;

struct Move {
  int z;
  int dir;

  Move(int z = -1, int dir = 0) {
    this->z = z;
    this->dir = dir;
  }

  string to_str() {
    int y = z / GRID_SIZE;
    int x = z % GRID_SIZE;
    string d = DS[dir];

    return to_string(y - 1) + " " + to_string(x - 1) + " " + d;
  }
};

class Frogs {
public:
  void load_data() {
    memset(g_is_danger_line, false, sizeof(g_is_danger_line));
    memset(g_checked, -1, sizeof(g_checked));
    memset(g_visited, -1, sizeof(g_visited));
    memset(g_visited_each_time, -1, sizeof(g_visited_each_time));
    g_cid = 0;
    g_vid = 0;

    for (int t = 0; t < MAX_T; ++t) {
      for (int fid = 0; fid < MAX_FROG_NUM; ++fid) {
        g_schedule[t][fid] = STAY;
      }
    }

    cin >> H >> W >> F >> KL >> KW >> PC;

    fprintf(stderr, "H = %d\n", H);
    fprintf(stderr, "W = %d\n", W);
    fprintf(stderr, "F = %d\n", F);
    fprintf(stderr, "KL = %d\n", KL);
    fprintf(stderr, "KW = %d\n", KW);
    fprintf(stderr, "PC = %f\n", PC);

    for (int y = 0; y < GRID_SIZE; ++y) {
      for (int x = 0; x < GRID_SIZE; ++x) {
        int z = calc_z(y, x);

        for (int t = 0; t < MAX_T; ++t) {
          if (y == 1 && 1 <= x && x <= W) {
            g_grid[t][z] = BEACH;
          } else if (y == 0 || y >= H + 1 || x == 0 || x >= W + 1) {
            g_grid[t][z] = OUTSIDE;
          }
        }
      }
    }

    g_flow_directions[1] = STAY;
    for (int y = 2; y <= H; ++y) {
      char dir;
      cin >> dir;

      if (dir == '>') {
        g_flow_directions[y] = RIGHT;
      } else {
        g_flow_directions[y] = LEFT;
      }
    }

    for (int y = 2; y <= H; ++y) {
      bool safe = false;

      for (int d = -1; d <= 1; ++d) {
        int ny = max(1, min(y + d, H));
        safe |= (g_flow_directions[y] != g_flow_directions[ny]);
      }

      if (not safe) {
        g_is_danger_line[y] = true;
      }
    }

    memset(g_coin_values, 0, sizeof(g_coin_values));
    for (int y = 2; y <= H; ++y) {
      if (not is_ez() && g_is_danger_line[y]) {
        g_coin_values[y] = 1 * y;
      } else if (y < H / 4) {
        g_coin_values[y] = 10 * y;
      } else if (y < H / 2) {
        g_coin_values[y] = 30 * y;
      } else {
        g_coin_values[y] = 100 * y;
      }
    }
  }

  int read_input(int turn) {
    memset(g_frog_positions, -1, sizeof(g_frog_positions));
    memset(g_coin_ids, -1, sizeof(g_coin_ids));
    int frog_id = 0;
    int coin_id = 0;

    for (int y = 1; y <= H; ++y) {
      for (int x = 1; x <= W; ++x) {
        int z = calc_z(y, x);
        cin >> g_grid[turn][z];

        if (g_grid[turn][z] == FROG) {
          g_frog_positions[frog_id] = z;
          ++frog_id;
        }
        if (g_grid[turn][z] == COIN) {
          g_coin_ids[turn][z] = coin_id;
          ++coin_id;
        }
      }
    }

    int water_counter[GRID_SIZE];
    memset(water_counter, 0, sizeof(water_counter));
    int log_counter[GRID_SIZE];
    memset(log_counter, 0, sizeof(log_counter));
    for (int y = 2; y <= H; ++y) {
      int f_dir = g_flow_directions[y];
      int cz = (f_dir == RIGHT) ? calc_z(y, 1) : calc_z(y, W);

      if (g_grid[turn][cz] == WATER) {
        while (g_grid[turn][cz] == WATER) {
          ++water_counter[y];
          cz += DZ[f_dir];
        }
      } else {
        while (g_grid[turn][cz] == LOG) {
          ++log_counter[y];
          cz += DZ[f_dir];
        }
      }

      if (g_is_danger_line[y]) {
        int from = -1;
        bool connect_up = false;
        bool connect_down = false;

        for (int x = 1; x <= W + 1; ++x) {
          int z = calc_z(y, x);

          if (g_grid[turn][z] == WATER || g_grid[turn][z] == OUTSIDE) {
            if (from != -1) {
              for (int nx = from; nx < x; ++nx) {
                int nz = calc_z(y, nx);
                if ((!connect_up || !connect_down) && g_grid[turn][nz] != COIN) {
                  g_grid[turn][nz] = SLOG;
                }
              }
            }

            from = -1;
            connect_up = false;
            connect_down = false;
          } else {
            if (from == -1) from = x;
            int uz = z - GRID_SIZE;
            int dz = z + GRID_SIZE;

            connect_up |= (g_grid[turn][uz] != WATER);
            connect_down |= (g_grid[turn][dz] != WATER);
          }
        }
      }
    }

    int end_at = min(turn + EXP_TIME, MAX_T);
    for (int t = turn + 1; t <= end_at; ++t) {
      for (int y = 2; y <= H; ++y) {
        for (int x = 1; x <= W; ++x) {
          int z = calc_z(y, x);

          if (g_flow_directions[y] == RIGHT) {
            if (x == 1) {
              if (t == turn + 1 && water_counter[y] == KW) {
                g_grid[t][z] = LOG;
              } else if (t == turn + 1 && KW >= 2 && water_counter[y] == KW - 1) {
                g_grid[t][z] = VLOG;
              } else if (t == turn + 2 && log_counter[y] == KL && KW == 1) {
                g_grid[t][z] = LOG;
              } else if (t == turn + 2 && log_counter[y] == KL && KW == 2) {
                g_grid[t][z] = VLOG;
              } else {
                g_grid[t][z] = WATER;
              }
            } else {
              if (g_grid[t - 1][z - 1] == FROG) {
                g_grid[t][z] = LOG;
              } else {
                g_grid[t][z] = g_grid[t - 1][z - 1];
                g_coin_ids[t][z] = g_coin_ids[t - 1][z - 1];
              }
            }
          } else {
            if (x == W) {
              if (t == turn + 1 && water_counter[y] == KW) {
                g_grid[t][z] = LOG;
              } else if (t == turn + 1 && KW >= 2 && water_counter[y] == KW - 1) {
                g_grid[t][z] = VLOG;
              } else if (t == turn + 2 && log_counter[y] == KL && KW == 1) {
                g_grid[t][z] = LOG;
              } else if (t == turn + 2 && log_counter[y] == KL && KW == 2) {
                g_grid[t][z] = VLOG;
              } else {
                g_grid[t][z] = WATER;
              }
            } else {
              if (g_grid[t - 1][z + 1] == FROG) {
                g_grid[t][z] = LOG;
              } else {
                g_grid[t][z] = g_grid[t - 1][z + 1];
                g_coin_ids[t][z] = g_coin_ids[t - 1][z + 1];
              }
            }
          }
        }
      }
    }

    for (int t = turn; t <= end_at; ++t) {
      for (int y = 2; y <= H; ++y) {
        int s_cnt = 0;

        if (g_flow_directions[y] == RIGHT) {
          for (int x = 1; x <= W; ++x) {
            int z = calc_z(y, x);
            g_slide_counter[t][z] = s_cnt;

            if (g_grid[t][z] == WATER) {
              s_cnt = 0;
            } else {
              ++s_cnt;
            }
          }
        } else if (g_flow_directions[y] == LEFT) {
          for (int x = W; x >= 1; --x) {
            int z = calc_z(y, x);
            g_slide_counter[t][z] = s_cnt;

            if (g_grid[t][z] == WATER) {
              s_cnt = 0;
            } else {
              ++s_cnt;
            }
          }
        }
      }
    }

    int elapsed_time;
    cin >> elapsed_time;

    return elapsed_time;
  }

  void run() {
    load_data();

    for (int turn = 0; turn < MAX_T; ++turn) {
      int elapsed_time = read_input(turn);
      search_best_moves_by_sa(turn, TIME_LIMIT / MAX_T);

      vector <Move> moves;
      for (int fid = 0; fid < F; ++fid) {
        int z = g_frog_positions[fid];
        int dir = g_schedule[turn][fid];
        if (dir == STAY) continue;

        moves.push_back(Move(z, dir));
      }

      output(turn, moves);

      if (turn == MAX_T - 1) {
        fprintf(stderr, "turn: %d, elapsed_time: %d\n", turn, elapsed_time);
      }
    }
  }

  int random_int(int from, int to) {
    return from + xor128() % (to - from + 1);
  }

  void search_best_moves_by_sa(int cur_turn, double time_limit = 0.01) {
    ll start_cycle = get_cycle();

    int cur_score = calc_score_full(cur_turn);
    int best_score = cur_score;
    int best_schedule[MAX_T + 1][MAX_FROG_NUM];
    int cur_dead_time[MAX_FROG_NUM];
    short cur_positions[EXP_TIME + 1][MAX_FROG_NUM];
    memcpy(best_schedule, g_schedule, sizeof(best_schedule));
    memcpy(cur_dead_time, g_dead_time, sizeof(cur_dead_time));
    memcpy(cur_positions, g_positions, sizeof(cur_positions));

    double cur_time = get_time(start_cycle);
    double total_diff = 0.0;
    double t = 0.1;
    ll R = 100000000;
    int try_count = 0;
    int end_at = min(cur_turn + EXP_TIME, MAX_T);
    int loop_cnt = 0;

    while (cur_time < time_limit) {
      cur_time = get_time(start_cycle);
      double remain_time = (time_limit - cur_time) / time_limit;

      int fid = loop_cnt % F;
      ++loop_cnt;
      int to = (cur_dead_time[fid] == -1) ? end_at - 1 : cur_dead_time[fid];
      assert(cur_turn <= to);
      int time, dir, nz;
      int limit = 100;
      do {
        time = random_int(cur_turn, to);
        int cz = cur_positions[time - cur_turn][fid];
        int cy = cz / GRID_SIZE;
        if (g_is_danger_line[cy]) {
          dir = random_int(0, 3);
        } else {
          dir = random_int(0, 4);
        }
        nz = cur_positions[time - cur_turn][fid] + DZ[dir];
        --limit;
      } while ((dir == g_schedule[time][fid] || g_grid[time][nz] == WATER || g_grid[time][nz] == OUTSIDE) &&
               limit >= 0);
      if (limit < 0) continue;

      int prev_dir = g_schedule[time][fid];
      g_schedule[time][fid] = dir;

      int score = calc_score_full(cur_turn);
      double diff_score = score - cur_score;
      total_diff += fabs(diff_score);

      if (diff_score > 0 || (xor128() % R < R * exp(diff_score / (t * sqrt(remain_time))))) {
        cur_score = score;
        memcpy(cur_dead_time, g_dead_time, sizeof(cur_dead_time));
        memcpy(cur_positions, g_positions, sizeof(cur_positions));

        if (best_score < score) {
          best_score = score;
          memcpy(best_schedule, g_schedule, sizeof(best_schedule));
        }
      } else {
        g_schedule[time][fid] = prev_dir;
      }

      ++try_count;
      double average_diff = total_diff / try_count;
      t = 1.4 * remain_time * average_diff;
    }

    memcpy(g_schedule, best_schedule, sizeof(g_schedule));

    if (cur_turn % 20 == 0) {
      fprintf(stderr, "turn: %d, try_count: %d, best_score: %d\n", cur_turn, try_count, best_score);
    }
  }

  bool is_ez() {
    if (KW == 1) {
      return true;
    } else {
      return false;
    }
  }

  int calc_score_full(int cur_turn) {
    ++g_vid;
    ++g_cid;

    int position_score = 0;
    int coin_score[F];
    int end_at = min(cur_turn + EXP_TIME, MAX_T);
    int cur_positions[MAX_FROG_NUM];
    double remain = (MAX_T - cur_turn - 2 * H) * 1.0 / (4 * H);
    if (KW <= 2) {
      remain = (MAX_T - cur_turn - 2 * H) * 1.0 / (3 * H);
    } else if (KW == 5 && KL <= 5) {
      remain = (MAX_T - cur_turn - 2 * H) * 1.0 / (5 * H);
    }
    int limit_y = H * remain;
    memset(coin_score, 0, sizeof(coin_score));
    memcpy(cur_positions, g_frog_positions, sizeof(cur_positions));
    memset(g_dead_time, -1, sizeof(g_dead_time));
    bool is_dead[MAX_FROG_NUM] = {false, false, false, false, false};

    for (int fid = 0; fid < F; ++fid) {
      int z = cur_positions[fid];
      g_visited_each_time[cur_turn][z] = g_vid;
      g_positions[0][fid] = z;
    }

    for (int t = cur_turn; t < end_at; ++t) {
      for (int fid = 0; fid < F; ++fid) {
        if (is_dead[fid]) continue;

        int z = cur_positions[fid];
        int y = z / GRID_SIZE;
        int dir = g_schedule[t][fid];
        int nz = z + DZ[dir];
        if (g_grid[t][nz] == WATER) {
          nz = z;
        } else if (g_grid[t][nz] == OUTSIDE) {
          nz = z;
        } else if (g_visited_each_time[t][nz] == g_vid && dir != STAY) {
          nz = z;
        } else if (g_grid[t][nz] == VLOG && g_slide_counter[t][z] < 1) {
          nz = z;
        }
        int ny = nz / GRID_SIZE;
        int nx = nz % GRID_SIZE;
        int f_dir = g_flow_directions[ny];
        int nnz = nz + DZ[f_dir];
        cur_positions[fid] = nnz;

        if (g_grid[t][nnz] == OUTSIDE) {
          g_dead_time[fid] = t;
          is_dead[fid] = true;
          coin_score[fid] = -9999 + (t - cur_turn) * 20;
          continue;
        }

        if (remain < 1.0 && g_grid[t][nz] == SLOG) {
          position_score -= 99;
        }

        g_visited_each_time[t][z] = -1;
        g_visited_each_time[t][nz] = g_vid;

        if (g_flow_directions[ny] == RIGHT && nx >= W - W / 3) {
          position_score -= 1;
        }
        if (g_flow_directions[ny] == LEFT && nx <= W / 3) {
          position_score -= 1;
        }

        if (ny > limit_y) {
          position_score += (H - ny + 1);

          if (ny == 1) {
            position_score += 9999;
          }
        } else {
          if (cur_turn < 3 * H) {
            position_score += (end_at - t) * 10 * ny;
          } else {
            position_score += (end_at - t) * ny;
          }

          if (g_is_danger_line[ny]) {
            if (g_flow_directions[ny] == RIGHT && W - W / 4 <= nx) {
              position_score -= (end_at - t) * 10;
              if (t == end_at - 1) {
                position_score -= 9999;
              }
            }
            if (g_flow_directions[ny] == LEFT && nx <= W / 4) {
              position_score -= (end_at - t) * 10;
              if (t == end_at - 1) {
                position_score -= 9999;
              }
            }
          }
        }

        if (g_grid[t][nz] == COIN && ny <= limit_y) {
          int coin_id = g_coin_ids[t][nz];
          assert(coin_id != -1);

          if (g_checked[coin_id] != g_cid) {
            coin_score[fid] += (end_at - t) * g_coin_values[ny];
            g_checked[coin_id] = g_cid;
          }
        }
      }

      for (int fid = 0; fid < F; ++fid) {
        int z = cur_positions[fid];
        int y = z / GRID_SIZE;
        int x = z % GRID_SIZE;
        int uz = z + DZ[0];
        int rz = z + DZ[1];
        int dz = z + DZ[2];
        int lz = z + DZ[3];
        g_visited_each_time[t + 1][z] = g_vid;
        g_positions[t + 1 - cur_turn][fid] = z;

        if (g_is_danger_line[y]) {
          if (g_flow_directions[y] == RIGHT) {
            if (x == W) {
              is_dead[fid] = true;
              coin_score[fid] = -99999;
            } else if (x >= W - 3 &&
                       g_grid[t + 1][uz] == WATER && g_grid[t + 1][dz] == WATER &&
                       g_grid[t + 1][lz] == WATER) {
              is_dead[fid] = true;
              coin_score[fid] = -99999;
            } else if (x >= W - 5 &&
                       g_grid[t + 1][uz] == WATER && g_grid[t + 1][dz] == WATER && g_grid[t + 1][lz] == WATER &&
                       g_grid[t + 1][uz + 1] == WATER && g_grid[t + 1][dz + 1] == WATER) {
              is_dead[fid] = true;
              coin_score[fid] = -99999;
            }
          }
          if (g_flow_directions[y] == LEFT) {
            if (x == 1) {
              is_dead[fid] = true;
              coin_score[fid] = -99999;
            } else if (x <= 3 &&
                       g_grid[t + 1][uz] == WATER && g_grid[t + 1][dz] == WATER &&
                       g_grid[t + 1][rz] == WATER) {
              is_dead[fid] = true;
              coin_score[fid] = -99999;
            } else if (x <= 5 &&
                       g_grid[t + 1][uz] == WATER && g_grid[t + 1][dz] == WATER && g_grid[t + 1][rz] == WATER &&
                       g_grid[t + 1][uz - 1] == WATER && g_grid[t + 1][dz - 1] == WATER) {
              is_dead[fid] = true;
              coin_score[fid] = -99999;
            }
          }
        }
      }
    }

    for (int fid = 0; fid < F; ++fid) {
      position_score += coin_score[fid];
    }

    return position_score;
  }

  void output(int turn, vector <Move> &moves) {
    ++g_vid;
    for (int fid = 0; fid < F; ++fid) {
      int z = g_frog_positions[fid];
      g_visited[z] = g_vid;
    }

    vector <Move> new_moves;
    for (Move &move : moves) {
      int z = move.z;
      int nz = z + DZ[move.dir];
      if (g_grid[turn][nz] == WATER) continue;
      if (g_grid[turn][nz] == OUTSIDE) continue;
      if (g_visited[nz] == g_vid) continue;

      new_moves.push_back(move);
      g_visited[z] = -1;
      g_visited[nz] = g_vid;
    }

    cout << new_moves.size() << endl;
    for (Move &move : new_moves) {
      cout << move.to_str() << endl;
    }
  }

  void show_grid(int turn) {
    for (int y = 0; y <= H + 1; ++y) {
      for (int x = 0; x <= W + 1; ++x) {
        int z = calc_z(y, x);

        fprintf(stderr, "%c", g_grid[turn][z]);
      }
      fprintf(stderr, "\n");
    }
  }
};

int main() {
  Frogs frogs;
  frogs.run();

  return 0;
}