Gを解けるようにするぞ、Fまでで満足してちゃだめだ
46:04 6完 + 1ペナ 380位
A Middle Letter
S[S.size()/2]を出力すればいいです、言うことないよ～
(AC 1:05)
B Modulo Number
N - x ≡ 0 (mod998244353)なので、式変形をすると
N ≡ x (mod998244353)となるので、「Nをmodで割ったあまりを求めてください」という問題になります
ACLのmodintはこういうときのためにあるんですよね～
(AC 3:13)
C Convex Quadrilateral
正直よく知らなかったんですが、「多角形 凸 判定」で調べると判定方法が書いてあるのでそれをプログラムに書けばいいです
ベクトルの外積を使うやつは、整数で処理できるので誤差を気にしなくていいですね
(AC 10:13)
D Snuke Panic(1D)
今回は出てくるところが5か所しかなくて、こういう「不自然に小さいところ」は注目する価値がかなりあります
制約として 1 ≦ K ≦ 5って書いてあればすぐ気づくとは思うんですが、問題文中にさらっと書いてあることも多いですよね
さて実際の問題に移ります
いまいる高橋くんの位置は0,1,2,3,4の5通りだけ考えればよいです
dp[i][j] := 時間iに位置jにいるときの最大値
とDPを定義して解くことができます
遷移自体は典型的なDPですね、ちょっとバグらせてかなしい
(AC 22:01)
E Throwing the Die
期待値の典型的な考え方として「後ろから考える」があります
最近も出ていますね
今回も後ろから考えてみます
つまり、N回目のサイコロを振ったときにjが出たときの期待値から考えてみます
dp[i][j] := i回目のサイコロを振ってjが出たときの期待値
とDPを定義します
N回目であれば、jで確定するしかないのでdp[N][j] = jです
では、N-1回目のものを考えてみましょう
もし振り直すとするとN回目で1~6が等確率で出るので、(dp[N][1] ~ dp[N][6]の和) / 6になります
なので、dp[N-1][j] = max(j , (dp[N][1] + dp[N][2] ... + dp[N][6]) / 6)となります
これを同様に更新していけば答えがわかります
何で制約がN≦100だったんだろう？？誤差かな？
(AC 28:34)
F Well-defined Path Queries on Namori
まず、クエリ関係なしに一意に定まる条件を考えます
クエリにたくさん答える問題はとりあえず、Q=1のときにどう解くか考えないとどうしようもないと思います
なもりグラフ(N頂点N辺のグラフ)には、1つだけサイクルがあることに着目します
サイクル上の点同士では、左回り・右回りを選べるので一意に定まりません
そうでないときを考えてみます
サイクルのどの頂点から出ているかを考えると、
出ている頂点が同じ：1回サイクルに入って回ることはできない=一意になる
出ている頂点が違う：1回サイクルに入って回ることができる=一意にならない
ということがわかります
よって、
1. サイクルを検出する
2. どの頂点から出ているか特定する
ということができればよいです
1はさまざまな記事があると思いますので、そちらを参照してください。
2はサイクル上の頂点からdfsをすることなどで求められます
同一頂点から出ているかは、UnionFindなどで管理することでクエリに対して高速に答えることができます
(AC 46:04)
G Yet Another RGB Sequence
こういうのはRGを固めて1つのものとしてみるのが典型です(高校数学A)
そうすると、R-K個のR, G-K個のG, B個のB, K個のRGを並び替える問題となります
ただ、これを単純に並べると、RGにするつもりではなかったR,Gがたまたま隣り合ってかぶってしまうことがあるので注意しなければいけません
RGとして用いないR,Gについては「Rの後にGがきてはいけない」という条件がつきます
では、とりあえずRを並べておくことにして、Gをその後に入れればどうでしょうか？
R, RG, Bをあらかじめ並べます
この通り数は (R + K + B)! / (R! * K! * B!)となります
これはいわゆる重複順列の公式です
その後にGを並べます
GはRの後にはおけないので、置く位置の候補としてはRGの後 or Bの後になります
よって、位置の候補は K+B+1個あります(+1は先頭です)
ここに、G-K個のGを並べればよいので、「K+B+1個の箱に、G-K個のGを入れる通り数」を計算すればよいです
これは二項係数を使って求められるので解けます
言われてみれば単純なんだけど、発想するのに時間かかってしまった
(AC 101:10)
総括
Gを安定して解けることを目指そう
