記録

6完, 7389人中668位でしたダメダメ水コーダーや緑コーダーに囲まれています　たすけて

解法

ふんわりしてます.

A - Middle Letter

A - Middle Letter
提出 0:16 (0)

解法

やる. 入力例を確認してなければFAだった. Unratedだからペナを犠牲にしても取りに行くべきだったか…

B - Modulo Number

B - Modulo Number
提出 0:56 (0)

解法

なんかちょっと考えちゃったけど, 普通に $N \% 998244353$ を求めればいい.
C++だと負の数を正の数で割ると欲しいのと違う数字が出てしまうので嫌な問題だが, Pythonでは実はそのままできる. みなさんPythonを使いませんか？.

C - Convex Quadrilateral

C - Convex Quadrilateral
提出 8:54 (0)

解法

幾何幾何してる. これつまり全部左回りか確認すればいいので, detを考える必要がある. ICPCでは幾何が出てくるのでやったことがある人が多いかも. といってもぼくは幾何は弱いので, 次の資料を見た.（17ページを参照！）

プログラミングコンテストにおける計算幾何入門
https://www.ioi-jp.org/camp/2017/2017-sp_camp-hide.pdf

D - Snuke Panic (1D)

D - Snuke Panic (1D)
提出 14:32 (0)

解法

一瞬愚直でやりたくなるが, どうみてもDP.
dp[i][j] : 時刻iでjにいるときの合計の最大値, とすれば, 問題文は幾何っぽいけれど, 整数時刻では整数地点にいると考えていい. あと穴から離れるのも無駄. だから $(10^5+1)\times 5$ サイズのテーブルでok.
遷移は隣から移動する, または移動しない. もしちょうど穴からすぬけが出てきたらゲットする.
時刻が $10^9$ 以下だったら, こっちもそれに座標圧縮して合わせる必要があり, ついでに少しdpが複雑になる. しかし今回は考慮しなくていいので, 助かった.

E - Throwing the Die

E - Throwing the Die
提出 18:36 (0)

解法

dp[i] を, N=iのときの答えとしよう. dp[1] = 3.5 はサンプルからわかる. dp[2] を求める. サイコロで4以上が出たら終了, 3以下ならもう一回振って期待値3.5に上がる. これを計算すると dp[2] = 4.25 となる.

具体的には $\frac{3}{6} \times 3.5 + \frac{1}{6} \times 4 + \frac{1}{6} \times 5 + \frac{1}{6} \times 6$ .
$A = ceil(dp(i))$ として, $A$ 以上なら終了し, $A$ 未満ならもう一回振って期待値を上げる.

正直なにが難しいか謎だった. 水Diffは高すぎる.

F - Middle Letter

F - Well-defined Path Queries on a Namori
提出 87:27 (0)

解法

$N$ 頂点 $N$ 辺連結グラフは典型で, 最近めっちゃ出てきてる. このグラフの特徴は, 閉路をただ1つ持っていること.
まずは閉路検出を行う. このとき, ただの閉路検出ではなく, 閉路をなす点も求めておく. これで無限バグ編に入った. 本当に黄コーダーか？閉路検出をしたあと, その閉路によってあとのやつらが分割され, 木と見ることができる. しかし, 閉路上の点でも, その木と接触しているやつは一意にパスが決まる. この「木に接触する閉路上の点」はただ1個存在する.

だから条件は
1. 閉路上の2点は一意じゃない.
2. 分割されたあと, 同じ木内の2点は一意.
3. ある木に接触する閉路上の点と, それに属する頂点は一意.
4. ある木に接触する閉路上の点を共有する2つの木の頂点間は一意.
5. そうでなければ, 一意じゃない.

となる.

しかし解説をみるとより簡潔だった. でもさすがに水Diffは低すぎる. EにDiffを吸い取られているのか？

G - Middle Letter

G - Yet Another RGB Sequence
提出コンテスト後

解法

これは昔に作った問題とほぼ一緒だった. 'RG'を一緒にまとめ, △とでもおく. △,R,G,B たちの重複あり順列を求めれつつ, 包除原理でどんどん包除しまくる. しかしサンプルが弱い. もう一度いう. サンプルが弱すぎた！！
なぜこんなにもサンプルが弱いのか. 我々は数学的に考察を詰めたあと, 1行のミスも許されずに実装する他なくなった.

ぼくは'RG'の個数を $K$ 個以上含む部分列の数を求めようとしていた. アプローチはいいが, 結論としてぼくがダメだった理由は, $K>1$ のときに1,-1,1,-1, ... と繰り返す包除原理ではダメだったから. 包除原理の「係数」が異なっていたのだ.

$4, -6, 4, -1$ , $10, -5, 1$ , $6, -1$ , $1$ . これに対処する「係数」が存在するのだ. 係数決め会議を行おう.

プラマイも一緒に決めてしまう. このとき

そして, $K$ に対する包除原理の係数は $(-1)^{i-K} \binom{i-1}{K-1}$ でOKだということが予想できる. 本当か？証明すべきことは： $\sum_{i=K}^{N} \binom{N}{i} (-1)^{i-K} \binom{i-1}{K-1}$ である.（ $N\geq K$ ）

でOK. これで包除原理の拡張？が証明できた.
$K=0$ のときは少し特殊で, これは全部の順列を数え上げればいいのでeasy.
'RG'が $K$ 個以上含む文字列の個数から, $K+1$ 個以上含む文字列の個数を引いていけば「最後の包除」として解けた.

ちなみに想定解はもっとずっと簡単な方法だった.