ARC #035参加しました。
公式解説があるので説明は最小限です。
A – 高橋くんと回文
問題概要
与えられた文字列が回文か否かを判定する。ただし*はどの文字として扱っても良い。
解法
基本的には文字列の先頭から、対応する位置の文字が一致するかを文字列の中間まで判定すれば回文判定が出来ます。
今回の問題では、そのチェックの時にどちらかの文字が*である場合も、一致と判定すればOKです。
コード
B – アットコーダー王国のコンテスト事情
問題概要
解く時間がT_iかかる問題がN個存在する。このコンテストのペナルティはその問題を解くまでにかかった時間である。
全ての問題を解くときのコンテストペナルティの最小値と、最小値になる解き方の組み合わせ数のmod 1,000,000,007を答える。
解法
コンテストペナルティを最小にするためにはかかる時間が小さいものから解く形で、小さい値から加算していけば求められます。
また、最小値のパターン数は、同じ時間で解ける問題の解き方の組み合わせの数になるので、(時間n_1の問題数)の階乗*(時間n_2の問題数)の階乗…のように、全ての時間の問題数の階乗を書けた値がパターン数となるので、その過程でmodをとれば答えが求まります。
コード
C – アットコーダー王国の交通事情
問題概要
N個の街、M個の道路がある。道路が逐次追加されるので、その道路が追加された際のある街から違う街までの最短経路の総和を答える。
解法
最初にワーシャルフロイドで、初期状態の最短経路を全て求めます。
その後、追加された経路が既存の経路よりも小さければ、経路の更新処理を行います。
この時、チェックする必要があるのは、その追加された経路を使うパターンの経路(開始地点から新規道路に隣接するいずれかの街までの経路+新しい道路+新規道路に隣接する←とは別の街から終了地点までの経路)と既存の経路の大小関係のみで、これらの最小値が新しい最短経路になります。
そのため、全ての街の組み合わせについてこの計算で最短経路を再計算します。
そして、更新した最短経路の値から、合計値を計算してその値を出力します。
コード
最初、合計部分(変数sum)をintで定義したためにWAが出て、はまってしまった。
D – 高橋くんとマラソンコース
問題概要
格子状の道がある街で、道は東か北の方向へのみ進めるとする。交差点上にN個のチェックポイントがあり、以下のクエリが投げられるので処理を行なう。
- i番目のチェックポイントの位置を変更する。
- チェックポイント l1j からチェックポイント r1j までの異なる経路の総数と、チェックポイント l2j からチェックポイント r2j までの異なる経路の総数の大小関係を出力する。
解法
Cでハマってちゃんと問題を読む時間も取れなかったのですが、公式配信では経路値の管理をセグメント木、また経路値が大規模になるので、logで持つ(大小関係は必ず2倍以上になる保証があり、logで大小関係が取れない、誤差等を考慮する必要は無い)等すれば解けるようです。