AtCoder Beginner Contest 224 (ABC 224) に参加して， ABCDE 5完 415位でした．

A Tires

cout << (S[S.size() - 2] == 'e' ? "er\n" : "ist\n");

B Mongeness

4重ループで全数探索します．

C Triangle?

3重ループで全数探索します．

(x0, y0), (x1, y1), (x2, y2) を頂点とする三角形が正の面積を持つ条件は， (dx1, dy1) := (x1, y1) - (x0, y0), (dx2, dy2) := (x2, y2) - (x0, y0) として， dx1 * dy2 != dx2 * dy1 です．

D 8 Puzzle on Graph

次のような無向グラフを考えます．

  • ノードは配置全体．
  • 配置uが配置vから一回の操作で得られるとき，uとvの間に辺がある．

初期配置から，目的とする配置までの距離を普通のBFSで求めます．

C++なので，配置は普通に長さ9の vector<int> で持って， すでに配置を見たかどうかも set<vector<int>> で管理して 間に合いました．時間制限4秒のところ，1.4秒くらいでした．

E Integers on Grid

$a_i$ の大きい順に決定していきます．各行・列ごとに 「その行・列のマスから始めてできるもっとも長い回数」を記憶しておけば， $(r_i, c_i, a_i)$ の答は， max($r_i$行から始められる最も長い回数, $c_i$列から始められる最も長い回数) + 1 になります．$a_i$ が等しいものは一気に処理する必要があります．

F Problem where +s Separate Digits

コンテスト中は F は飛ばして G に行きました．

短いもので実験してみると，次のことが分かります．

  • 右端の数は，すべてで右端(一の位)の数として現れる．
  • 右から2番目の数は，半分で一の位，残りで十の位の数として現れる．
  • 右から3番目の数は，半分で一の位，残りの半分で十の位，残りで百の位の数として現れる．

以下同様なので，このとおりに計算すれば良いです．

G Roll or Increment

解けませんでした．残り15分の時点で以下の考察はできていたのに，デバッグしきれませんでした．

最適解は，次のような形になっています:

  • T, T-1, …, T-(k-1) の k 個では，出目を1増やす． (1 <= k <= T)
  • その他では，振り直す．

k を決めれば良いです．

上の k 個の位置での期待値の平均は (k - 1) / 2 * A です． したがって，振り直す位置での期待値を e とすると，

e = B + (k / N) * ((k - 1) / 2 * A) + ((N - k) / N) * e

となりますので，これを解いて

e = (N * B + k * (k - 1) * A / 2) / p

を得ます．T - k の位置では，k 回出目を増やすよりもランダムの方が 期待値が小さいので，

N * B + k * (k - 1) * A / 2) / p < A * k

が成り立ち，k はこれを成り立たせる最小の数ですから，二分探索で k を決定できます．