これいる？

前半の解説はこちらのブログに詳しいです．

A – 2 倍チェック / Is It a Number?

#include <cctype> をすると isdigit(c) というのが使えて，c が数字かどうかを判定できます．返り値は 0 か 0 以外なので，以下のようなコードではこわれうるのに注意です．

int main() {
  std::string s;
  std::cin >> s;
  bool valid = true;
  for (auto c: s) valid &= isdigit(c);
  if (valid) std::cout << std::stoi(s) << std::endl;
  else std::cout << "error" << std::endl;
}

詳しくは以前の記事に書いてあります．

もちろん，'0' から '9' までは連続して並ぶことが保証されていますから，'0' <= c && c <= '9' と判定してもよいです．

雰囲気ちょっと似てる．

B – 増減管理 / Up and Down

増減を管理します．言われた通りにやります．

C – 3 番目 / The Third

std::sort というのがあります． std::nth_element というのもありますね．

D – 重複検査 / Duplicated?

いろいろやり方はあると思います．

各値の出現回数を数えて，0 回のものと 2 回のものを見つけるのが楽だと思います．

int main() {
  int n;
  std::cin >> n;

  std::vector<int> count(n+1);
  for (int i = 0; i < n; ++i) {
    int a;
    std::cin >> a;
    ++count[a];
  }

  int zero = -1, two = -1;
  for (int i = 1; i <= n; ++i) {
    if (count[i] == 0) zero = i;
    if (count[i] == 2) two = i;
  }

  if (zero == -1) std::cout << "Correct" << std::endl;
  else std::cout << two << " " << zero << std::endl;
}

E – SNS のログ / Restore

言われた通りにやります．フォローフォローで \(i\) 番目の人のフォローを見るとき，\(i-1\) 番目までの人によってフォローした人を見ないように気をつけましょう．

他にも，自分自身をフォローしないように気をつけましょう．

F – DoubleCamelCase Sort

大文字小文字の判定には #include <cctype> で使える isupper(c) や islower(c) が便利です． 'A' <= c && c <= 'Z' などもいいですが，規格としては英字が連続していることは（というか ASCII であることが）保証されていないので気をつけましょう．まぁ多くの環境が ASCII だろうしアレなんですけど．

で，単語ごとに切り出せたら，それらを小文字にしてソートします．小文字にする際は tolower(c) が便利です．

あとは，toupper(c) で先頭と末尾を大文字に直して，出力すると終わりです．

Python だと簡単に書けますね．

import re

s = re.findall(r'[A-Z][a-z]*[A-Z]', input())
s.sort(key=lambda s: s.lower())
print(''.join(s))

G – 組分け / Division

全ての組分けを作り，各々について幸福度を計算し，その最大値を求めると終わりです．

全ての組分けを作るところが初心者的には難しいパートだと思います．

\(i\) について \(0\) 以上 \(3^n\) 未満の整数でループし，この \(i\) が組分けを表すとします．それで，\(j\) 番目の人は \(\lfloor i / 3^j\rfloor \) を \(3\) で割ったあまりのグループに入れることにする，という方法が一番楽だと思います．

pow(3, n) をすると誤差でこわれないか心配なので，整数でやりたいです．

int main() {
  // 入力略
  int pow3 = 1;
  for (int i = 0; i < n; ++i) pow3 *= 3;
  for (int i = 0; i < pow3; ++i) {
    std::vector<int> g(n);  // g[j] が j 番目の人のグループを表す
    for (int ii = i, j = 0; j < n; ++j) {
      g[j] = ii % 3;
      ii /= 3;
    }
    // スコア計算略
  }
  // 出力略
}

他のやり方として，再帰関数を使うとか，ビット全探索を二重にして \(O(3^n)\) になるやつをするやつなどが考えられます．

int whole = (1 << n) - 1;
for (int i = 0; i <= whole; ++i)
  for (int j = i; j; j = (j-1) & i) {
    int ga = j;
    int gb = i & ~j;
    int gc = whole & ~i;
    // ...
  }

つまらないコーナーケースに気を払わなきゃなのでおすすめはしません（えびちゃんは本番ではこれをしました）．

H – まとめ売り / Bulk Selling

ちょっと難易度が上がってきたかな．

次のようなクエリを処理すると見ます．

\(x\) 番目の品物を売る
奇数番目のセットを売る
奇数番目のセットと偶数番目のセットを売る

偶数番目のセットと奇数番目のセットで，やることは同じなので，以下では奇数番目のセットのことだけ考えます．ということで，次のクエリを処理できれば十分ということになります．

\(x\) 番目の品物を \(a\) 個売る
全種類の品物を \(a\) 個ずつ売る

1 つめのクエリだけなら簡単です． 2 つめのクエリだけでも簡単です（全体のうち在庫が最小のもの一つの個数さえ覚えておけばよいので）．

そこで，次の二つを覚えることにします．

セットとして売った個数（商品数ではなくセット数）\(s\)
（単品販売のみを考慮した）品物の在庫の最小値 \(m\)

すなわち，\(i\) 番目の商品の実際の在庫の数は \(c_i - s\) となります． 1 つめのクエリではこれを元に判定します．

また，全体の在庫の最小値は \(m - s\) として計算できます． 2 つめのクエリではこれを元に判定します．

実際に販売が行われたら \(s\)，\(m\)，\(c_i\) を適切に更新します．

これらによって解くことができます．なお，セグ木などを使うと考察をスキップして解けると思います．

I – 部品調達 / Procurement

bit DP と呼ばれるテクが有効です．これ，競技プログラマ以外はどの程度できるものなんでしょう．あるいは別のやり方で解いたりするんでしょうか．

まず，配列 dp を考えます． dp[S] を部品の集合 S を得るための最小コストとして定義します． S は集合を二進数でエンコードした整数とするのが楽です．

たとえば，S = 10011 は集合 \(\{0, 1, 4\}\) に対応します．下（右）から 0-indexed で見て 1 になっている部分が集合に含まれるという意味です．

部品の集合 T をコスト c で買えるとき，dp[S|T] より dp[S] + c の方が安ければ，dp[S|T] についてよりよい値が見つかったことになります．

コードで書くと次のようになります．

std::vector<int> dp(1 << n, inf);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
  for (int j = 0; j < (1 << n); ++j) {
    // s[i] = i 個目のセット中の商品の集合
    // c[i] = i 個目のセットのコスト
    int nj = j | s[i];
    int nc = dp[j] + c[i];
    dp[nj] = std::min(dp[nj], nc);
  }
}

dp[(1 << n) - 1] が inf なら達成不可能です．そうでなければ，その値が求めるコストとなります．

ほぼ既出では？まぁ典型なので既出とか関係なくサクッと通してほしいナァ...

J – 地ならし / Leveling

a[h][1] と a[h][w] と a[1][w] を結ぶ道の最小コストを求めたいです．

a[h][1] から a[h][w] に行って，そこから... と考えるのは大変そうです．

そこで，ある一点 a[i][j] は必ず道に使うと決め打ちしてみましょう． a[i][j] から上記の三点への最短距離の合計を考えます．

全ての a[i][j] を試して，これの最小値を求めると，それが所望の最小コストであることが示せます．

最小コストを実現する道を考えたとき，上記の三点への経路に枝分かれしているようなマスが存在するためです．イメージは次の AA の点 R です．道が * です．

.......*
......**
....***.
....*...
****R*..
*....***

R が三点のいずれかの場合は，その点への経路が空と見ることができます．

そこで，a[i][j] から Dijkstra 法などを行い，三点への距離を求めるとよいです（a[i][j] 自体のコストも加える）．

実際には，三点から Dijkstra 法をしておくことで，各 a[i][j] について定数時間で計算できると思います．（制約的に何やってもよさそうだったので，本番は毎回 Dijkstra していました．）

K – 巨大企業 / Conglomerate

これはグラフです．特に木と呼ばれるものですね．知らない人はググるとよいです．以下では，基本的な用語は知っているものとして進めます*1．

頂点 \(1\) を根とする木を考えます．頂点 \(u\) と頂点 \(v\) に共通する祖先を考えます．すなわち，\(u\) から根方向に辿って到達できるノードと，\(v\) から同じく到達できるノードの共通部分です．このうち，最も根から遠いもの（\(u\) や \(v\) から近いもの）を最深共通祖先 (lowest common ancestor; LCA) と呼びます．

さて，求める条件「\(u\) は \(v\) の部下である」は，この LCA を使って「\(u\) と \(v\) の LCA は \(v\) である」と言い換えることができます．

そして，これは（競技プログラマ以外にとって）どの程度有名かわからないんですが，ある二点の LCA は（線形時間の前処理によって）定数時間で答えるアルゴリズムがあります*2．

よって，それなどを行うことで，この問題を解くことができました．

あるいは，ダブリングなどを用いてクエリあたり \(O(\log(n))\) 時間で答えることもできます．各頂点について \(1\) 個上，\(2\) 個上，\(4\) 個上，\(8\) 個上，... の頂点を覚えておくことで，ある頂点から \(k\) 個上の頂点を \(O(\log(k))\) 時間で求められます．これに加え，各頂点の深さも覚えておきます．頂点 \(v\) の深さを \(d(v)\) と書くことにします．それにより，「\(d(u) > d(v)\) かつ \(u\) から \(d(u)-d(v)\) 個上の頂点は \(v\) である」かどうかを判定することでクエリに答えることができます．

もっと「殴ってない」感じの解法も説明します．まず，根から DFS したとき，頂点 \(v\) を最初に訪れるタイミングと最後に訪れたタイミングがいつかを覚えておきます．頂点 \(v\) が頂点 \(u\) の部下である（部分木に属している）ことと，\(v\) を最初に訪れてから最後に訪れるまでの間に \(u\) を訪れることは同値なので，そのタイミングを比較することで答えることができます．大がかりなデータ構造を用いなくても前処理 \(O(n)\)，クエリ \(O(1)\) 時間で処理できます．

L – グラデーション / Gradation

最小全域木を知っていますか？

たかだか 5 つの使わなくてもよい頂点はどう扱いましょう？各頂点について使うかどうかを決め打ちしても \(2^5 = 32\) 通りしかないので，全パターンを試せばよいです．

使える頂点が決まったら，その各ペアを結ぶ辺のコストを計算します．辺ベースでやってしまうのが楽そうなので Kruskal 法で実装しましたが，Prim 法や Boruvka 法などでも解けると思います．

M – おまかせ / Auto Choice

ある程度慣れた競技プログラマであれば，問題文を見た瞬間に二分探索を書き始めると思うんですが，そうでない人はどう考えるのかが気になります．

ある \(x\) について，「適切な合成を行うことで，幸福度 \(x\) を達成することが可能か？」という条件を考えます．境界が存在して，それ以下では達成可能で，それを超えると不可能になることがわかると思います．この境界を二分探索で求めます．

あとは，\(x\) を決め打ちしたときに，「適切な合成」をどう行うかを考えればよいです．選ぶ添字の集合を \(S\) とすると，求める条件は次のように表せます． \[\frac{\sum_{i\in S} b_i}{\sum_{i\in S} a_i} \ge x.\] 分母を払うなどをして，次のように変形できます． \[\sum_{i\in S} (b_i-a_i x) \ge 0.\]

左辺が大きいものから取るのがお得なので，その順でソートします．ヘルパーは 1 体までしか取れないので，適当に場合分けをします．今見ているのがヘルパーかつ，すでにヘルパーを使ったならスキップです．

5 体選んだところで，上の総和が非負になっているかを判定します．

今回，整数ではなく実数での二分探索なので，（誤差などの関係で）回数を決め打ちして行うのがよさそうです．普通の問題設定であれば，\(\log_2(10^{27}) \approx 90\) 回程度回せば十分でしょう．

類題

N – 整地 / Land Clearing

イベントソートとか呼ばれるやつっぽいような．

座標 \(0\) から右に向かって見ていくことにします．今見ている座標に車の右端を合わせるときのコストを管理し続けます．

石を区間として見るのではなく，区間の端点として見ます．すなわち，\(i\) 番目の石では，座標 \(l_i\) を見たときにコストが \(p_i\) 増えます．また，その石の影響を受けなくなるのは \(r_i+c\) ですから，座標 \(r_i+c\) を見たときにコストを \(p_i\) 減らします．

この際，増加と減少の順序が「減少が先」「追加が後」となってほしいので，座標全体を \(2\) 倍し，追加イベントの方は \(+1\) する，などをすると実装が楽になりそうです．

走査をしていき，座標が \(c\) 以上でのコストの最小値が答えです．（座標が \(c\) 未満では車が通れないためです．）

境界条件などには気をつけて実装しましょう．たとえば，車の右端が \(w\) を超えたりしないようにしましょう．

O – 持久戦 / Endurance

偏りのないサイコロが \(n\) 個あり，各々の各面に整数が書かれています．次のようなゲームを考えます．

好きなサイコロを一つ選び，振る
今までに出た整数の最大値以下なら，やめる
そうでなければ，選ぶところから繰り返す

この操作回数の期待値の最大値を求めたいです．

次のようにイメージします．

状態 j にいるとき k > j を出すと状態 k に遷移する
状態 j にいるとき k <= j を出すと終状態に遷移する

まず，サイコロの出目は座圧しておきます．座圧というのは座標圧縮のことです．知らない人はこれを解きましょう．

dp[j] を，「最後に j が出てからの操作回数の期待値」とします．

dp[j] は，愚直には次のように求めることができます．j の降順に求めます． dp[十分大きい] = 0.0 であることが基礎ケースとしてわかるためです．

i 番目のサイコロでは a[i][k] を出すことができるとします．まず，そのサイコロを振る一回は必ずカウントされます．また，1/6 の確率で a[i][k] が出ますので，a[i][k] > j であれば dp[a[i][k]] / 6.0 が期待値に加算されます．遷移先での期待値の最大値は求められているためです．

愚直には次のようになります．

dp[j] = 0.0;
for (int i = 0; i < n; ++i) {
  double cur = 1.0;  // 一回振るので
  for (int k = 0; k < 6; ++k)
    if (a[i][k] > j) cur += dp[a[i][k]] / 6.0;
  dp[j] = std::max(dp[j], cur);
}

これを実際に書くと，TLE してしまうので，高速化することを考えます．

さて，j の昇順に求めているのですから，毎回 j と大小比較するのは無駄がありそうです． j を処理する時点で補助配列 aux[i] の値が次のコードで得られる値と等しくなるように管理します．

aux[i] = 1.0;
for (int k = 0; k < 6; ++k)
  if (a[i][k] > j) aux[i] += dp[a[i][k]] / 6.0;

すなわち，最後に j が出ていて i 番目のサイコロを振ったときの期待値の最大値です．

i 番目のサイコロの出目に j が含まれるとき，j を処理し終えた時点で次のような処理をすればよいです．

aux[i] += dp[j] / 6.0;
max_aux = std::max(max_aux, aux[i]);

どのサイコロがいつ処理されるかは前処理で求めておくことができます．ここで，max_aux と aux[*] は 1.0 で初期化しておきます．

dp[j] の計算に必要なものは定数時間でアクセスできるようになり，次のように書けます．

dp[j] = max_aux;

ここまでできれば，あとはおまけです．一番最初に振るサイコロを考えます． i 番目のサイコロが a[i][k] を出せるとき，dp[a[i][k]] / 6.0 の合計 +1 が i 番目のサイコロで始めたときの期待値です．よって，これの最大値を求めればよいです．

本番はこれもセグ木を使ったんですが，いらないですね．

まとめると，次のようになります． m-1 は座圧後の出目の最大値です（種類数が m という方がいい？）．

std::vector<double> aux(n, 1.0);
double aux_max = 1.0;
std::vector<double> dp(m, 0.0);
for (int j = m-1; j >= 0; --j) {
  dp[j] = aux_max;
  for (auto i: ev[j]) {
    // ev[j] は出目に j を持つサイコロの添字
    aux[i] += dp[j] / 6.0;
    aux_max = std::max(aux_max, aux[i]);
  }
}

double res = 0.0;
for (int i = 0; i < n; ++i) {
  double cur = 1.0;  // 最初に振る一回
  for (int j = 0; j < 6; ++j) {
    // enc[x] は x の座圧後の値
    cur += dp[enc[a[i][j]]] / 6.0;
  }
  res = std::max(res, cur);
}

std::cout << std::fixed << std::setprecision(16) << res << std::endl;

感想

完走した感想ですが，educational speedrun のような印象を受けました．

？？「speedrun なら 1 時間で全完しろや」

えびちゃん「ごめん」

頭の中のながたかな「5 時間コンテストは長いですから、1 時間で全完してください。」

二時間半でエキスパートは確定したものの，一時間を残して満点だったので，speedrun と主張するには遅すぎそうですね．特に中盤あたりまで，淡々と典型問題をタイピングしていくのが疲れました．最後の二問も同じような気持ちで処理できるようになりたいものです．

初心者の人も，PAST の問題をサクッと解けるようにするといくらか力がつくんじゃないかなと思います．

裏話

最後に O 問題に O 問題のコードを投げたつもりで J 問題のコードを投げて RE や TLE が出たのが面白かったです．落ち着こうね．

コマンドラインで pbcopy < O.cpp のようにしてコピーしていて，二回目以降は C-r pbc などを入力しているはずなんですよね．なぜ J の方がコピーされたのかよくわかっていません．たぶん焦っていたんでしょう．

*1:面倒になってきたわけではないですよ．

*2:オイラーツアー+RMQ．RMQ に sparse table を使うと構築に \(O(n\log n)\) 時間かかりますが，実際には構築 \(O(n)\) クエリ \(O(1)\) の RMQ も存在します．えびちゃんは sparse table を使っちゃいました．

えびちゃんの日記

えびちゃん（競プロ）の日記です。

PAST アルゴリズム実技検定 #1 解説