結果
ABCDE5完(57:45 + 1ペナ) Performance: 1544
大きく詰まるところはなく5完できたのでとりあえず満足．
コード
各問題の振り返り
A
を出力するだけ
cmath の pow 関数は浮動小数点で計算するので，一応整数型で pow を自前で実装． 一応 long 型にしておいたが，制約的には int でも大丈夫なはず．
2分26秒
B
野球っぽいルールに従って得点を数える
累積和で効率的にできそうなことは気づいたが計算量は余裕があるため，問題文どおりに愚直にシミュレーションしたほうが実装ミスは少ないと判断．
5分23秒
C
3x3マスの盤面において，縦横の和が指定されたときのありうる盤面数を数える (俗に言う魔法陣)
基本はありうる数字の埋め方について全探索だが，9マスぶんの数字の埋め方のパターンは で大きすぎる．
探索する数を減らすため盤面の自由度を考えてみると，左上4マスだけ埋めればあとは自動的に決まることに気づく．
もっと盤面が大きければ DFS などで探索したいが，たかが4つなので4重for文の雑なコードで済ませた．
9分58秒
D
たくさんの半開区間が与えられたとき，それらの区間の和を最小個数の区間の和で表す問題．
区間の和だけが重要なので，区間が与えられた順番にはあまり意味がない．
そこで， の値でソートして考えると見通しがよくなる．
が小さいほうから区間を調べ，区間が重なっているかぎりつなげてひとつの区間にし，つながらないものが現れたら次の区間を開始する．
区間をつなげるときの処理をミスして1WA
14分35秒 + 1WA
E
与えられた不満度を最小にするような人の並び順を求める問題．
前から順に人の並び を決めることを考えてみる．
番目に人
を置くとき
，これにより発生する不満度はそれより後ろにいる人のうち
が嫌いな人のもつ不満度の和
になる．
前から順に各時点で増える不満度が最小になるように順番を決めていけば良さそうである． 厳密な証明はなしで提出したがAC．
公式解説にあるグラフ理論的な考え方を使えばこの貪欲法も正しさを証明できる．
25分23秒
F
配列の各要素を更新しながら，3重の累積和を求めるクエリに答える問題．
紙で計算して3重累積和の一般項を求めるところまではできたが，そこからがどうすれば効率よく計算できるか思い浮かばず時間切れ．
終了後解説AC．
で整理すればうまく処理できるというところが思い浮かばなかった．
実装にあたって，modint などを使わないと注意深く mod をとるのが結構面倒だった．
