ハル研プロコン2020に参加しました
この記事はKMCアドベントカレンダー18日目の記事です。
皆様こんにちは。zekeと申します。寒いですね、自転車を手袋なしで乗っていると手先が凍ってしまいました。今回はハル研究所が主催するプログラミングコンテストに参加しましたので雑に振り返っていきたいと思います。
さてハル研プロコンは2020年の11/4~11/18に開催されました。ハル研プロコンは2003年ごろから開催されているマラソン型プログラミンコンテスト*1で有名らしいですね。サークルの中で話に出ていたので気になって参加を決めました。最終順位は43位でした。*230位以内でもらえるトートバックほしかった…
問題
昔むかし、かけっこでカメに負けてしまったウサギがいました。 悔しさを胸にウサギは修行の旅にでます。 次こそ勝つために、修行の地に散らばる秘伝の巻物を集めてください。
はい、まあこれだけではわからないので簡単に説明しますと、
二次元平面上に「巻物」が散らばっている、目標はそれらをできるだけ早く回収することである。
参加者は巻物を回収する「ウサギ」が次にどこに向かうかを座標で指定しなくてはならない。
「ウサギ」の飛ぶ距離は、「巻物」を取るたびに長くなるが、「地形」によっては短くなってしまう。*3
ステージに関する全情報が開示されており、乱数依存。*4
こんな感じでしょうか。問題を見たときTSP*5みたいだなと記憶しています。
この問題特有の設定として
がありました。個人的に一つ目に関する考察が大変だったように思われます。
可視化ツールと確認用コードがありましたので実行してみると…
確認用コードを読んでみると、どうやらまだとっていない巻物に一直線に向かうような行動を指示しているようです。これでは途中に「池」があっても迂回しないので時間がかかってしまいますね…
実装方針
ここで今後のおおまかな実装方針を決めました。
最適な巡回順を見つける
最短の経路を探索する
一つ目ではどの巻物からとっていくか？というのを考えていて、二つ目ではある地点からある地点まで移動するときに、地形などを考慮してどのように進んでいくか？というのを考えようとしています。
経路探索
まず取り掛かったのは二つ目です。これは実装方針が立ちやすかったからです。二次元グリッド上の最短経路探索は重みありグラフの最短経路問題に帰着できることが多いです。今回の場合だと地形によって重みを付けた有向グラフの構築をした後、ダイクストラ法*10というアルゴリズムを適用することで簡単に実装することができます。(一つの座標に対して8方向へ有向辺を張りました、ステージが50*50=2500の大きさで *11 と考えると計算量
オーダーになることもわかります。)
実行してみると…
総ターン数が劇的に改良されているのもわかります*13
次に一つ目の巡回順について考えてみましょう。TSP問題はNP困難ですので多項式時間で解くことができません。そこでTSP問題で最もよく使われる2-opt法*14を実装しました。これはTSPの近似解を求めるもので、局所改善法の一つでもあります。貪欲解*15から局所改善を行いました。
わかりやすいように二つ並べました。左が改善前(貪欲解)で右が改善後(局所改善適用後)です。264ターンから194ターンに改善されてます。いい感じですね。
またこれを実装した後に制約をにらんでいると巻物の最大数が20個であることに気づきました*16。それならばbitDP*17による完全解を求めることができます！先ほどTSPはNP困難と紹介したのですが、指数時間で間に合う制約なら完全解を出すことができます。といっても愚直にやると巻物の数をNとするとかかってしまい計算量
？ぐらいかかってしまいます。富岳だと60sec以内で実行できるかもしれませんが、一般的なパソコンなら無理です*18。しかし動的計画法を用いると
まで落とすことが可能です。これを実装してやることで時間内で(20secほどかかる)巡回順の完全解を求めることが可能です。*19
微調整
ここまでで30000の大台を切ることに成功しました*20。ここからは巡回順は最善であることが証明されているので、経路最適化に注力していくことになります。ここではウサギの座標が浮動小数点で表記されていることがポイントです。単純な経路探索では大体の経路しかわからないため、細かいところは別に実装する必要があります。以下は細かい修正を比較したものです。
あとは光学的距離をヒントに幾何的なアプローチをしていたのですが、時間切れになってしまいました…
最終的には27567を達成することができました！
感想
とても楽しかったです！マラソンの醍醐味を味わえた問題でした。ある程度こうすればうまくいくんじゃないかと仮説を立てて、実装＆デバッグした後にうまく動いているのを見ると感激してしまいますね。
個人的に大変だったのは膨大なコードファイルの数ですね。
またこれはマラソン競技全般に言えるのですがデバッグがしんどいです…振り返りでは簡単と書いてある場所でも実際の実装には二日かかっているものもあります。ひとえに能力不足ですね、精進します。大体全体で30時間ぐらいかかったんじゃないかなと思います。実は自動車免許合宿中にやっていたこともあって大学の課題とともにやる必要があり、時間があまりとれなかったのが反省点です。ちゃんと計画して生きていきたいですね。
それでもマラソンは楽しい！みんなもやろう！
最後に
明日のKMC のアドベントカレンダーはpastakさんです。
おまけ
誰も見ないと思いますが、最終提出コードを貼っておきます…
//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright (C)HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください。
//------------------------------------------------------------------------------
#include "Answer.hpp"
#include <bits/stdc++.h>
//------------------------------------------------------------------------------
namespace hpc {
typedef long double Weight;
struct Edge { // src:辺の始点,dst:辺の終点,weight:辺の重さ
int src, dst;
Weight weight;
Edge(int Src, int Dst, Weight weeight) {
src = Src;
dst = Dst;
weight = weeight;
}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
const long long INF = 1e18;
const double DINF = 1e15;
bool operator<(const Edge& e, const Edge& f) {
return e.weight != f.weight ? e.weight > f.weight
: //辺は重さが重いものを"小さい"と定義する
e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
// Global
template <class T>
bool chmax(T& a, const T& b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
Vector2 OUTPUT(Vector2 pos, Vector2 target) {
float xres = 0;
float yres = 0;
if (pos.x > target.x && pos.x < target.x + 1) {
xres = pos.x;
} else {
xres = target.x + 0.5;
}
if (pos.y > target.y && pos.y < target.y + 1) {
yres = pos.y;
} else {
yres = target.y + 0.5;
}
return Vector2(xres, yres);
}
Graph StageGraph(Parameter::StageWidth* Parameter::StageHeight);
std::vector<int> scrolls_order;
std::vector<int> scroll_grid;
std::vector<std::vector<int>> state_type(
Parameter::StageHeight, std::vector<int>(Parameter::StageWidth));
int scroll_index = 0;
double distance(double sy, double gy, double sx, double gx) {
return sqrt(pow(sy - gy, 2) + pow(sx - gx, 2));
}
//
//------------------------------------------------------------------------------
/// コンストラクタ
/// @detail 最初のステージ開始前に実行したい処理があればここに書きます
Answer::Answer() {}
//------------------------------------------------------------------------------
/// デストラクタ
/// @detail 最後のステージ終了後に実行したい処理があればここに書きます
Answer::~Answer() {}
void shortestPath(const Graph& g, int s, std::vector<Weight>& dist,
std::vector<int>& prev) {
int n = g.size();
dist.assign(n, INF);
dist[s] = 0;
prev.assign(n, -1);
std::priority_queue<Edge> Q;
Q.push(Edge(-2, s, 0));
while (!Q.empty()) {
Edge e = Q.top();
Q.pop();
if (prev[e.dst] != -1) continue;
prev[e.dst] = e.src;
for (auto f = g[e.dst].begin(); f != g[e.dst].end(); f++) {
if (dist[f->dst] > e.weight + f->weight) {
dist[f->dst] = e.weight + f->weight;
Q.push(Edge(f->src, f->dst, e.weight + f->weight));
}
}
}
}
std::vector<int> buildPath(const std::vector<int>& prev, int goal, int start) {
std::vector<int> path;
for (int u = goal; u != start; u = prev[u]) path.push_back(u);
// reverse(path.begin(), path.end());
return path;
}
int Two2One(const int y, const int x) { return y * Parameter::StageWidth + x; }
std::pair<int, int> One2Two(const int state) {
return {state / Parameter::StageWidth, state % Parameter::StageWidth};
}
//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出される処理
/// @detail 各ステージに対する初期化処理が必要ならここに書きます
/// @param aStage 現在のステージ
void Answer::initialize(const Stage& aStage) {
//初手グラフ構築
// Timer::timer time();
scroll_index = 0;
Graph tempGraph(Parameter::StageWidth * Parameter::StageHeight);
StageGraph = tempGraph;
scrolls_order = {};
scroll_grid = {};
// std::cerr << "start" << std::endl;
int dx[] = {-1, 0, 1, 0, 1, -1, 1, -1, 1, 2, 1, 2, -1, -2, -1, -2};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1, 2, 1, -2, -1, 2, 1, -2, -1};
for (int height = 0; height < Parameter::StageHeight; height++) {
for (int width = 0; width < Parameter::StageWidth; width++) {
int end = Two2One(height, width);
Terrain type = aStage.terrain(Vector2(width, height));
Weight poswei = 0;
int TYPE = 0;
if (type == Terrain::Plain) {
poswei = 3;
TYPE = 0;
// std::cerr<<"P";
}
if (type == Terrain::Bush) {
poswei = 5;
TYPE = 1;
// std::cer
// std::cerr << "B";
}
if (type == Terrain::Sand) {
poswei = 10;
TYPE = 2;
// std::cerr << "S";
}
if (type == Terrain::Pond) {
TYPE = 3;
// continue;
// std::cerr << width<<" "<<height<<std::endl;
poswei = 30;
}
state_type[height][width] = TYPE;
for (int way = 0; way < 8; way++) {
int starty = height + dy[way];
int startx = width + dx[way];
if (startx >= Parameter::StageWidth || startx < 0 ||
starty >= Parameter::StageHeight || starty < 0) {
continue;
}
if (way >= 8) {
poswei *= 2.236;
} else if (way >= 4) {
poswei *= 1.414;
}
int start = Two2One(starty, startx);
StageGraph[end].push_back(Edge(end, start, poswei));
}
}
// std::cerr<<std::endl;
}
// std::cerr<<"initialize finished"<<std::endl;
////////////////////////////////////////////////////////////////////////////////
// bitDP
for (auto scroll : aStage.scrolls()) {
scroll_grid.push_back(Two2One(scroll.pos().y, scroll.pos().x));
}
int scrolls_num = scroll_grid.size();
std::vector<std::vector<Weight>> scrolls_dist(
scrolls_num, std::vector<Weight>(scrolls_num));
for (int i = 0; i < scrolls_num; i++) {
std::vector<Weight> dist;
std::vector<int> prev;
// std::pair<int,int> tempnow=One2Two(scroll_grid[i]);
// int nowh=tempnow.first;
// int noww=tempnow.second;
shortestPath(StageGraph, scroll_grid[i], dist, prev);
for (int j = 0; j < scrolls_num; j++) {
if (scrolls_dist[j][i] != 0) {
scrolls_dist[i][j] = scrolls_dist[j][i];
} else {
scrolls_dist[i][j] = dist[scroll_grid[j]];
}
}
}
auto pos = aStage.rabbit().pos();
int rabbit_posx = static_cast<int>(pos.x);
int rabbit_posy = static_cast<int>(pos.y);
std::vector<Weight> dist_fromrabbit;
std::vector<int> prev_fromrabbit;
shortestPath(StageGraph, Two2One(rabbit_posy, rabbit_posx), dist_fromrabbit,
prev_fromrabbit);
int nearest_scroll = 0;
Weight nearest_reg = INF;
for (int i = 0; i < scrolls_num; i++) {
if (nearest_reg > dist_fromrabbit[scroll_grid[i]]) {
nearest_reg = dist_fromrabbit[scroll_grid[i]];
nearest_scroll = i;
}
// std::cerr<<dist_fromrabbit[scroll_grid[i]]<<std::endl;
}
if (scrolls_num <= 2) {
std::vector<bool> have_seen(scrolls_num, false);
scrolls_order = {};
for (int i = 0; i < scrolls_num; i++) {
scrolls_order.push_back(nearest_scroll);
Weight tempreg = INF;
int next_order = 0;
have_seen[nearest_scroll] = true;
for (int j = 0; j < scrolls_num; j++) {
if (have_seen[j]) {
continue;
}
if (tempreg > scrolls_dist[nearest_scroll][j]) {
tempreg = scrolls_dist[nearest_scroll][j];
next_order = j;
}
}
nearest_scroll = next_order;
}
return;
}
/////////////////////////////////////////////////////////////////////////////////////
std::vector<std::vector<Weight>> bitDP(
std::pow(2, scrolls_num), std::vector<Weight>(scrolls_num, 1e9));
std::vector<double> bias(scrolls_num - 1);
bias[0] = 1.00;
for (int i = 1; i < scrolls_num - 1; i++) {
bias[i] = bias[i - 1] / 1.1;
}
bitDP[(1 << nearest_scroll)][nearest_scroll] = 0;
for (int bit = 1; bit < std::pow(2, scrolls_num); bit++) {
for (int j = 0; j < scrolls_num; j++) {
if (!(bit & (1 << j))) {
continue;
}
if (__builtin_popcount(bit) == 1) {
continue;
}
int beforebit = bit & ~(1 << j);
int befotebitcount = __builtin_popcount(beforebit);
for (int k = 0; k < scrolls_num; k++) {
chmin(bitDP[bit][j],
bitDP[beforebit][k] + ((Weight)scrolls_dist[k][j] *
(Weight)bias[befotebitcount - 1]));
}
}
}
Weight bitres = DINF;
int hogehoge = 0;
for (int i = 0; i < scrolls_num; i++) {
if (chmin(bitres, bitDP[std::pow(2, scrolls_num) - 1][i])) {
hogehoge = i;
}
}
int invbit = std::pow(2, scrolls_num) - 1;
int invtop = hogehoge;
std::vector<int> bitDPinv_path;
bitDPinv_path.push_back(invtop);
while (1) {
if (invbit == (1 << (nearest_scroll))) {
break;
}
int beforebit = invbit & ~(1 << invtop);
int bitCount = __builtin_popcount(beforebit);
for (int i = 0; i < scrolls_num; i++) {
if (abs((bitDP[beforebit][i] +
(scrolls_dist[i][invtop] * bias[bitCount - 1])) -
bitDP[invbit][invtop]) < 0.0001) {
bitDPinv_path.push_back(i);
invbit = beforebit;
invtop = i;
break;
}
}
}
reverse(bitDPinv_path.begin(), bitDPinv_path.end());
scrolls_order = bitDPinv_path;
std::cerr << "bitDP score" << bitDP[(1 << scrolls_num) - 1][hogehoge]
<< std::endl;
return;
/////////////////////////////////////////////////////////////////////////////////////
}
Vector2 remote_jump(Vector2 pos, Vector2 goal, Weight power,
const Stage& aStage) {
Vector2 res;
double disreg = 0;
for (double i = power; i >= 0.01; i -= 0.01) {
Vector2 res1 = aStage.getNextPos(pos, i, goal);
Vector2 res2 = aStage.getNextPos(res1, power, goal);
if (chmax(disreg, distance(res2.y, pos.y, res2.x, pos.x))) {
res = res1;
}
}
return res;
}
//------------------------------------------------------------------------------
/// 毎フレーム呼び出される処理
/// @detail 移動先を決定して返します
/// @param aStage 現在のステージ
/// @return 移動の目標座標
///////////////////////////MAIN///////////////////////////////////////
Vector2 Answer::getTargetPos(const Stage& aStage) {
while (1) {
// std::cerr<<scroll_index<<std::endl;
auto const pos = aStage.rabbit().pos();
int rabbit_posx = static_cast<int>(pos.x);
int rabbit_posy = static_cast<int>(pos.y);
std::pair<int, int> goal =
One2Two(scroll_grid[scrolls_order[scroll_index]]);
for (auto scroll : aStage.scrolls()) {
if (static_cast<int>(scroll.pos().x) == goal.second &&
static_cast<int>(scroll.pos().y) == goal.first) {
if (scroll.isGotten()) {
// std::cerr<<"get"<<std::endl;
scroll_index++;
goal = One2Two(scroll_grid[scrolls_order[scroll_index]]);
}
break;
}
}
int rabbit_pos = Two2One(rabbit_posy, rabbit_posx);
std::vector<Weight> dist;
std::vector<int> prev;
shortestPath(StageGraph, rabbit_pos, dist, prev);
std::vector<int> temp_path = buildPath(
prev, scroll_grid[scrolls_order[scroll_index]], rabbit_pos);
bool is_sea = true;
for (int i = 1; i < static_cast<int>(temp_path.size()); i++) {
std::pair<int, int> now = One2Two(temp_path[i]);
std::pair<int, int> tempgoal;
if (i != 0) {
tempgoal = One2Two(temp_path[i - 1]);
} else {
tempgoal = One2Two(temp_path[i]);
}
if (state_type[static_cast<int>(now.first)]
[static_cast<int>(now.second)] != 3) {
is_sea = false;
}
bool land2sea =
(state_type[pos.y][pos.x] == 0) &&
(state_type[static_cast<int>(tempgoal.first)]
[static_cast<int>(tempgoal.second)] == 3);
if (!land2sea) {
land2sea = (state_type[pos.y][pos.x] == 0) &&
(state_type[static_cast<int>(tempgoal.first)]
[static_cast<int>(tempgoal.second)] == 2);
}
double power =
aStage.rabbit().power() *
Parameter::JumpTerrianCoefficient[state_type[static_cast<int>(pos.y)][static_cast<int>(pos.x)]];
double purepower = aStage.rabbit().power();
Vector2 nownext = aStage.getNextPos(pos, purepower, Vector2(now.second + 0.5, now.first + 0.5));
Vector2 tempnext = aStage.getNextPos(pos,purepower,Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5));
if (state_type[(int)tempnext.y][(int)tempnext.x]>state_type[(int)nownext.y][(int)nownext.x]) {
continue;
}
if (state_type[(int)tempnext.y][(int)tempnext.x]>state_type[(int)nownext.y][(int)nownext.x]) {
continue;
}
if(state_type[pos.y][pos.x]==0&&state_type[(int)tempnext.y][(int)tempnext.x]==3&&state_type[(int)nownext.y][(int)nownext.x]==3&&state_type[(int)tempgoal.first][(int)tempgoal.second]==0){
continue;
}
Vector2 now_state = pos;
Vector2 goal_vector =
Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5);
while (1) {
if ((state_type[static_cast<int>(pos.y)]
[static_cast<int>(pos.x)] == 2 ||
state_type[static_cast<int>(pos.y)]
[static_cast<int>(pos.x)] == 3)) {
break;
}
if (state_type[static_cast<int>(pos.y)]
[static_cast<int>(pos.x)] !=
state_type[static_cast<int>(goal_vector.y)]
[static_cast<int>(goal_vector.x)]) {
break;
}
if (state_type[static_cast<int>(now_state.y)]
[static_cast<int>(now_state.x)] >
state_type[static_cast<int>(pos.y)]
[static_cast<int>(pos.x)]) {
break;
}
if (now_state.x == goal_vector.x &&
now_state.y == goal_vector.y) {
// break;
return Vector2(goal_vector.x, goal_vector.y);
}
now_state =
aStage.getNextPos(now_state, purepower, goal_vector);
}
if (distance(pos.y, now.first, pos.x, now.second) < power) {
if (land2sea) {
// return Vector2(tempgoal.second + 0.5, tempgoal.first +
// 0.5);///////////////////////////
return remote_jump(
pos,
Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5),
purepower, aStage);
}
return Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5);
}
if (distance(pos.y, now.first, pos.x, now.second + 1) < power) {
if (land2sea) {
// return Vector2(tempgoal.second + 0.5, tempgoal.first +
// 0.5);///////////////////////////
return remote_jump(
pos,
Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5),
purepower, aStage);
}
return Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5);
}
if (distance(pos.y, now.first + 1, pos.x, now.second) < power) {
if (land2sea) {
// return Vector2(tempgoal.second + 0.5, tempgoal.first +
// 0.5);///////////////////////////
return remote_jump(
pos,
Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5),
purepower, aStage);
}
return Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5);
// std::cerr << "hoge" << std::endl;
}
if (distance(pos.y, now.first + 1, pos.x, now.second + 1) < power) {
if (land2sea) {
// return Vector2(tempgoal.second + 0.5, tempgoal.first +
// 0.5);///////////////////////////
return remote_jump(
pos,
Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5),
purepower, aStage);
}
return Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5);
// std::cerr << "hoge" << std::endl;
}
}
reverse(temp_path.begin(), temp_path.end());
std::pair<int, int> Tempres = One2Two(temp_path[0]);
if ((abs(goal.first - rabbit_posy) + abs(goal.second - rabbit_posx) <
3) |
is_sea) {
return Vector2(goal.second + 0.5, goal.first + 0.5);
}
if (state_type[static_cast<int>(pos.y)][static_cast<int>(pos.x)] == 3) {
for (int i = 0; i < static_cast<int>(temp_path.size()); i++) {
std::pair<int, int> tempres = One2Two(temp_path[i]);
if (state_type[static_cast<int>(tempres.first)]
[static_cast<int>(tempres.second)] != 3) {
return Vector2(tempres.second + 0.5, tempres.first + 0.5);
}
}
}
reverse(temp_path.begin(), temp_path.end());
return Vector2(Tempres.second + 0.5, Tempres.first + 0.5);
}
}
///////////////////////////MAIN///////////////////////////////////////
//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出される処理
/// @detail 各ステージに対する終了処理が必要ならここに書きます
/// @param aStage 現在のステージ
void Answer::finalize(const Stage& aStage) {}
} // namespace hpc
// EOF
*1:競技プログラミングの中で比較的長期間で開催されるコンテストのこと。なにかしらのスコアで競うものが多い。今回は約2週間。
*2:最高順位は28位でした。
*3:巻物をとるたびに1.1倍、地形に関しては後述
*4:手元と本番ではステージが異なる
*5:巡回セールスマン問題
*6:平地:1.0,茂み:0.6,砂地:0.3,池:0.1の補正
*7:マルチスレッド不可
*9:見にくくてすみません…
*10:辺が非負であるときに単一始点最短距離を解くためのアルゴリズム
*11:E:辺数,V:頂点数
*12:巡回順が変わっているのは重み付きで一番近くの巻物をとるように改良したため
*13:70%改善！
*14:2辺をランダムに選び、コストが低くなる方につなぎかえるアルゴリズム
*15:近い巻物から回収する
*16:先に読んどくべきだった…
*18:競プロでよく言ってる
*19:もちろん巻物をとったら飛距離が1.1倍になることを考慮しています
*20:ちなみに33333を切るとチャレンジスコア達成ということでハル研から褒められます
*21:かかりすぎ
今年買ってよかったもの2020
この記事は、Kyoto University Advent Calendar 2020の6日目の記事です。
自己紹介
こんにちは、zekeというものです。京都大学工学部工業化学科で学部2回生をやらせてもらっているものです。普段はのんびり大学生活をしながら、趣味でCPUについて勉強したり、競プロ(マラソンが主)をやっていたりします。
今日の話
これの執筆を完全に忘れていたこともあってネタが思いつかなかったので、この時期によくある「今年買ってよかったもの」を紹介していきたいと思います。
今年はオンライン授業が中心だったため、それに関するものを中心にやっていきたいと思います。
Ipad無印
これが私のオンライン授業を支えたといっても過言ではないです。私の属する学科では毎週のように課題が出る授業がいくつかあるのですが、そのほとんどをIpadでやっています。おそらくタブレットがなければ紙に書いて写真で撮る方法があると思うのですが、そんなことやってられないの思い購入を決定しました。GoodNotesというノートアプリで普段多用するのですが、ノートを階層化して保存できたりPDFへの変換が容易であることから非常に使い勝手が良いです。大体Ipad他(ペン、充電器、カバー、フィルム)込々で￥50000でそろえることができます。タブレットはほかにもアンドロイドタブレットやfireタブレットなどがありますが、使い勝手としてIpadが一番いいんじゃないでしょうか。
本立て
私の学科が指定する専門書は総じてサイズが大きいのですが、そういった本の閲覧に役立ったのがこの本立てです。通常こういった本は特に新しいものだと手で押さえていないと勝手に閉じたりしてストレスがたまるわけですが、この本立てはいい感じの角度に固定してくれるので重宝しています。
ノートPCクーラー
私のノートPCは大体常時稼働＆常時電源接続をしているので、時々重い処理をさせると大爆音でファンが鳴ることがよくありました。オンライン授業が始まってPCの使用頻度が上がったのでどうしようかと考えていたところ、ノートPC向けファンがあることを知り買ってみた次第です。構造としては4つのファンが駆動する板の上にPCを乗っけるだけなのですが、夏ごろなどは特に冷却に寄与していたんじゃないかと思います(丸二日CPU使用率100%の状態を続けてもクラッシュしなかった)。ノートPCの熱に困っている方は一度試してみるといいかもしれません。
サブディスプレイ
オンライン授業でZoomなどを使っていると、Zoomの画面で1画面を使ってしまうのでその間に気になったことを調べられなかったりTL巡回ができない不自由がありました。そこでAmazonでまあまあ安かったこちらのモニターを購入しました。モニターを買う時に気を付けてほしいのが結構場所をとるので、買う前にどのような配置をするか一考して買わないと、えらい目に合うということですね。机の上だったら25インチ程度が限界じゃないでしょうか。
人をだめにするソファー
一時期流行ったやつですね。コロナ禍で家にいることが多くて、できる限り快適に暮らしたいという思いから購入しました。個人的に欠点としては、座ると快適過ぎて立って何もしたくなくなるというところですかね。タブレットで授業を受けながら座って作業すると最高です。
パネルヒーター
大学生は冬に炬燵に潜るという偏見があるのですが、わが下宿には炬燵用の机も炬燵もないのでこれを買いました。これだけではめちゃくちゃ寒いので毛布を二枚ほど巻くといい感じに暖かくなります。これからの季節電気代を節約したい方はぜひ。
メモリ
私のノートPCは8GBだったのですが、なんか動作がもっさりしていたので買いました32GBメモリ。感想としては以前より動きがよくなった印象(Chromeがもっさりしない)ですが32GBもいらなかったですね、16GBで十分だった。メモリの余裕は心の余裕。
外付けSSD
SSD容量のほうも仮想環境をいくつか立てていると、デフォルトの256GBが悲鳴を上げだしたので買いました1TB。主にSteamのゲームデータなどを入れています。
CPUの創り方
最後に本の紹介。この本はその名の通りCPUの作り方について教えてくれるのですが、最低限オームの法則さえ知っていれば理解できる良書。CPUの最低限の知識をインプットしながら実際に作ることができます(といってもくそ雑魚ですが)。サークル発表用の資料を作ったりもしているので気になった方はどうぞ。
最後に
買った本の紹介をしようとして、今年読んだ本を見ていたらほとんど借りた本ということがわかりました。図書館は偉大ですね。あとこれを書いてるときにちょうど0:00(〆切)になってしまいました…間に合わなかった…
明日の記事は二十日さんによるものです。お楽しみに～
AtCoderで水色になりました！
zekeです。AtCoderで競技プログラミングをしている大学1回生です。先日、三日連続rated(初日はunrated)でめでたく入水できましたので、色変記事を書いた次第です。
この週末で+113した pic.twitter.com/K1PMWfdZVQ
— じーく (@zeke8080) January 12, 2020
約10か月で水色になれました。4月に一応の目標としていた水色に到達できてほっとしています。水色の色変記事を書くことは夢だったので、自分語りを加えながら、これまでの競プロ人生を振り返っていきたいと思います。
一応の注意
完全な自己満記事です。覚悟してください。
競技プログラミングを始めたきっかけ
高校まではプログラミング自体をほとんどやったことがなく、むしろハードの方面をやっていました。ロボカップなどに出ていたこともありました。しかし、大学の新歓でKMCというサークルに出会い、そこで競プロと出会いました。そのサークルでは毎週、競プロ練習会が開かれていて、自分のようなC++を触ったことのないような初心者に対しても親切に教えていただいたので徐々にはまっていった感じです。先輩方には感謝してもしきれないです。AtCoderもその流れで知って、ABC124にて初参加を果たしました。平成ABCにしては簡単な回で3完などをしています。
灰～茶にかけて
先述した通り、毎週の競プロ練習会でいろんなことを教わったのですが、始めたばかりの自分には荷が重く、あまり理解はできませんでした。その頃は、あまり競プロを熱心にはやっておらず、毎週末のコンテストに出るだけだったのですが、7月ぐらいにICPCがあることを知りました。これは大学生向けの競プロの大会であり、3人組で出るものだったので、同じサークルの同じく同時期に始めた人と組んで出場しました。このコンテストのために最低限のC++の文法(配列、データ構造)や基本的なアルゴリズム(全探索など)を頭に突っ込んでいた覚えがあります。そして、コンテスト直前ぐらいで茶色になりました。
そのあとにあったICPCですが、やはり初心者には荷が重く、2完しかできませんでした。しかし、その時印象的だったのは、自分たちの向かいのチームが終わる直前で難問を通していたことです。そのチームは「heno world」さんで、めちゃくちゃ強い方々だったのですが、その姿を見て「早く強くなって、あんなふうになりたい」と思った記憶があります。
茶～緑にかけて
ちょうど夏休みに入ったので、大学図書館に行っては精進を繰り返していました。蟻本を買ったり、drkenさんの記事(神記事たくさん！)を読んだりして、いろんなアルゴリズムを頭に叩き込みました。全探索、BFS、DFS、累積和、二分探索、尺取り、動的計画法などのアルゴリズムの存在を知りました。とにかく、このころはICPCで振るわなかったこともあって、必死でABCのC問題を埋めていた気がします。この時、同時並行でゲーム製作をしていたこともあり基本的な実装力がついた気がします。具体的にはA、B問題は確実に解ける、C問題も令和ABCになってからは安定してとけるようになる、といったところでしょうか。レートが伸び悩んだ時期もありましたが夏の終わりまでに色変を目指して頑張っていました。そうやってしているうちに、緑パフォが安定してきて9月初めごろに緑になれました。
緑～水にかけて
かなり大変でした。緑になるまでに、いろんなアルゴリズムを学びましたが、それがまだ実践段階にはなかったのです。具体的には二分探索の使いどころや基本的な動的計画法の書き方とかです。またbitを用いた問題(XORなど)、グラフ問題と出会った問題と出会ったのもこの頃です。しかし、今まで学んだことを組み合わせて使ったり、違った視点から見る問題にも出会って、だんだん競プロの楽しさに気づき始めました。問題もAtCoderにとどまらずAOJやCodeforces、yukicoderにも手を出して片っ端から解いていた感じです。難易度帯としてはAtCoderだとdifficultyが緑～水ぐらい、yukicoderでは星2～3ぐらいでしょうか。AOJは新たなアルゴリズムを知った時に、それを試すために利用しました。コンテストのほうは令和ABCに切り替わってからA、B、C問題はACして当たり前、Dも大体解けて、E問題にチャレンジしていこうという感じです。しかし、時々爆死してしまうこともあり、それは他の記事にまとめています。
11月ぐらいで順調に上がっていたレートがカクっと下がったり、解けそうで解けない問題に出会ったりして歯がゆい思いもしました。しかし、この頃に始めたTwitterであほみたいに強い方々や、同じぐらいのレベルで頑張っている人を見てモチベをもらったりしていました。そんな感じで精進を続けていたら二回のunratedを経て無事に水色になりました。
やったことに関してあれこれ
精進などの内容をつらつら語ります
その１：コンテストに出る
多分一番大事なのでは？と思います。もちろんABCは出るとして、諸意見ありますがAGCや企業コンにもどんどん出るべきだと思います。自分は理不尽に難しい問題を解くのが好きなこともあるのですが、二時間ぐらい頭を抱えながら問題を考える経験を付けるべきだと思います。また、ACしたときの快感は凄まじいものがありますし、たとえできなかったとしても解説を見るなどして、いろんな気づきがあるからです。Twitterでコンテストについてワイワイするのも楽しいですし、とにかく出ましょう！
その２：問題を解きまくる
はい、精進です。解きまくりましょう。個人的に精進の助けになったページを下に貼ります。
drkenさんの蟻本シリーズです！蟻本で習った内容をAtCoderの問題で復習できるので、最高です！
はまやんはまやんはまやんさんの分野別問題まとめページです！ある分野に関して集中的にやりたいときに最適です。
AtCoder Rivalsというサイトです。登録したユーザーの問題の提出状況をTL形式で観測できます。異常精進している人々を観測してモチベを上げましょう！
他にもたくさんのサイトにお世話になりました。感謝します。
その３：刺激を受ける
こちらのサービスは天才や人外がうようよいて、奢りそうになった時に見るといいかもしれません！！！
他にも、解説記事を書いてみたり、サークル内で講座をやったりすることで自分は精進をしました。拡張などを作ったりするとテンションが上がります。
水色になるまでに勉強したアルゴリズム、テク(若干、上から目線)
いろんなマクロ
自分は緑になったぐらいでC++でマクロを導入しました。賛否が分かれますが、自分は競プロの本質のみを追求できるので愛用しています。
全探索系アルゴリズム
BFS、DFS、bit全探索、貪欲などを含みます。この辺りは類似問題を解きまくって、慣れるしかないと思います。実装が重いことがあるので注意です。コンテストでは真っ先に疑う癖をつけたほうがいいと思います。
二分探索
これも真っ先に身につけたほうがいいと思います。応用範囲が大きいですし、何よりよく出ます。これもコンテストで真っ先に疑うべきものです。
(基本的な)動的計画法
最初の難関です。ナップサックを始め様々な形があるのが特徴です。自分は、全然できなかったのでEDPCなどを解きまくって習得しようとしています。以下、自分が書いた精進記事です。
累積和
めちゃくちゃ出ます。他のアルゴリズムとの組み合わせの相性がとてもいいです。一次元、二次元imosを習得しましょう。
以下の記事が最高なのでぜひ読みましょう！
グラフ
最短距離問題、全探索系問題、木、二分木、抽象グラフに落とす…などバリエーション豊かです。概念自体を競プロで初めて見たので大変でした。
こちらも神記事なので読みましょう！
UnionFindなどの集合系
UnionFindだと思わせない問題が多いように感じます。
小学校算数
いっぱい出ます。組み合わせ、確率、整数、いろいろあります。自分は中学受験勢だったので当時のことを思い出しながらやっています。
受験数学
いっぱい出ます。整数、幾何、三角関数、いろいろあります。数学が得意な人々は持ち前の数学力で殴っていくらしいです。自分はよわよわです。
C++の文法あれこれ
コンテナ、構造体、STLなどです。C++には競プロのために作られているのではないかと思うほど便利なSTLがあったりするので、ぜひ覚えましょう。
ぶっちゃけ使えなくても大丈夫なやつ
セグメント木など
これから勉強していこうと思います。一回だけ実戦で使ったことがあり、青パフォをたたき出したときには発狂しました。
幾何とか
あまり出ないし…誤差に注意なことを覚えておくといいかもしれません。
フローとか
知ってはいるけど実戦では使ったことはない、そのようなものです。
他Twitterでみかけるような難しそうなやつ
ぶっちゃけそんなものを覚えるよりも、既存の知っているアルゴリズムの熟練度を上げるのが大事だと思います。
最後に
自分は大学に入ってから競プロに出会ったのですが、この界隈には天才、奇人、人外、神、その他諸々がうようよしています。自分はただの凡人なので、そういった人たちを見ると自己肯定感がガリガリ削られます。でも、自分は頭を限界まで使う競プロが好きで、この界隈に入り込んだことの後悔を全くしていません。むしろ、自分の力がどこまで通用するか試したいぐらいです。この度は水色になりましたが、次は青目指して猛進していきたいです(/・ω・)/。
長くなりましたが、ここまで読んでいただきありがとうございました。
どうして自分は水色になれなかったのか
これは、KMC Advent Calendarの25日目の記事です。
前日はid:cc141君の公認会計士試験を受けてみたでした。 公認会計士すごい。
はじめましてzekeです。競技プログラミングとかやっています。
突然ですが見てほしいものがあります。
目標としていた「この記事を書くまでに色を変える」ことができませんでしたーーーーー！！！！！
いや、Advent Calendarに登録した時点では色変記事書く気満々だったんですよ。いや、ほんとに。 しかし、この度色を変えることができなかったので、色変記事ならぬ「色が変わらなかった記事」を書こうと思うんですよ、書くネタがマジでなかったため。 趣旨としては、ここ最近のコンテストで好成績を残せなかった反省をつらつら述べるだけになっております。 それでもいい方は、最後まで読んでいただけると、ありがたいです。
水色になれなかった理由その一 : やはり精進が足りなかった
競プロの原点にして最も大事な精進。やっぱりこれが足りないのが第一の理由でしょう。
水色になれなかった理由その二 : コンテストに最後まで集中できる環境、体調を整える
これは意外に大事だと思います。
- この時学祭があって気持ちが浮ついていた
- サークルのシフトを七時間こなした
- コンテストをやるよい場所がなかったので、ネカフェでコンテストをした
これらの状況でやったのが大きいと思います。結果、ABCでAB二完という惨敗をしています。 これは余談ですが、このコンテスト終わった後、憂さ晴らしに朝までカラオケなどをやっています。 つまり、「落ち着いて集中できる状態で」、「体調を万全にして」、「慣れた場所で」コンテストを行うことが大事でしょう。 そういった状況下では、
- 少なくとも爆死の可能性は大幅に減らせる
- 過去に解いた問題を効果的に想起することができ、類似問題が出た時に大きなアドバンテージになる
- いつもと違うことが起こっても(5完しても緑パフォなど)気持ちが乱されない
- コンテスト終了間際まで集中力を維持できる
といったメリットがあると思います。 なので、最近は可能な限り、自室で30分ほどの仮眠をとった後に、ウォーミングアップとして数問解いてからコンテストに臨もうとしています(なかなか難しいですが)。
水色になれなかった理由その三 : 本番慣れしていない
これは競プロにとどまらず、受験などにも共通すると思うのですが、やはり本番になれるというのは大事です。つまりは、もっとratedに出ろってことですね。やはり練習だけでは
- 解いている問題がどのくらいの難易度かわからない(順位表情報からある程度分かることもありますが)
- 思いついた解法にしがみついてしまう
- 初手で躓いた(簡単な問題でWAを生やす)などの想定外な出来事に弱い
といったものがあると思います。 特に二つ目は自分では大きいと思っていて、この問題ではO(1)の解法にコンテスト中ずっととらわれていて二分探索でできることに気づくことができませんでした。 やはりレートが関係するコンテストならではの緊張感を毎回感じていて、それによる失敗はあると思います。 そこで数日前、初めてCodeforcesのdiv2に出ました。ratedのコンテストを増やして、早く本番慣れをしたいです。
水色になれなかった理由その四 : フラグを立てた
年内水色ワンチャンあるか？ pic.twitter.com/5h094KiZVn
— じーく (@zeke8080) November 9, 2019
これはお手本のようにフラグを立てる阿呆の図です。
ほんっとにフラグを立てるのは危険です！！！！ 間違ってでも、
- コンテスト前に「あっ次のコンテストで色変わるわwwww」
- コンテスト中に「あっ勝確www」
とかをやってはいけません！！！！！ 慢心ダメゼッタイ。 こんなことをするから、
大爆死！！ pic.twitter.com/vPW1QFIgbV
— じーく (@zeke8080) November 24, 2019
こんなことになるわけです。
こんなことを言ってきましたが、
自分は競プロが好きです。19年生きてきて、ここまで一喜一憂しながらも、ここまで熱心に取り組んでいるのは初めてかもしれません。やっぱり難問にぶち当たって、悩みに悩みぬいた挙句、思いついた解法で実装してはWAを生やし、ドイツ語の授業を犠牲にして考察を重ねた結果出すACには格別なものがあります。やはり、水色になるには、その過程を楽しむといったことが一番かもしれません。年内にはあと二回のratedがあります。これまでの反省を踏まえて、水色めざしてがんばっていきたいと思います。
