#892488 (C++14) No.5017 Tool-assisted Shooting

提出ソース

結果

問題	No.5017 Tool-assisted Shooting
ユーザー	ss
提出日時	2023-07-16 19:33:42
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	71 ms / 2,000 ms
コード長	13,577 bytes
コンパイル時間	1,942 ms
コンパイル使用メモリ	182,012 KB
実行使用メモリ	24,396 KB
スコア	3,883,310
平均クエリ数	1001.00
最終ジャッジ日時	2023-07-16 19:33:56
合計ジャッジ時間	13,138 ms
ジャッジサーバーID （参考情報）	judge13 / judge12
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	67 ms 23,400 KB
testcase_01	AC	65 ms 23,676 KB
testcase_02	AC	62 ms 23,844 KB
testcase_03	AC	68 ms 23,412 KB
testcase_04	AC	64 ms 24,324 KB
testcase_05	AC	64 ms 23,376 KB
testcase_06	AC	63 ms 24,276 KB
testcase_07	AC	64 ms 23,400 KB
testcase_08	AC	64 ms 23,640 KB
testcase_09	AC	68 ms 23,664 KB
testcase_10	AC	65 ms 23,256 KB
testcase_11	AC	62 ms 24,312 KB
testcase_12	AC	64 ms 24,360 KB
testcase_13	AC	65 ms 24,264 KB
testcase_14	AC	65 ms 23,652 KB
testcase_15	AC	63 ms 23,664 KB
testcase_16	AC	64 ms 23,568 KB
testcase_17	AC	65 ms 24,072 KB
testcase_18	AC	64 ms 23,664 KB
testcase_19	AC	64 ms 24,012 KB
testcase_20	AC	65 ms 23,388 KB
testcase_21	AC	65 ms 23,868 KB
testcase_22	AC	63 ms 23,544 KB
testcase_23	AC	62 ms 23,628 KB
testcase_24	AC	65 ms 24,024 KB
testcase_25	AC	65 ms 24,312 KB
testcase_26	AC	71 ms 23,640 KB
testcase_27	AC	65 ms 24,324 KB
testcase_28	AC	65 ms 23,400 KB
testcase_29	AC	63 ms 24,036 KB
testcase_30	AC	63 ms 24,048 KB
testcase_31	AC	64 ms 23,400 KB
testcase_32	AC	64 ms 23,556 KB
testcase_33	AC	66 ms 24,288 KB
testcase_34	AC	64 ms 23,400 KB
testcase_35	AC	65 ms 24,024 KB
testcase_36	AC	63 ms 24,348 KB
testcase_37	AC	65 ms 23,544 KB
testcase_38	AC	69 ms 23,532 KB
testcase_39	AC	65 ms 24,024 KB
testcase_40	AC	66 ms 24,264 KB
testcase_41	AC	64 ms 24,324 KB
testcase_42	AC	66 ms 24,288 KB
testcase_43	AC	64 ms 24,060 KB
testcase_44	AC	65 ms 23,424 KB
testcase_45	AC	65 ms 24,024 KB
testcase_46	AC	66 ms 23,532 KB
testcase_47	AC	64 ms 23,652 KB
testcase_48	AC	65 ms 24,324 KB
testcase_49	AC	64 ms 23,640 KB
testcase_50	AC	66 ms 23,388 KB
testcase_51	AC	65 ms 24,060 KB
testcase_52	AC	64 ms 23,388 KB
testcase_53	AC	65 ms 23,664 KB
testcase_54	AC	65 ms 23,436 KB
testcase_55	AC	67 ms 23,844 KB
testcase_56	AC	65 ms 23,436 KB
testcase_57	AC	66 ms 24,036 KB
testcase_58	AC	65 ms 24,180 KB
testcase_59	AC	66 ms 23,412 KB
testcase_60	AC	66 ms 24,396 KB
testcase_61	AC	64 ms 23,640 KB
testcase_62	AC	69 ms 24,228 KB
testcase_63	AC	64 ms 23,436 KB
testcase_64	AC	65 ms 23,556 KB
testcase_65	AC	67 ms 24,024 KB
testcase_66	AC	66 ms 23,844 KB
testcase_67	AC	64 ms 24,060 KB
testcase_68	AC	64 ms 24,060 KB
testcase_69	AC	66 ms 23,652 KB
testcase_70	AC	65 ms 24,036 KB
testcase_71	AC	66 ms 24,276 KB
testcase_72	AC	65 ms 24,240 KB
testcase_73	AC	65 ms 23,400 KB
testcase_74	AC	65 ms 23,436 KB
testcase_75	AC	65 ms 23,640 KB
testcase_76	AC	65 ms 23,856 KB
testcase_77	AC	65 ms 24,288 KB
testcase_78	AC	65 ms 24,360 KB
testcase_79	AC	65 ms 23,628 KB
testcase_80	AC	65 ms 23,568 KB
testcase_81	AC	65 ms 23,436 KB
testcase_82	AC	64 ms 24,060 KB
testcase_83	AC	64 ms 24,072 KB
testcase_84	AC	65 ms 23,436 KB
testcase_85	AC	65 ms 23,436 KB
testcase_86	AC	69 ms 23,664 KB
testcase_87	AC	65 ms 23,652 KB
testcase_88	AC	65 ms 24,072 KB
testcase_89	AC	65 ms 23,424 KB
testcase_90	AC	65 ms 23,388 KB
testcase_91	AC	66 ms 23,376 KB
testcase_92	AC	62 ms 23,448 KB
testcase_93	AC	64 ms 23,412 KB
testcase_94	AC	63 ms 23,640 KB
testcase_95	AC	64 ms 24,312 KB
testcase_96	AC	65 ms 23,844 KB
testcase_97	AC	64 ms 24,276 KB
testcase_98	AC	68 ms 23,400 KB
testcase_99	AC	64 ms 23,556 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

#ifndef __UTIL__
#define __UTIL__

#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REPR(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)

// Debug

template<class T>
void print_collection(std::ostream& out, T const& x);

template<class A>
std::ostream& operator<<(std::ostream& out, std::vector<A> const& x) { print_collection(out, x); return out; }
template<class A, size_t N>
std::ostream& operator<<(std::ostream& out, std::array<A, N> const& x) { print_collection(out, x); return out; }
template<class A>
std::ostream& operator<<(std::ostream& out, std::set<A> const& x) { print_collection(out, x); return out; }
template<class A>
std::ostream& operator<<(std::ostream& out, std::unordered_set<A> const& x) { print_collection(out, x); return out; }
template<class A, class B>
std::ostream& operator<<(std::ostream& out, std::map<A, B> const& x) { print_collection(out, x); return out; }


template<class A, class B>
std::ostream& operator<<(std::ostream& out, std::pair<A, B> const& x) {
  out << '(';
  out << x.first;
  out << ',';
  out << x.second;
  out << ')';
  return out;
}

template<class T, size_t... I>
void print_tuple(std::ostream& out, T const& a, std::index_sequence<I...>);
template<class... A>
std::ostream& operator<<(std::ostream& out, std::tuple<A...> const& x) {
  print_tuple(out, x, std::index_sequence_for<A...>{});
  return out;
}

template<class T, size_t... I>
void print_tuple(std::ostream& out, T const& a, std::index_sequence<I...>){
  using swallow = int[];
  out << '(';
  (void)swallow{0, (void(out << (I == 0? "" : ", ") << std::get<I>(a)), 0)...};
  out << ')';
}

template<class T>
void print_collection(std::ostream& out, T const& x) {
  int f = 0;
  out << '[';
  for(auto const& i: x) {
    out << (f++ ? "," : "");
    out << i;
  }
  out << "]";
}

static inline void d1_impl_seq() { std::cerr << "}"; }
template <class T, class... V>
void d1_impl_seq(T const& t, V const&... v) {
  std::cerr << t;
  if(sizeof...(v)) { std::cerr << ", "; }
  d1_impl_seq(v...);
}

static inline void d2_impl_seq() { }
template <class T, class... V>
void d2_impl_seq(T const& t, V const&... v) {
  std::cerr << " " << t;
  d2_impl_seq(v...);
}

#define D0(x) do { std::cerr << __FILE__ ":" << __LINE__ << ":" << __func__ <<  " " << x << std::endl; } while (0)
// #ifdef DEBUG
#define D1(x...) do {                                         \
    std::cerr << __LINE__ << "  {" << #x << "} = {";  \
    d1_impl_seq(x);                                           \
    std::cerr << std::endl << std::flush;                     \
  } while(0)
// #else
// #define D1(x...) {}
// #endif
#define D2(x...) do {                     \
    std::cerr << "!";                     \
    d2_impl_seq(x);                       \
    std::cerr << std::endl << std::flush; \
  } while(0)

using namespace std;

static constexpr int INF = 1<<30;

// #define NDEBUG

static std::vector<std::string> split(const std::string &s, char delim) {
  std::vector<std::string> elems;
  std::stringstream ss(s);
  std::string item;
  while (getline(ss, item, delim)) {
    if (!item.empty()) {
      elems.push_back(item);
    }
  }
  return elems;
}

struct XorShift {
  unsigned int x, y, z, w;
  double nL[65536];
  XorShift() { init(); }
  void init()
  {
    x = 314159265; y = 358979323; z = 846264338; w = 327950288;
    double n = 1 / (double)(2 * 65536);
    for (int i = 0; i < 65536; i++) {
      nL[i] = log(((double)i / 65536) + n);
    }
  }
  inline unsigned int next() { unsigned int t=x^x<<11; x=y; y=z; z=w; return w=w^w>>19^t^t>>8; }
  inline double nextLog() { return nL[next()&0xFFFF]; }
  inline int nextInt(int m) { return (int)(next()%m); } // [0, m)
  int nextInt(int min, int max) { return min+nextInt(max-min+1); } // [min, max]
  inline double nextDouble() { return (double)next()/((long long)1<<32); } // [0, 1]
};
XorShift rng;

template <typename T>
inline void rough_shuffle(vector<T>& lv) {
    int n = lv.size();
    for (int i = n; i > 0; --i) {
        int id = rng.nextInt(i);
        swap(lv[id], lv[i-1]);
    }
}

std::size_t calc_hash(std::vector<int> const& vec) {
  std::size_t seed = vec.size();
  for(auto& i : vec) {
    seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }
  return seed;
}

struct Timer {
  double LIMIT; // FIXME: 時間制限(s)
  Timer() : LIMIT(0.95) { reset(); }
  Timer(double limit) : LIMIT(limit) { reset(); }
	chrono::system_clock::time_point start;
	void reset() {
		start = chrono::system_clock::now();
	}
 
	double get() {
		auto end = chrono::system_clock::now();
		return chrono::duration_cast<chrono::milliseconds>(end - start).count()/1000.0;
	}
};

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

    std::vector<int> groups(int a) {
      // aと同じgroupに属する頂点のリストを返す
      std::vector<int> result;
      for (int i = 0; i < _n; ++i) {
        if (leader(a) != leader(i)) continue;
        result.push_back(i);
      }
      return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

}  // namespace atcoder

#endif

// #pragma GCC optimize("O3")

// #include "util/marathon/pos.hpp"
using namespace std;

int DX[9] = {0, 1, 0, -1, -1, -1, 1, 1, 0};
int DY[9] = {-1, 0, 1, 0, -1, 1, -1, 1, 0};

namespace pos {
    int W = 0, H = 0; // xとyのサイズ
    static constexpr int UP = 0;
    static constexpr int RIGHT = 1;
    static constexpr int DOWN = 2;
    static constexpr int LEFT = 3;
    bool isOrthogonal(int d1, int d2) {
      // UP, RIGHT, DOWN, LEFTのdir同士が直行しているか
      assert (0 <= d1 && d1 <= 3);
      assert (0 <= d2 && d2 <= 3);
      return (d1+d2) % 2;
    }
}

struct Pos {
  int x = -1, y = -1;
  Pos() {}
  Pos(int i): x(i%pos::W), y(i/pos::W) {}
  Pos(int x, int y): x(x), y(y) {}
  bool operator == (const Pos &other) const { 
    return (other.x == x) && (other.y == y);
  }
  bool operator != (const Pos &other) const { 
    return !((*this) == other);
  }
  int euclid(const Pos &other) const {
    return sqrt((x-other.x)*(x-other.x)+(y-other.y)*(y-other.y));
  }
  int manhattan(const Pos &other) const {
    return abs(x-other.x)+abs(y-other.y);
  }
  Pos to(int d) const { return Pos(x+DX[d],y+DY[d]); }
  int id() const { return y*pos::W+x; }
  bool outside() const {
    return x < 0 || x >= pos::W || y < 0 || y >= pos::H;
  }
  friend std::ostream& operator<<(std::ostream& os, const Pos &p) {
    os << '(' << p.x << ',' << p.y << ')';
    return os;
  }
};

namespace pos {
    Pos nullpos;
}

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using pii = pair<int, int>;

static constexpr int W = 25;
static constexpr int H = 60;

int turn_ = 0;
int LEFT = -1;
int STAY = 0;
int RIGHT = 1;
map<int, char> dir2char_ = {
  {-1,'L'},
  {0,'S'},
  {1,'R'},
};

namespace util {
  int getLDist(int fromx, int tox) {
    // 左方向の距離
    int dist = fromx-tox;
    if (dist < 0) dist += W;
    return dist;
  }
  int getRDist(int fromx, int tox) {
    int dist = tox-fromx;
    if (dist < 0) dist += W;
    return dist;
  }
  int to(int fromx, int tox) {
    if (fromx == tox) return STAY;
    int l = getLDist(fromx,tox);
    int r = getRDist(fromx,tox);
    if (l <= r) return LEFT;
    else return RIGHT;
  }
  Pos to(Pos p, int dir) {
    if (dir == LEFT) return Pos((p.x+W-1)%W, p.y+1);
    if (dir == STAY) return Pos(p.x, p.y+1);
    if (dir == RIGHT) return Pos((p.x+1)%W, p.y+1);
    assert(false);
  }
}

struct Enemy {
  int inithp = 0, hp = 0, power = -1;
  Enemy() {}
  Enemy(int h, int p): inithp(h), hp(h), power(p) {}
  int get_turn_to_kill(int level) {
    return (hp + level - 1) / level;
  }
  friend std::ostream& operator<<(std::ostream& os, const Enemy &e) {
    os << "[E]";
    os << "inithp = " << e.inithp;
    os << ",hp = " << e.hp;
    os << ",power = " << e.power;
    return os;
  }
};

using FieldType = array<array<Enemy, H>, W>; 

struct Field {
  int me = 12; // x座標
  int level = 1;
  int power_ = 0;
  FieldType arr;
  void step(int dir) {
    // 移動
    me += dir;
    if (me < 0) me += W;
    if (me >= W) me -= W;
    
    int y = getY(me);
    if (y != H) {
      arr[me][y].hp -= level;
      // 殺した敵を削除
      if (arr[me][y].hp <= 0) {
        power_ += arr[me][y].power;
        assert(power_ >= 0);
        arr[me][y] = Enemy();
      }
    }
    level = 1 + power_ / 100;
    assert(level > 0);

    REP(x,W) {
      REP3(y,1,H) {
        arr[x][y-1] = arr[x][y];
      }
      arr[x][H-1] = Enemy();
    }
  }

  bool exists(const Pos &p) const { return arr[p.x][p.y].power >= 0; }
  void setEnemy(int x, int hp, int power) {
    arr[x][H-1] = Enemy(hp, power);
  }
  friend std::ostream& operator<<(std::ostream& os, const Field &f) {
    REP(x,W) {
      REP(y,H) {
        int hp = f.arr[x][y].hp;
        if (hp >= 100) os << hp/100 << '+';
        else {
          os << hp;
          if (hp < 10) os << ' ';
        }
      }
      os << '\n';
    }
    return os;
  }
  int getY(int x) { // 一番近い敵のy座標
    REP(y,H) {
      if (exists(Pos(x,y))) return y;
    }
    return H;
  }
};
Field field_;
double BAD = -1000000000;


struct State {
  Field field;
  double evaluateKillEnemy(int x) {
    // xにいる一番近い敵を殺した場合の良さを計算
    // 高いほど良い
    int me = field.me;
    double ret = 0;
    int l = util::getLDist(me, x);
    int r = util::getRDist(me, x);
    int dir = util::to(me, x);
    int turn_to_reach = min(l, r);
    if (turn_to_reach == 0) turn_to_reach = 1;
    Pos p(me,0);
    REP(i,turn_to_reach) {
      Pos np = util::to(p,dir);
      Pos np2 = Pos(np.x,np.y+1);
      // D1(me,x,np,turn_to_reach);
      // D1(np);
      if (field.exists(np) || field.exists(np2)) {
        // D1(turn_,me,np,x);
        return -4; // 移動中に敵にぶつかって死ぬ
      }
      p = np;
    }
    int y = field.getY(x);
    if (y == H) {
      return -1; // 敵がいない
    }
    if (y-turn_to_reach <= 1) return -2; // 先に敵がいなくなる
    Enemy enemy = field.arr[x][y];
    int damage = (y-turn_to_reach-1)*field.level;
    if (damage < enemy.hp) return -3; // 敵を殺しきれない
    int turn_to_kill = enemy.get_turn_to_kill(field.level);
    return (double)enemy.power/(turn_to_kill+turn_to_reach);
  }
};


bool readInput() {
  int n;
  std::cin >> n;
  if(n == -1) return true;
  if (n >= W) return true;
  assert(n < W);
  for(int i = 0; i < n; i++) {
    int h, p, x;
    std::cin >> h >> p >> x;
    // D1(n, h, p, x);
    field_.setEnemy(x, h, p);
  }
  return false;
}

void writeOutput(int dir) {
  cout << dir2char_[dir] << endl;
}

void test () {
  D1(util::to(10,10));
  D1(util::to(10,11));
  D1(util::to(11,10));
  D1(util::to(1,23));
  D1(util::to(23,1));
}

int solve (int turn) {
  State s;
  s.field = field_;
  double best = BAD;
  int bestx = -1;
  REP(x,W) {
    double score = s.evaluateKillEnemy(x);
    // D1(turn, x, score);
    if (score > best) {
      bestx = x;
      best = score;
    }
  }

  // D1(turn,s.field.level,s.field.me,bestx,best,s.field.getY(bestx));
  // cerr << s.field;
  // output
  int dir = STAY;
  if (bestx != -1) {
    dir = util::to(s.field.me, bestx);
  }
  return dir;
}



int main() 
{
  pos::W = 25; pos::H = 60;
#ifdef LOCAL
  std::string s;
  getline(cin,s);
#endif
  writeOutput(STAY);
  REP(turn,1000) {
    turn_ ++;
    if (readInput()) return 0;
    int dir = solve(turn);
    field_.step(dir);
    writeOutput(dir);
    // if (turn > 0) return 0;
    // if (turn > 284) return 0;
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード