【新歓ブログリレー】AtCoder Heuristic Contestに参加しよう！
はじめに
この記事はプログラミングをかじったことがある人向けのものとなります。
AtCoder Heuristic Contestとは、最適解を出すのが難しい問題に対し、できるだけ良い解を作成するコンテストです。AtCoderでは最近HeuristicのレートがAlgorithmとは別に正式に実装されました。参加人数も徐々に増えつあり、今後さらに盛り上がっていくでしょう。
ここでは、Heuristic入門者に向けてIntroduction to Heuristics ContestをC++で解きつつ、実際のコンテストでの100位内に入れるようなスコアを出すコードを書いていこうと思います。
問題
こちらを見てください。
このIntroduction to Heuristics ContestではメインのA問題と入門者向けガイド付き小問B, Cがあります。
まずはB問題を解いてみましょう。
B問題
#include <bits/stdc++.h>
using namespace std;
int D;
vector<int> C;
vector<vector<int>> S;
int main(){
cin >> D;
C.resize(27);
for(int i = 1; i <= 26; i++) cin >> C[i];
S.resize(D + 1, vector<int> (27));
for(int i = 1; i <= D; i++) for(int j = 1; j <= 26; j++) cin >> S[i][j];
int score = 0;
vector<int> last(27, 0);
for(int d = 1; d <= D; d++){
int t; cin >> t;
score += S[d][t];
last[t] = d;
for(int i = 1; i <= 26; i++) score -= C[i] * (d - last[i]);
cout << score << endl;
}
return 0;
}
こんな感じで書くとACになります。入力/出力が1-indexedなのでそれに合わせました、嫌という人は0-indexedで書いても全く問題はないです。
さて、これで「途中までの状態に対して、次に開催するコンテストを決めたときにスコアがどうなるか」を求めることができました。これを構造体にしてみます。 次のようになります。
#include <bits/stdc++.h>
using namespace std;
int D;
vector<int> C;
vector<vector<int>> S;
struct status {
vector<int> ans, last;
int score = 0;
status(){
last.resize(27, 0);
}
void add(int t){
ans.push_back(t);
int d = ans.size();
score += S[d][t];
last[t] = d;
for(int i = 1; i <= 26; i++) score -= C[i] * (d - last[i]);
}
};
int main(){
cin >> D;
C.resize(27);
for(int i = 1; i <= 26; i++) cin >> C[i];
S.resize(D + 1, vector<int> (27));
for(int i = 1; i <= D; i++) for(int j = 1; j <= 26; j++) cin >> S[i][j];
status T;
for(int d = 1; d <= D; d++){
int t; cin >> t;
T.add(t);
cout << T.score << endl;
}
return 0;
}
statusのadd(int t)を行うと、今までの状態からtのコンテストを開催した状態になります。このコードでB問題をACすることができます。これを使ってA問題で正の得点を得られるコードを書いてみます。(C問題はこの記事では解きません。興味のある人は解いてみてください。)
貪欲法
1日目から順にタイプ1, 2, 3, … 26を開催した時で最もスコアがよくなったものを採用し、次の日に進む というコードを書いてみます。このように「その場で最善の手を選ぶことを繰り返す」アルゴリズムを貪欲法といいます。
#include <bits/stdc++.h>
using namespace std;
int D;
vector<int> C;
vector<vector<int>> S;
struct status {
vector<int> ans, last;
int score = 0;
status(){
last.resize(27, 0);
}
void add(int t){
ans.push_back(t);
int d = ans.size();
score += S[d][t];
last[t] = d;
for(int i = 1; i <= 26; i++) score -= C[i] * (d - last[i]);
}
};
int main(){
cin >> D;
C.resize(27);
for(int i = 1; i <= 26; i++) cin >> C[i];
S.resize(D + 1, vector<int> (27));
for(int i = 1; i <= D; i++) for(int j = 1; j <= 26; j++) cin >> S[i][j];
status T;
for(int d = 1; d <= D; d++){
status nxt;
for(int t = 1; t <= 26; t++){
status tmp = T;
tmp.add(t);
if(nxt.score == 0 || nxt.score < tmp.score) nxt = tmp;
}
T = nxt;
}
for(int d = 0; d < D; d++){
cout << T.ans[d] << endl;
}
return 0;
}
Tがその日までの暫定解で、そこからタイプ1, 2, 3, … 26を開催した時のスコアが最も高くなるものを採用しています。これをA問題に提出すると、62,634,806点となります。だいたい850位くらいのスコアとなります。
ビームサーチ
なんかつよそうですね。実際つよいです。
貪欲法では、開催した時にスコアが最も高くなるものを採用しました。今回の問題ですか、一度スコアが下がるコンテストを開催した方が最終スコアが高くなるということが起こりえます。ビームサーチでは、最初に幅を設定し各ターンで上位幅分を採用し次のターンへ遷移させていきます。幅は大きい方がよいですが、その分実行時間がかかるのでうまい値を見つけてください。実装にはpriority_queueを使います。
#include <bits/stdc++.h>
using namespace std;
int D;
vector<int> C;
vector<vector<int>> S;
struct status {
vector<int> ans, last;
int score = 0;
status(){
last.resize(27, 0);
}
void add(int t){
ans.push_back(t);
int d = ans.size();
score += S[d][t];
last[t] = d;
for(int i = 1; i <= 26; i++) score -= C[i] * (d - last[i]);
}
};
bool operator<(const status& a, const status& b){ return a.score < b.score; }
int main(){
const int width = 400;
cin >> D;
C.resize(27);
for(int i = 1; i <= 26; i++) cin >> C[i];
S.resize(D + 1, vector<int> (27));
for(int i = 1; i <= D; i++) for(int j = 1; j <= 26; j++) cin >> S[i][j];
priority_queue<status> que;
que.push(status());
for(int d = 1; d <= D; d++){
priority_queue<status> nxt;
for(int i = 0; i < width; i++){
if(que.empty()) break;
status T = que.top();
que.pop();
for(int t = 1; t <= 26; t++){
status tmp = T;
tmp.add(t);
nxt.push(tmp);
}
}
swap(que, nxt);
}
status Ans = que.top();
for(int d = 0; d < D; d++){
cout << Ans.ans[d] << endl;
}
return 0;
}
vector<priority_queue>をしてもよいのですが、1つ前からしか遷移しないのでswapするようにしてメモリ消費量を抑えています。(適当に書いたらMLEになりました…)
実行時間は1908ms, 118,063,284点を獲得できました。実際のコンテスト62位相当です。(これは2年前のコンテストなので、多分ボーダーが低めです。最近のコンテストだともうちょい厳しめの順位になります。)
おわりに
と、こんな感じでより良いスコアを獲得できるコードを書いていくのがHeuristic Contestです。今回のものは短期(2h)でしたが、1~2週間の長期のものもあります。また、AtCoderのHeuristicのレートは下がらないので、気軽に参加することができます。プログラミング書きたいけど作りたいもの何もないな…という人にとってはとてもいいコンテストだと思います。ぜひ参加してみてはいかがでしょうか？
適当に書いて提出したらよいスコアが出たので記事にしただけで、普段は大体150位近辺です…
コラム
新入生に向けて、現在使っているパソコンを紹介します。
Lenovo YOGA 750iを使っています。
- CPU : Intel Core i7 1165G7
- メモリー : 16GB
- ストレージ : 512GB SSD
(確か)12万程度で買えたと思います。アクティブペンが付属していて、360度回転させタブレットのようにも使用でき、とても良いです。
似たようなスペックでHP ENVY 14-ebがありますが、それと比較して
- 価格が1万円ほど安い
- 100gほど軽い
などの利点がありとてもおすすめです。
また、パソコンを買う際に「充電器の大きさ」はとても重要視した方がよいと思います。 僕はAnker PowerPort III 65W Podを使っています。もとの充電器よりだいぶ小さく快適です。PD充電に対応しているものを購入するとよいと思います。 また、コンセントが使えないことも考え大容量モバイルバッテリーを準備しておくのもよいと思います。 僕はAnker PowerCore III Eliteを使っています。
コメント入力