JOI 2018/2019 予選参加記（+読み甲斐があるかもしれない話）

先週の日曜日(12/7)、JOI（日本情報オリンピック）のオンライン予選に参加して、506点(100+100+100+100+100+6)・Aランクを獲得しました。その時の体験談を記事数稼ぎも兼ねて書こうと思います。まあ高３なので本選出れないんですけどね。化学グランプリとか数オリは出れるのにな(ﾎﾞｿｯ

問題と公式の解説・解答例が情報オリンピック日本委員会のサイトに載っているので参考にしてください（この記事にも問題の概要を載せています）。

※コードはすべてC++です。また、小課題（部分点）の制約はA~E問題では省略しています。

A問題 – ソーシャルゲーム (Social Game)

概要

• JOI君は月曜日にあるソシャゲを始めた。
• そのソシャゲは一日一回ログインボーナスがコイン\(A\)枚、週間（月～日）フルログインボーナスがコイン\(B\)枚である。
• 少なくとも\(C\)枚のコインを得るために必要な最低のログイン日数を求めよ。

問題ページ

制約

• \(1\leqq A\leqq1000\)
• \(0\leqq B\leqq1000\)
• \(1\leqq C\leqq10^6\)

入出力

思考過程

週間フルログボをきちんともらったほうが当然コインの貯まる速さは速いので、１日目から順にログインのがいいな。シュミレーションかな（割り算は大変そう）。A問題だし。制約も間に合いそう。

コード・提出結果

#include <iostream>
using namespace std;

int main() {
  int a, b, c, coin = 0, i;
  cin >> a >> b >> c;
  for (i = 1; i <= 100000000; i++) {
    coin += a;
    if (i % 7 == 0) coin += b;
    if (coin >= c) break;
  }
  cout << i;
  return 0;
}

ループのカウンタ変数iをfor文の外で定義して、最後にそのまま出力できるように書いています。iの初期値を0にしなかったのは、週間ログボをもらう日曜日のタイミングをi%7==0と書きたかったからです。出力もそのままiになるし。

感想

いわゆる「やるだけ」という部類に入りそうです。下手に数学で解こうとすると逆にドツボにはまりそう（昔の僕のパターン）。

B問題 – すごろくと駒 (Sugoroku and Pieces)

概要

• JOI君は横一列2019マス・左端スタート・右端ゴールのすごろくを持っている。
• 現在このすごろくには、\(N\)個の駒（左側から駒1, 駒2, …, 駒\(N\)）が置いてある。
• 駒\(i\)はマス\(X_i\)に置かれている（\(i\neq j\)のとき\(X_i\neq X_j\)）。
• JOI君は\(M\)回の操作を行い、そのうち\(j\)回目の操作では駒\(A_j\)を1マス進める。ただし、ゴールにいる、または移動先に別の駒があるときは動かさない。
• 操作終了後の各駒のマスを求めよ。

問題ページ

制約

• \(1\leqq N\leqq100\)
• \(1\leqq X_1<X_2<\cdots<X_N\leqq2019\)
• \(1\leqq M\leqq100\)
• \(1\leqq A_j\leqq N\ (1\leqq j\leqq M)\)

入出力

思考過程

制約小さいしシュミレーションだな（即断）。

コード・提出結果

#include <iostream>
#include <vector>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<bool>sugoroku(2030, false);
  vector<int>koma(n+1);
  for(int i=1; i<=n; i++){
    cin >> koma[i];
    sugoroku[koma[i]]=true;
  }
  int m;
  cin >> m;
  for(int i=0; i<m; i++){
    int a;
    cin >> a;
    if(koma[a]!=2019 && !sugoroku[koma[a]+1]){
      sugoroku[koma[a]]=false;
      sugoroku[koma[a]+1]=true;
      koma[a]++;
    }
  }
  for(int i=1; i<=n; i++){
    cout << koma[i] << endl;
  }
  return 0;
}

駒iの現在の位置を他の駒の位置と関わりながら変更していくにあたって、

• 駒iの位置を持つ配列だけをとる
• 盤面用の配列に駒iの位置を保存する

の２通りが考えられますが、前者だと進もうとする位置に駒があるかどうか、後者だと現在の駒iの位置がどこかを調べるのにどちらも\(O(N)\)かかってしまいますし、for文を書くのが面倒です。そこでこの二つの配列を同時に更新することにしました（ただし後者は「そのマスに駒があるかどうか」のみを保存）。

と、今書いてて気づいたんですが、駒同士の順序関係は入れ替わらないので駒iの進む先を見るときは駒i+1だけ調べればいいですね。\(O(1)\)じゃん、つらい。ACしたしいいけど。

感想

これもA問題と同じでシュミレーションするだけの問題でした。いい方法を時間を掛けて考えるのもいいけど、制約を見て愚直な解法を試してみるのも一つの手だと思います。

C問題 – マルバツスタンプ (Circle Cross Stamps)

概要

• JOI君はマルスタンプ、バツスタンプ、マルバツスタンプの３種類のスタンプをそれぞれ0個以上持っている。
• マルスタンプは’O’、バツスタンプは’X’、マルバツスタンプは’OX’または’XO’を紙に印字できる。
• JOI君は持っているスタンプを一度ずつ用いる。
• JOI君が印字した長さ\(N\)の文字列\(S\)から、JOIくんが持っていたマルバツスタンプの個数の最大値を求めよ。

問題ページ

制約

• \(1\leqq N\leqq10^5\)

入出力

思考過程

とりあえず前からOXとXOを取れるだけ取ってみるとどうなるんだろう。仮に前から取ってはいない最大な取り方があったときは・・・お、それぞれ前にずらせば最初から取った取り方になるじゃん。じゃあ貪欲だな。

コード・提出結果

#include <iostream>
#include <string>
using namespace std;

int main() {
  int n, ox = 0;
  string s;
  cin >> n >> s;
  for (int i = 0; i < n - 1; i++) {
    if (s[i] == 'O' && s[i + 1] == 'X') {
      ox++;
      i++;
    } else if (s[i] == 'X' && s[i + 1] == 'O') {
      ox++;
      i++;
    }
  }
  cout << ox;
  return 0;
}

変数oxでマルバツスタンプの数を数えています。’OX’または’XO’が見つかったときにiを1増やしているのは、例えば文字列が”…OXO…”となっていた時、前の’OX’を取った後に次の’XO’を重複して数えさせないためです。2文字目の分をスキップしてるわけです。

感想

実は貪欲が正しいちゃんとした証明を未だに書いていません() 貪欲が怖いときはDPという方法もあるようです。

D問題 – 日本沈没 (Japan Sinks)

概要

• 日本列島は横方向に\(N\)個の区画に分割されていて、左から\(i\)番目の区間\(i\)の高さは\(A_i\)である。
• 現在海面の高さは0であり、時間の経過とともに徐々に上がっていく。
• 海面より高くて繋がった領域を島と呼ぶとき、日本が沈没するまで島の数は増減する。
• 島の数の最大値を求めよ。

問題ページ

制約

• \(1\leqq N\leqq10^5\)
• \(0\leqq A_i\leqq10^9\ (1\leqq i\leqq N)\)

入出力

思考過程

（長い思考の末）高度が下がって上がるところ（例：4→3→5）では水が来たときに島が一つ増えて、上がって下がるところでは一つ減るな。こいつらの個数を高さごとにメモして水位0から島の個数計算するとどうだろう。あ、でも水位\(0\sim10^9\)全部ループ回してると多分間に合わないな… あ、日本の横幅が\(10^5\)以下だから変化ある高さだけ数えれば最多でも\(10^5\)回だけ処理すればいいじゃん。mapで数えてforeachで順に計算するか。

コード・提出結果

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
  int n;
  cin >> n;
  map<int, int> maxl, minl;
  maxl[0] = minl[0] = 0;
  vector<int> a;
  a.push_back(-100000);
  for (int i = 1; i <= n; i++) {
    int tmp;
    cin >> tmp;
    if (tmp != a[a.size() - 1]) a.push_back(tmp);
  }
  a.push_back(-100000);
  n = a.size() - 2;
  for (int i = 1; i <= n; i++) {
    if (max(a[i - 1], a[i + 1]) < a[i]) maxl[a[i]]++;
    if (min(a[i - 1], a[i + 1]) > a[i]) minl[a[i]]++;
  }
  map<int, int> diff = minl;
  for (pair<int, int> p : maxl) {
    diff[p.first] -= p.second;
  }
  int isl = 1;
  int ret = 0;
  for (pair<int, int> p : diff) {
    isl += p.second;
    ret = max(ret, isl);
  }
  cout << ret;
  return 0;
}

map<int, int>maxl, minlに、高さをキーとし、その高さでそれぞれ極大、極小になる個数を保存。また、後者ー前者（=その高さでの島の増え幅）をdiffに保存。その後にforeach構文を使って、キーが小さい順にdiffの値を取り出して順に島の数を計算、最大値を出しました。

このとき、水位0でのdiffの値が無いと島の数の初期値をうまく定められないので、最初にmaxl[0]=minl[0]=0をして確実に値が取れるようにしています（最初の水位が0未満として、島の数の初期値を1、最大値チェックの初期値を0にしています。後者も1にしてしまえば良さそうですが、そうしてしまうと日本が全部海抜0mだったときにバグります）。

感想

いやー、C++でmapとforeachの組み合わせは最高ですね。mapに格納された値を順に取り出す方法ってforeach以外にあるんですかね。僕は知りません。値の範囲に比べて処理する要素の個数が少ないときは、この組み合わせでループ数を大幅に減らせることがあります。AtCoder Beginner Contest 105のD – Candy Distributionもその一つです。mapを使う以外にも、配列に出てきた要素をメモしておくという方法もあります。

ちなみにforeach構文はmapだけじゃなくvector配列などにも使えます。基本的な使い方はこんな感じです。map<T1, T2>に使うときはpair<T1, T2>で受け取ります（1つ目の要素にキー、2つ目に値が格納されます）。詳細はC++日本語リファレンス – 範囲for文を参照のこと（これ範囲for文って呼ぶんですね）。

for(型 変数: コンテナ(vector,mapなど)){
  //処理
  //コンテナの最初から最後まで一つずつ変数に格納されてループ
}

//例
vector<double>vec(n);
for(int i = 0; i < n; i++)cin >> vec[i]; //普通のfor文で入力
for(double d: vec){
  cout << d << endl; //vec[0], vec[1], ...が順に出力される
}

string str, rstr;
cin >> str;
for(char c: str){ //string型はchar型の配列
  if(65 <= c && c <= 90)c += 32;
  else if(97 <= c && c <= 122)c -= 32;
  //大文字と小文字を相互変換（ASCIIを想定）
  rstr.push_back(c);
}

E問題 – イルミネーション (Illumination)

概要

• JOI氏は、所有している並んだ\(N\)本の木\(1\sim N\)のうちいくつかに飾りをつける。
• 木\(i\)を飾り付けたときの美しさは\(A_i\)である。
• \(j=1,\ 2,\ \cdots,\ M\)それぞれに対して、木\(L_j,\ L_j+1,\ \cdots, R_j\)の内1本しか飾り付けられない。
• この条件を満たすように飾り付けたときの美しさの合計の最大値を求めよ。

問題ページ

制約

• \(1\leqq N\leqq2\times10^5\)
• \(1\leqq M\leqq2\times10^5\)
• \(1\leqq A_i\leqq10^9\ (1\leqq i\leqq N)\)
• \(1\leqq L_j\leqq R_j\leqq N\ (1\leqq j\leqq M)\)

入出力

思考過程

制限される区間が被ってなければそれぞれの中の最大を取れば良いんだけどなぁ。貪欲でうまくできないか？ あ、木1から順番に考えれば、今考えてる木を含む制限区間より前の美しさの合計の最大値はもう変わらないのか。ってことは、DPが使えるかも？ 今考えてる木までの美しさの合計の最大値は、「今の制限区間より前の美しさの合計の最大値」+「今考えてる木の美しさ」か、「一つ手前までの最大値」のうち大きい方になるのか。これでDPのテーブルを埋められるな。今の木がどの制限区間にも含まれないなら、単純に「一つ手前までの最大値」+「今考えてる木の美しさ」でいいな。これでこの問題が解けました（解説PDF並感）。

コード・提出結果

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<long> a(n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];
  vector<pair<int, int>> lr(m + 1);
  for (int i = 0; i < m; i++) {
    cin >> lr[i].first >> lr[i].second;
  }
  lr[m] = make_pair(n + 1, n + 1);
  sort(lr.begin(), lr.end());
  vector<long> dp(n + 1);
  dp[0] = 0;
  int nowlr = 0;
  for (int i = 1; i <= n; i++) {
    while (lr[nowlr].second < i) nowlr++;
    if (lr[nowlr].first > i)
      dp[i] = dp[i - 1] + a[i];
    else
      dp[i] = max(dp[i - 1], dp[lr[nowlr].first - 1] + a[i]);
  }
  cout << dp[n];
  return 0;
}

変数nowlrに「現在見ている木を含む制限区間の内、前端がもっとも小さいもの（の番号）」（今見てる木が制限区間に含まれないときは、それよりも後の中で一番最初にあるもの）を保持。その制限区間に今の木が含まれるかどうかを見て、それによってテーブルを埋める処理を場合分けしてます。

感想

例年D問題にDPの問題が出る傾向があると言われていますが、今年はE問題でしたね（実を言うと、Dを考えた時DP使えないよなぁ…ってちょっと悩んでました）。Dで使えなさそうだからEにDP問くるかも？って思いながら考えたおかげか、この問題は割とすんなり解くことができました。そういうの考えずに解いたら解けたのかなぁ。

F問題 – 座席 (Seats)

概要

• 20XX年、世界には\(N\)個の国があり、国1から国\(N\)まで順に並んでいる。
• この年の国際情報オリンピックには、国\(i\)からは\(A_i\)人の選手が参加する。
• 競技場には\(A_1+A_2+\cdots+A_N\)個の座席が一列に並んでいる。
• 不正防止のため、同じ国同士や隣国同士の選手を隣り合わせに座らせることはできない。
• この条件を満たす座席の割当方法の個数を10007で割った余りを求めよ。

問題ページ

制約

入出力

思考過程（小課題A）

（長考の末）わかんねｗ とりあえずnext_permutationで全列挙して部分点取るか。

コード・提出結果

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

const long fact[] = {1, 1, 2, 6, 24};
const long mod = 10007;
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  long ret = 0;
  vector<int> p;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    for (int j = 0; j < a[i]; j++) p.push_back(i);
  }
  do {
    bool trig = true;
    for (int i = 0; i < p.size() - 1; i++) {
      if (abs(p[i] - p[i + 1]) < 2) {
        trig = false;
        break;
      }
    }
    if (trig) ret++;
  } while (next_permutation(p.begin(), p.end()));
  ret %= mod;
  for (int i = 0; i < n; i++) {
    ret *= fact[a[i]];
    ret %= mod;
  }
  cout << ret;
  return 0;
}

next_permutation(C++)はalgorithmライブラリに含まれる関数で、配列などの要素を辞書順に組み替えてくれる関数です。
引数を指定して実行すると、

• 辞書順で現在の並びの次の並びがある場合は、trueを返し配列を並び替える
• 現在の並びが辞書順最後の場合は、falseを返す

という挙動をします。なので、並べ替えたい要素を最初にソートしてからdo～while構文の条件式にそのまま入れると、すべての並べ方を列挙して処理することができます。今回はこの前列挙の中で、条件を満たすもののみをカウントするという処理をしています。

感想

20点（=6+14点）はそれほどややこしくないDPだったみたいです。割と時間があったのでこの解法くらいは考えるべきだったかなぁ…

ちなみに満点解法（挿入DP）はめちゃめちゃ難しいです。どれくらい難しいかって言うと、本選出場有資格者（高２以下）の中で完答者が2人しかいません。やばいね。ちなみにその完答者は競プロツイッタラーの間では有名な天才双子くん（くん付けなんておこがましいけど他にいい呼び方が思いつかなかったので…）だったみたいです。やっぱりすごい人ってどこの世界にもいるもんですねぇ。

まとめ（というか回顧録というか怪文書というか）

ここからがタイトルにある「読み甲斐があるかもしれない話」です。

僕、実はJOIに高１から参加してたんですよね。でも高１・高２のときは300点しか取れずにBランク止まりでした（DPすら知らない弱小プログラマー）。その頃は「こんな問題どうやったら解けるんだ…？」と、高３の時にこんなに点数取れるとは夢にも思っていませんでした。けれど、高２のJMO本選爆死した後に「AtCoderをやろう」ってやけくそに心に決めて、それからずっとコンテストに出続けて精進をしてたら、いつの間にかこんなに成長していました（たまたま問題が良かったのかも知れないけどｗ）。自分で心に決めて続けてきたことが初めて実を結んだ体験で、とても感慨深かったです。

この記事を読んでくれてる人の中にも「何かをやりたいけど、どうせうまくいかないしなぁ」みたいに感じてる人がいるかもしれません。そんな人は是非、１年間でも半年でもいいから、少しだけでも「続けてみよう」って決心して、そして本気で取り組んでみてほしいです。やったこともないことが自分に合っているかどうかなんて自分にはわかりません。１年後、良い成果が出てるかもしれないし、出てないかもしれない。でも結果が出てなくてもいいんです。人間ってシングルコアじゃないですから。色んなことを並列して行えるんです。決して無為な時間にはなりません。

高校生で科学が好きなら、例えば数オリ・物チャレ・化グラ・情オリ・科学の甲子園といったイベントがたくさんあります。ほかにも、小説を書くとか、興味のある分野を先取りして学んでみるとか、様々な形の「チャレンジ」がそこら中に転がっていると思います。

大事なことなので二度言いますが、やってみていい結果が出なくたっていいんです。そのときはその時です。それよりも、後になって「もしあのときからやってたなら今頃～」と後悔する方が、よっぽど悔しいし、辛いです（実体験）。後から「やっぱりやってみたかった」と思っても、内容によってはチャンスはもう二度と訪れないかもしれません（科学オリンピックなどもいい例です）。

……とここまで書いておいてうまい締めが思いつきません（緊急事態だ）。まあでも僕の言いたいことはここまでに詰めきったつもりです。考え方は人それぞれですから「読んだ人は今すぐこれに従いなさい！！」なんてことは毛頭思ってません（むしろネットの記事一つ見て考え方をコロコロ変えるのはよろしくないでしょう）が、人生観（？）の一つだと思ってちょっとでも参考にしてくれると嬉しいです。

以上です。