ARC035 A, B, C 考察

arc035 A - 高橋くんと回文

前からと後ろからで 1 文字ずつ走査する。両方の文字が一致せず両方とも * でないものがあればそれは NO それ以外は YES 。

https://atcoder.jp/contests/arc035/submissions/16994978

arc035 B - アットコーダー王国のコンテスト事情

早く解けるものから順に解けばコンテストペナルティは最小になる。同じ時間で解けるものがあるときその並び替えの数だけ解き方がある。 BTreeMap で昇順に並べつつ個数を数える。現在の時刻とコンテストペナルティの合計を計算して最小値を求める。問題の時間ごとに 10^9 + 7 で剰余を取りつつ個数の階乗を求めてそれらをかけ合わせて解き方の数を求める。

https://atcoder.jp/contests/arc035/submissions/16995039

arc035 C - アットコーダー王国の交通事情

N 個の頂点と M 個の辺の無向グラフがある。各頂点間の最短距離の合計を S とする。 K 個の辺を追加するときそれぞれの S を求める。……という問題。

初期の各頂点間の最短距離はダイクストラ法などで O(N(N+M)logN) で求められる。 N <= 400 M <= 1000 なのでこれなら間に合う。ただこれを K 回の辺の追加ごとにやると K <= 400 なので間に合わない。

そこで初期の各頂点間の最短距離と X_i Y_i Z_i (1 <= i <= K) を使う。各頂点間の距離 (j から k の距離とする) を j から X_i までの距離と Z_i と Y_i から k までの距離で短くなるなら更新する。これによって K 回の O(N^2) で各頂点間の最短距離の合計を求められる。これだと間に合う。

https://atcoder.jp/contests/arc035/submissions/16995686

リングフィットアドベンチャー 100 日目 ワールド 16 レベル 159 。