Skip to content

Instantly share code, notes, and snippets.

@riantkb

riantkb/Answer.cpp

Created December 7, 2016 07:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save riantkb/5278f53767bcce53e903cf74587415ec to your computer and use it in GitHub Desktop.
Save riantkb/5278f53767bcce53e903cf74587415ec to your computer and use it in GitHub Desktop.
Download ZIP
ハルコン2016でのrian_tkbのコード
Raw
Answer.cpp
//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright Copyright (c) 2016 HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください
//------------------------------------------------------------------------------
#include "Answer.hpp"
#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <random>
// 乱数試行回数
#define looplim 240
/// プロコン問題環境を表します。
namespace hpc {
//------------------------------------------------------------------------------
/// Answer クラスのコンストラクタです。
///
/// @note ここにインスタンス生成時の処理を書くことができますが、何も書かなくても構いません。
Answer::Answer()
{
}
//------------------------------------------------------------------------------
/// Answer クラスのデストラクタです。
///
/// @note ここにインスタンス破棄時の処理を書くことができますが、何も書かなくても構いません。
Answer::~Answer()
{
}
// 隕石の個数
int n;
// 各ビーム発射ターンにおける宇宙船の座標 (一部不使用)
Vector2 poss[50];
// 各ターンにおける宇宙船の座標
Vector2 pos[2000];
// 各ビームの発射先
Vector2 tars[50];
const double speed = 1.99999;
const double eps = 0.0001;
const double epsL = 0.001;
inline int bitcnt(int a) {
int bits = a;
bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}
// まだ訪れていない隕石のうち一番近いものを返す
inline int get1st(const Stage& aStage, const Vector2& spos, int visited) {
double min1 = 3000;
int minid1 = -1;
for (int i = 0; i < n; ++i) {
if ((visited >> i) & 1) continue;
double dis = spos.dist(aStage.asteroid(i).pos()) - aStage.asteroid(i).radius();
if (dis < min1) {
min1 = dis;
minid1 = i;
}
}
return minid1;
}
// まだ訪れていない隕石のうち二番目に近いものを返す
inline int get2nd(const Stage& aStage, const Vector2& spos, int visited) {
double min1 = 3000, min2 = 3000;
int minid1 = -1, minid2 = -1;
for (int i = 0; i < n; ++i) {
if ((visited >> i) & 1) continue;
double dis = spos.dist(aStage.asteroid(i).pos()) - aStage.asteroid(i).radius();
if (dis < min1) {
min2 = min1;
minid2 = minid1;
min1 = dis;
minid1 = i;
}
else if (dis < min2) {
min2 = dis;
minid2 = i;
}
}
return minid2;
}
// まだ訪れていない隕石のうち三番目に近いものを返す
inline int get3rd(const Stage& aStage, const Vector2& spos, int visited) {
double min1 = 3000, min2 = 3000, min3 = 3000;
int minid1 = -1, minid2 = -1, minid3 = -1;
for (int i = 0; i < n; ++i) {
if ((visited >> i) & 1) continue;
double dis = spos.dist(aStage.asteroid(i).pos()) - aStage.asteroid(i).radius();
if (dis < min1) {
min3 = min2;
minid3 = minid2;
min2 = min1;
minid2 = minid1;
min1 = dis;
minid1 = i;
}
else if (dis < min2) {
min3 = min2;
minid3 = minid2;
min2 = dis;
minid2 = i;
}
else if (dis < min3) {
min3 = dis;
minid3 = i;
}
}
return minid3;
}
// まだ訪れていない隕石のうちk番目に近いものを返す (k <= 3)
inline int getnext(const Stage& aStage, const Vector2& spos, int visited, int k) {
if (k == 3) {
return get3rd(aStage, spos, visited);
}
if (k == 2) {
return get2nd(aStage, spos, visited);
}
return get1st(aStage, spos, visited);
}
//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出されます。
///
/// @note ここで、各ステージに対して初期処理を行うことができます。
///
/// @param[in] aStage 現在のステージ。
void Answer::init(const Stage& aStage)
{
std::mt19937 mt(0);
n = aStage.asteroidCount();
int bestok = 1300;
int bestdep = -1;
Vector2 posstmp[looplim][50];
Vector2 postmp[looplim][2000];
Vector2 tarstmp[looplim][50];
for (int loop = 0; loop < looplim; ++loop) {
Vector2 spos = aStage.ship().pos();
std::vector<int> poscanshoots[50];
std::vector<Vector2> posshoottar[50];
int vis[30];
int visturn[30];
for (int i = 0; i < 30; ++i) {
visturn[i] = 1900;
}
int turn = 0;
int visited = 0;
postmp[loop][0] = spos;
// 経過ターンが今出ている最良のターン数+40以上となった場合は, それ以降に訪れる隕石を決めても意味がないのでループを打ち切る
for (int i = 0; i < n && turn < bestok + 40; ++i) {
// 次に目指す隕石を今いる位置から何番目に近いものにするかを乱数で決める
// 一番近い隕石になる確率 : 2/3
// 二番目に近い隕石になる確率 : 2/9
// 三番目に近い隕石になる確率 : 1/9
int minid = getnext(aStage, spos, visited, Math::Min(mt() % 3 > 0 ? 1 : (mt() % 3 > 0 ? 2 : 3), n - i));
vis[i] = minid;
visited |= 1 << minid;
// dir : 向かうべき方向の単位ベクトル
Vector2 dir = (aStage.asteroid(minid).pos() - spos).unit();
for (int j = turn + 1; j < bestok + 40; ++j) {
if (j % 41 == 0) {
// レーザーを撃つので動けない
postmp[loop][j] = postmp[loop][j - 1];
continue;
}
postmp[loop][j] = postmp[loop][j - 1] + dir * speed;
if ((j + 1) % 41 == 0) {
posstmp[loop][j / 41] = postmp[loop][j];
}
// 目標の隕石にぶつかったという判定
if (aStage.asteroid(minid).pos().dist(postmp[loop][j]) + eps < aStage.asteroid(minid).radius()) {
visturn[i] = j;
// 今までは隕石の中心に向かって進んでいたが, 実際には隕石にかすればいいので, 最後の一歩だけ少し曲げる
// 曲げる方向は, まだ訪れていない一番近い隕石への距離が一番短くなるような方向
//// あまり意味がなかった気がする
//// 最後にちょっと曲げるなら最初から斜めに行ってもよかった感
Vector2 pos1 = postmp[loop][j];
double dis = postmp[loop][j - 1].dist(aStage.asteroid(minid).pos());
// 曲げる角度を, 余弦定理からのcosの逆関数で求める
double rr = aStage.asteroid(minid).radius() - epsL;
double cos = (dis * dis + speed * speed - rr * rr) / (2 * dis * speed);
if (cos < eps - 1 || cos > 1 - eps) break;
double rad = Math::ACos(cos);
if (rad < eps) break;
Vector2 pos2 = postmp[loop][j - 1] + dir.getRotatedRad(rad) * speed;
Vector2 pos3 = postmp[loop][j - 1] + dir.getRotatedRad(-rad) * speed;
double d1 = get1st(aStage, pos1, visited);
double d2 = get1st(aStage, pos2, visited);
double d3 = get1st(aStage, pos3, visited);
if (d2 < d1 && d2 < d3) {
postmp[loop][j] = pos2;
}
else if (d3 < d1) {
postmp[loop][j] = pos3;
}
if ((j + 1) % 41 == 0) {
posstmp[loop][j / 41] = postmp[loop][j];
}
break;
}
}
turn = Math::Min(visturn[i], bestok + 60);
spos = postmp[loop][turn];
}
// 各ビーム発射ターンにおける宇宙船の座標がわかったので, そこからどういう隕石の集合が落とせるのかを全探索する
// ビームを発射する座標が決まっている場合, いずれかの隕石に接するように撃つビームだけを考えると十分
// よって, ある点からビームを発射して落とせる隕石の集合を列挙するのにかかる計算量は O(n^2)
int lim = (turn + 1) / 41 + 1;
for (int i = 0; i < lim; ++i) {
for (int j = 0; j < n; ++j) {
// ビームを発射する座標と目標とする隕石の中心の座標が10未満の場合, すでにその隕石は破壊しているはずなのでその隕石を目標に定める必要がない
if (posstmp[loop][i].squareDist(aStage.asteroid(j).pos()) < 99) continue;
// sinの逆関数で接線の角度を求める
double dis = posstmp[loop][i].dist(aStage.asteroid(j).pos());
double rad = std::asin((aStage.asteroid(j).radius() - epsL) / dis);
Vector2 dir = aStage.asteroid(j).pos() - posstmp[loop][i];
Vector2 tar1 = posstmp[loop][i] + dir.getRotatedRad(rad);
Vector2 tar2 = posstmp[loop][i] + dir.getRotatedRad(-rad);
// ビームが他の隕石にも当たるかどうかUtilの関数を用いて調べる
int cs1 = 0, cs2 = 0;
if (posstmp[loop][i].squareDist(tar1) > 1) {
for (int k = 0; k < n; ++k) {
if (Util::CanShootAsteroid(posstmp[loop][i], tar1, aStage.asteroid(k).pos(), aStage.asteroid(k).radius() - eps)) {
cs1 |= 1 << k;
}
}
}
if (posstmp[loop][i].squareDist(tar2) > 1) {
for (int k = 0; k < n; ++k) {
if (Util::CanShootAsteroid(posstmp[loop][i], tar2, aStage.asteroid(k).pos(), aStage.asteroid(k).radius() - eps)) {
cs2 |= 1 << k;
}
}
}
// ビームが他の隕石にも当たった場合のみ記憶しておく
if (cs1 > (1 << j)) {
poscanshoots[i].emplace_back(cs1);
posshoottar[i].emplace_back(tar1);
}
if (cs2 > (1 << j) && cs1 != cs2) {
poscanshoots[i].emplace_back(cs2);
posshoottar[i].emplace_back(tar2);
}
}
}
// 決めた宇宙船のルートでのクリア可能ターン数を二分探索
int ng = 0, ok = bestok + 10;
while (ng < ok - 1) {
int m = (ng + ok) >> 1;
// そのターンまででまだぶつかってない(破壊してない)隕石の集合を求めておく
int rem = (1 << n) - 1;
int remcnt = n;
for (int i = 0; i < n && visturn[i] <= m; ++i) {
rem ^= 1 << vis[i];
--remcnt;
}
// そのターン数までのビーム発射座標におけるビーム発射により, まだぶつかっていない隕石全てを落とせるかを判定する
// 判定方法は, 落とせる隕石の個数が多い順に貪欲にビームを撃つ, なので嘘貪欲
//// マッチング問題っぽくて厳密に解きたくなかった
int shootposcnt = Math::Min(m / 41, lim);
int used = 0;
Vector2 tarstemp[50];
int okflg = 0;
for (int i = 0; i < shootposcnt; ++i) {
// 各点から任意の隕石がビームにより落とせるので, 残った隕石の数が残りビーム発射回数以下になった時点で全て落とせることがわかる
if (shootposcnt - i >= remcnt) {
okflg = 1;
break;
}
int max = 1, maxpos = -1, maxshoot = 0;
Vector2 maxtar;
for (int j = 0; j < shootposcnt; ++j) {
if ((used >> j) & 1) continue;
for (size_t k = 0; k < poscanshoots[j].size(); ++k) {
int bc = bitcnt(poscanshoots[j][k] & rem);
if (bc > max) {
max = bc;
maxpos = j;
maxshoot = poscanshoots[j][k] & rem;
maxtar = posshoottar[j][k];
}
}
}
if (max == 1) {
okflg = 0;
break;
}
used |= 1 << maxpos;
rem ^= maxshoot;
remcnt -= max;
tarstemp[maxpos] = maxtar;
}
if (okflg) {
// 残った隕石の数 <= 残りビーム発射回数 なので,
// 残った隕石と残ったビーム発射座標に対して適当に割り当てる
int rt = rem;
int j = 0;
for (int i = 0; i < shootposcnt; ++i) {
if (!((used >> i) & 1)) {
while (!((rt >> j) & 1) && j + 1 < n) ++j;
tarstemp[i] = aStage.asteroid(j).pos();
rt ^= 1 << j;
}
tarstmp[loop][i] = tarstemp[i];
}
ok = m;
}
else ng = m;
}
// 二分探索によってクリア可能ターンが求まったが, 次の隕石を目指して動いていたもののその隕石に到達せずにビームで破壊して終了, みたいなときに
// 隕石を目指さずにビームでより撃ち落とせるような座標に移動した方が早く終了する場合がある
// なのでそれを探索する
// 探索方法としては, ビームは直線なのでとあるビームを撃てる場所もその直線上となる
// よって, その直線と今の座標との距離を見る, ...とかすると円の共通接線全列挙とかいうことになってやりたくなくなる
// が, そんなことはしなくてもよくて, とある点と直線の距離が k 以下の場合,
// 当然その点を中心とした半径 k の円と直線は交点を持つ
// なので, ビーム発射ターンまでのターン数に応じた移動可能距離を半径とする円の円周上の各点から O(n^2) で落とせる隕石の集合を列挙してあげればよい
// 円周上を分割して多くの点を調べた方が漏れなく調べ上げられるが, 重いわりにそこまで改善されなかったので 19 分割にとどまっている
// また, 計算量削減のため, 先に最後の発射点以外について先ほど述べた嘘貪欲を行なっている
for (int i = (Math::Min(ok, bestok) - 1) / 41; i > 0; --i) {
int rem = (1 << n) - 1;
int remcnt = n;
int lasvisturn = -1;
for (int j = 0; j < n && visturn[j] <= i * 41; ++j) {
rem ^= 1 << vis[j];
--remcnt;
lasvisturn = visturn[j];
}
lasvisturn = Math::Max((i - 1) * 41, lasvisturn);
int shootcnt = i - 1;
int used = 0;
Vector2 tarstemp[50];
for (int j = 0; j < shootcnt; ++j) {
int max = 1, maxpos = -1, maxshoot = 0;
Vector2 maxtar;
for (int k = 0; k < shootcnt; ++k) {
if ((used >> k) & 1) continue;
for (size_t l = 0; l < poscanshoots[k].size(); ++l) {
int bc = bitcnt(poscanshoots[k][l] & rem);
if (bc > max) {
max = bc;
maxpos = k;
maxshoot = poscanshoots[k][l] & rem;
maxtar = posshoottar[k][l];
}
}
}
if (max == 1) {
break;
}
used |= 1 << maxpos;
rem ^= maxshoot;
remcnt -= max;
tarstemp[maxpos] = maxtar;
}
int remposcnt = shootcnt - bitcnt(used);
int max = 0, maxshoot = 0;
Vector2 maxtar;
Vector2 maxpos;
double d = (i * 41 - lasvisturn - 1) * speed - eps;
Vector2 tpos = postmp[loop][lasvisturn];
std::vector<int> remv;
for (int k = 0; k < n; ++k) {
if ((rem >> k) & 1) remv.emplace_back(k);
}
int rlim = 19;
for (int j = 0; j < rlim; ++j) {
double rd = Math::PI * 2 * j / rlim;
Vector2 posrd = tpos + Vector2(Math::Cos(rd), Math::Sin(rd)) * d;
for (int &k : remv) {
if (posrd.squareDist(aStage.asteroid(k).pos()) < 50) continue;
double dis = posrd.dist(aStage.asteroid(k).pos());
double rad = std::asin((aStage.asteroid(k).radius() - epsL) / dis);
Vector2 dir = aStage.asteroid(k).pos() - posrd;
Vector2 tar1 = posrd + dir.getRotatedRad(rad);
Vector2 tar2 = posrd + dir.getRotatedRad(-rad);
int cs1 = 0, cs2 = 0, c1 = 0, c2 = 0;
if (posrd.squareDist(tar1) > 1) {
for (int &l : remv) {
if (Util::CanShootAsteroid(posrd, tar1, aStage.asteroid(l).pos(), aStage.asteroid(l).radius() - eps)) {
cs1 |= 1 << l;
++c1;
}
}
}
if (posrd.squareDist(tar2) > 1) {
for (int &l : remv) {
if (Util::CanShootAsteroid(posrd, tar2, aStage.asteroid(l).pos(), aStage.asteroid(l).radius() - eps)) {
cs2 |= 1 << l;
++c2;
}
}
}
if (c1 > max) {
max = c1;
maxshoot = cs1;
maxpos = posrd;
tarstemp[i - 1] = tar1;
}
if (c2 > max) {
max = c2;
maxshoot = cs2;
maxpos = posrd;
tarstemp[i - 1] = tar2;
}
if (remcnt - max <= remposcnt)
goto A;
}
}
break;
A:
rem ^= maxshoot;
remcnt -= max;
for (int j = lasvisturn + 1; j <= i * 41; ++j) {
postmp[loop][j] = maxpos;
}
int rt = rem;
int jj = 0;
for (int j = 0; j < shootcnt; ++j) {
if (!((used >> j) & 1)) {
while (!((rt >> jj) & 1) && jj + 1 < n) ++jj;
tarstemp[j] = aStage.asteroid(jj).pos();
rt ^= 1 << jj;
}
tarstmp[loop][j] = tarstemp[j];
}
tarstmp[loop][i - 1] = tarstemp[i - 1];
ok = i * 41;
}
if (ok < bestok) {
bestok = ok;
bestdep = loop;
}
}
// もっとも良い結果を大域変数にコピー
for (int i = 0; i < 50; ++i) {
poss[i] = posstmp[bestdep][i];
tars[i] = tarstmp[bestdep][i];
}
for (int i = 0; i < 2000; ++i) {
pos[i] = postmp[bestdep][i];
}
}
//------------------------------------------------------------------------------
/// 各ターンでの行動を返します。
///
/// @param[in] aStage 現在ステージの情報。
///
/// @return これから行う行動を表す Action クラス。
Action Answer::getNextAction(const Stage& aStage)
{
int turn = aStage.turn();
// ビームを撃てる(はずの)ターン
if ((turn + 1) % 41 == 0) {
// 本番ケースでバグったときや誤差死したとき用
// もしビームを撃ってどの隕石も破壊されなかった場合, とりあえず残っている隕石を撃つ
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (aStage.asteroid(i).exists()) {
if (Util::CanShootAsteroid(aStage.ship().pos(), tars[turn / 41], aStage.asteroid(i).pos(), aStage.asteroid(i).radius() - eps)) {
++cnt;
}
}
}
if (cnt == 0) {
for (int i = 0; i < n; ++i) {
if (aStage.asteroid(i).exists()) {
return Action::Shoot(aStage.asteroid(i).pos());
}
}
}
// あらかじめ決めた位置に発射
return Action::Shoot(tars[turn / 41]);
}
// あらかじめ決めた位置に移動
return Action::Move(pos[turn + 1]);
}
//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出されます。
///
/// @param[in] aStage 現在ステージの情報。
///
/// @note ここにステージ終了時の処理を書くことができますが、何も書かなくても構いません。
void Answer::finalize(const Stage& aStage)
{
}
} // namespace
// EOF
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment