• バチャ

• 4問解けたのでなかなかいい感じ。まあ解きなおしなのでホントは全完しなといけないんですが。。。

ABC026 「高橋君の給料」

考察

• 入力情報に従って辺を張り、DFSすればいいのでは？って感じで考察終了

解法

• 入力情報に従って辺を張ることで木を作る。
• 深さ優先探索で、末端の社員から順番に給料を求めていく。

実装

• 実装に30分くらいかけてしまった。
• その時書いたコードがこれだけど、無駄が多い。
  • 自分で木を作ったくせに、visited[] で訪れたかを判定している。木では、一度訪れた頂点には二度と訪れないので、この配列は必要ない
  • vectorで給料を管理するより、Min, Maxだけを持てばよかった（最初はそうしようとしたけどうまくいかなかったからvectorを使った。）
  • DFSの終了条件が明示的に書いてないので読みにくい
• なので、リファクタリングした

コード

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> G[22];

int dfs(int from) {
   // 部下がいないなら1を返す
   if (G[from].empty()) return 1;

   int Min = 1e8, Max = -1;
   for (int to : G[from]) {
      int t = dfs(to);
      Min = min(Min, t);
      Max = max(Max, t);
   }

   return Min + Max + 1;
}

int main() {
   cin >> N;
   for (int i = 1; i < N; i++) {
      int b; cin >> b; b--;
      G[b].push_back(i);
   }

   cout << dfs(0) << endl;

   return 0;
}

感想

• 以前はDFSを書けなかったから解けなかったが、DFSにも少し慣れたためか何とか解けた
• 考察がすぐ終わったのはうれしい
• でも、DFSを行き当たりばったりで実装するから時間がかかってしまう。もっとスマートに実装できないもんかねー。
• この問題解いて気づいたんだけど、再帰関数の終了条件は明示的に書いた方がコードが読みやすい。あと、終了条件は関数の一番上に書いた方がコードが読みやすくなる。（あくまで個人の意見です...

ABC027 「倍々ゲーム」

考察

• まず、図を書いてみる。すると、完全2分木になっていることが分かる。完全2分木は下の画像を参考に。
• 完全2分木を見た時に、深さ1の時は高橋君の手番、深さ2の時は青木君の手番、深さ3の時は高橋君の手番、...のようになっている。
• つまり、完全2分木の深さが奇数の時は高橋君の手番で、そこに並ぶ数字は高橋君が取る可能性のある数字となっている。同様に、深さが偶数の時は青木君の手番で、そのに並ぶ数字は青木君がとる可能性のある数字となっている。

• ここで、勝敗条件を確認する。「$x$が$N$を超えたとき、最後に操作を行った人が負け」となる。僕は「～を超える」という表現が好きではないので、「$x$が$N+1$以上になったとき、最後に操作を行った人が負け」と読み替える。

• 次に、完全2分木のどの深さで$x$が$N+1$以上になるのかを考える。これは完全2分木を眺めていると分かる。完全2分木の深さ$d$でとり得る値の範囲は$2^d \leq 値 \leq 2\times 2^d - 1$となる。つまり、$d$の値をループで回して、$2^d \leq N+1 \leq 2 \times 2^d - 1$ を満たす$d$が、$x$が$N+1$以上になるような深さであることが分かる。

• ここで少し前の考察で「木の深さが奇数の時は高橋君の手番で、偶数の時は青木君の手番である」といったことを思い出す。$x$が$N+1$以上になるような深さ$d$が奇数なら、高橋君の手番で初めて$N+1$になる数が出てくる可能性がある。偶数なら、青木君の手番で初めて$N+1$になる数が出てくる可能性がある。

• （$x$が$N+1$以上になるような深さを$d$と呼ぶことにするっていうのを一応書いておく）

• ここでようやく、どうすれば2人が最善を尽くす手になるのかを考えることができる。

• $N+1$が高橋君の手番で出てくる可能性があるときを考える。この時の$d$は奇数となっている。

  • まず、高橋君にとっての最善手を考える。高橋君は自分の最後の手番で値が$N$以下になるようにしたい。そうすれば勝つことができる。なぜなら、高橋君の最後の手番と同じ深さには$N+1$があるため、次の深さ(青木君の手番)では確実に$x$は$N+1$以上となっているからである。
  • さて、高橋君が自分の最後の手番で値が$N$以下になるようにするには、深さ$d$でなるべく数が小さくなるようにしたい。図でいうと、なるべく値が左側に寄るようにしたい。そのためには、高橋君は毎回$2x$を選ぶのが最善手となる。もし高橋君が$2x+1$を選んだら、深さ$d$で$x$が$N+1$以上になる確率が上がってしまうだけなので高橋君にとって何の得もない。それにさっきも書いたけど、深さ$d+1$で$x$が$N+1$以上になることは保証されているため、高橋君はとりあえず深さ$d$で$x$を$N以下になるようにすることだけを考えればいい。
  • 次に、青木君にとっての最善手を考える。青木君は深さ$d$で高橋君に$N+1$以上の値を取らせたい。そうしなければ青木君は負けてしまう。なぜなら深さ$d+1$は自分の手番で、その時には$x$は確実に$N+1$以上になってしまうからである。つまり、青木君は深さ$d$の時の$x$の値いをなるべく大きくしたい。よって、青木君にとっての最善手は毎回$2x+1$を選ぶこととなる。

• $N+1$が青木君の手番で出てくる可能性があるときを考える。この時の$d$は偶数となっている。

  • これは上記の人物を逆にして考えればいいだけ。
  • 深さ$d$で$N+1$以上になってしまう可能性があるので、青木君はできるだけ数を小さくしたい。よって、青木君の最善手は常に$2x$を選ぶこととなる。
  • 逆に高橋君は深さ$d$で$N+1$以上の数を青木君に取らせたい。よって、高橋君の最善手は常に$2x+1$を選ぶこととなる

完全2分木

• 以下の2つを満たす2分木を完全2分木という
  1. 全ての葉(末端のノード)が同じ深さを持つ
  2. 葉以外のノードは全て2つの子ノードを持つ
• ただ、完全2分木の定義は本によって違うらしく、柔軟に受け取る必要がありそう

解法

• $2^d \leq N+1 \leq 2\times 2^d -1$となるような深さ$d$を求める。
• $d​$が奇数なら高橋君は常に$2x​$を選び、青木君は常に$2x+1​$を選ぶ。
• $d$が偶数なら高橋君は常に$2x+1$を選び、青木君は常に$2x$を選ぶ。
• 実際にシミュレーションすることで答えを求めることができる。計算量は$O(log{N})$となる。

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
   // 入力
   ll N;
   cin >> N;

   // N+1が出てくる深さを求める
   int depth = 0;
   for ( ; ; depth++) {
      if ( (1LL<<depth) <= N+1 && 2*(1LL<<depth)-1 >= N+1 ) {
         break;
      }
   }

   ll x = 1;
   int cnt = 0;
   while (1) {
      if (depth%2) {
         x = x * 2; cnt++;
         if (x >= N+1) break;
         x = x * 2 + 1; cnt++;
         if (x >= N+1) break;
      } else {
         x = x * 2 + 1; cnt++;
         if (x >= N+1) break;
         x = x * 2; cnt++;
         if (x >= N+1) break;
      }
   }

   if (cnt&1) {
      puts("Aoki");
   } else {
      puts("Takahashi");
   }

   return 0;
}

• もっときれいに実装できるだろうけど、今は理解することで精いっぱいなのでリファクタリング今度する。

感想

• むずい。ゲーム系の問題はすごい苦手。なので考察がすっげー長くなってしまった。こんなに時間かけてたらコンテスト終わっちゃうなー。。。
• この問題の理解度は70%位なので、少しモヤモヤが残ってる。
• 2分木の探索が$O(log{N})$なのは知識として知ってるど、理由は知らないのでなんとかしないとなー。

ABC028 「数を3つ選ぶマン」

考察

• 愚直にループで和を全通り求めて、setに入れればおしまいかなーって感じで考察終了。

解法

• 3重ループで和を全通り求め、配列に入れる

• 配列をユニークにする(この操作、必要ないかも？？？)

• 昇順にソートして後ろから3番目の数を出力する

コード

#include <bits/stdc++.h>
using namespace std;

int v[10];

int main() {
   for (int i = 0; i < 5; i++) cin >> v[i];

   vector<int> a;
   for (int i = 0; i < 5; i++) {
      for (int j = 0; j < 5; j++) {
         for (int k = 0; k < 5; k++) {
            if (i == j || j == k || i == k) continue;
            a.push_back(v[i] + v[j] + v[k]);
         }
      }
   }

   sort(a.begin(), a.end());
   a.erase(unique(a.begin(), a.end()), a.end());

   cout << a[a.size()-3] << endl;

   return 0;
}

• 結局set使わないほうがよかった。vectorに突っ込んでunique()すればユニークになるので。（コンテストではset使ったけど）
• 上位陣はもっときれいなコードだったけど、よくわからんからいいか。。。

別解

• 自分で考えて解くこともできる。解説は公式があげてる。
• これよくわかんない。

感想

• 愚直に解くとすごく簡単で、何も考えずに解ける。
• ちゃんと考えると難しい。ほんとは$O(1)$でできた方がいいんだよなー。。。
• うーん、なんかもやもやする。

ABC029 「Brute-force Attack」

解法

• DFSで全列挙
• DFSでa, b, cの順に探索していけば自然と辞書順になる。図を描くとたぶんわかりやすい。

実装

• コンテスト中はこんな感じのコード書いたけど、解説のコードがきれいだったのでそれを参考にリファクタリングする。

コード

#include <bits/stdc++.h>
using namespace std;

int N;

void dfs(string s) {
   if (s.size() >= N) {
      cout << s << endl;
      return;
   }

   for (char c = 'a'; c <= 'c'; c++) {
      dfs(s + c);
   }
}

int main() {
   cin >> N;
   dfs("");

   return 0;
}

感想

• 辞書順という言葉を読み飛ばしてたけど、ACできてしまった。
• 逆辞書順とか書いてあったら僕のコードじゃダメだったので、ちゃんと問題文読もうねってなった。

ABC030 「飛行機乗り」

考察

• 普通に空港A、B間を行き来すればいいだけなのでは？って感じで考察終了

解法

自分の解法

• 次の便を、配列を走査することで探す。
• ただ、毎回要素0から探すのでは計算量が$O(NM)$ になってしまう。
• なので、A, Bの配列をそれぞれどこまで走査したかを変数として持っておく。
• そうすることで、計算量が$O(N + M)$になる。

自分の解法のコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int N, M, X, Y;
int A[111111], B[111111];

int main() {
   cin >> N >> M >> X >> Y;
   for (int i = 0; i < N; i++) cin >> A[i];
   for (int i = 0; i < M; i++) cin >> B[i];

   ll t = 0; // 現在時刻
   int ai = 0, bi = 0; // 配列のインデックスを保持しておく。
   int cnt = 0; // 往復回数
   while (1) {
      // 空港Aから空港Bへ向かう
      for ( ; ai < N; ai++) {
         if (A[ai] >= t) {
            t = A[ai] + X;
            break;
         }
      }
      if (ai >= N) break;

      // 空港Bから空港Aへ向かう
      for ( ; bi < M; bi++) {
         if (B[bi] >= t) {
            t = B[bi] + Y;
            break;
         }
      }
      if (bi >= M) break;

      cnt++;
   }

   cout << cnt << endl;

   return 0;
}

想定解法

• 次の便を2分探索で探す。
• 計算量はたぶん$O(N log{N} + M log{M})$

想定解法のコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll N, M, X, Y;
ll A[111111], B[111111];

int main() {
   cin >> N >> M >> X >> Y;
   for (int i = 0; i < N; i++) cin >> A[i];
   for (int i = 0; i < M; i++) cin >> B[i];

   ll t = 0; // 現在時刻
   int cnt = 0; // 往復回数
   while (1) {
      // 空港Aから空港Bへ向かう
      int aPos = lower_bound(A, A + N, t) - A;
      if (aPos >= N) break;
      t = A[aPos] + X;

      // 空港Bから空港Aへ向かう
      int bPos = lower_bound(B, B + M, t) - B;
      if (bPos >= M) break;
      t = B[bPos] + Y;

      cnt++;
   }

   cout << cnt << endl;

   return 0;
}

感想

• 2分探索は思いつかなかったー。しかもにぶたんが想定解法とか。。。
• 実行時間的に、計算量間違えてそう。。。