九州大学プログラミングコンテスト2018：E - Treeone
問題
解法
ある要素を inf にした場合，答えは２つに分けられた数列のそれぞれの中で完結する要素の総和が０である部分列の数の和になる．そこで，２つに分ける箇所を全探索し，それぞれについて前後の数列に当てはまる部分列がいくつあるか調べる．この時，元の数列の最初と最後から同じ要素が出てきた個数を数えて置き，それぞれ累積和を取ることによって，当てはまる部分列の個数を O(1) で知ることが出来る．累積和を取る際，元の数列の最初からのものだけを計算し，部分列の個数を求めようとするのは間違え（要素を０にする箇所をまたぐ部分列の個数も含んでしまうことになるから）．
解答
最初，要素を０にする箇所をまたぐ部分列の個数を全部の個数から引くことを考えていて実装が詰まってしまった．解説を読んで解法の通りに方針転換したが，実装がまた難しすぎて時間が大幅にかかった．
九州大学プログラミングコンテスト2018：D - Novelist
問題
解法
王都から各都市に行ったならばすぐに王都に戻るのが最適であるので，M 個の依頼からすぐにまた王都に戻ってくる時刻を１つに定められる．なので，２種類の依頼を１つにまとめてしまうことで，最大スケジューリング問題にすることが出来る．あとは，時間の区間を終わりが早い順にソートし，終わりと始まりが重なってはいけないことに注意して貪欲に選んでいけばよい．問題文より，最後はどこにいてもよいので，王都から各都市に行けるならば最後に行く．O(N + LlogL)．
解答
upper_bound() を使う際，事前に配列を sort() していなくて 1 WA してしまった．
技術室奥プログラミングコンテスト #3：E - デフレゲーム
問題
解法
何回目に操作が終了するかで場合分けをする．k 回目に操作が終了する確率は
(n / n) * ( ( n - 1 ) / n) * ( ( n - 2 ) / n) * ... * ( ( n - ( k - 2 ) ) / n) * ( ( k - 1 ) / n)
になる．k 回目までのさいころの目の数の和の期待値は，１回あたりの期待値が (n + 1) / 2 であるので，
k * (n + 1) / 2
になる．あとは 2 <= k <= n + 1 のそれぞれの k に対して確率と目の数の和の期待値を掛け合わせた和を求めればよい．確率を求める際，k ごとに一回一回求めていては計算量が O(n^2) となってしまうので，k - 1 回目の時の確率を利用する形で k 回目の時の確率を求めると O(n) にすることができる．
解答
さいころの目の数の和の期待値を利用せずに解こうとしていて 1 WA．確率については自分で一から求めることが出来た．
