SRM 710 div2

Writerの方の解説
codeforces.com

Easy

問題概要

　n要素の配列Aが与えられる。この配列の部分列の和を最大化したい。ただし、配列の最初の要素のA[0]を選択した場合、部分列の和の正負を反転させる。

解法

　一番最初を選ぶ場合はマイナスのものだけを選択することで最大となり、選ばない場合はプラスのものだけを選択することで最大となる。この両パターンで大きい方を返す。

Med

問題概要

　n要素の配列Aが与えられる。i番目の要素を選択するとA[i]を0にした後、i+1番目からA[i]個の要素に+1する。このときn-1番目の要素の次の要素は0番目の要素である。要素1つのみが正の数になるように要素を選択していく。このとき、どのように要素を選択していけば条件を達成することができるのか出力する。

解法

　0でないもっとも先頭の要素を選択することを繰り返し、要素の遷移をシミュレートしていく。

Hard

問題概要

　n頂点m辺の連結な無向グラフが与えられる。各頂点には0からn-1のラベルがつけられる。自己ループや二重辺がないことが保証されている。各辺および各頂点にコストが定められており、頂点iから頂点jのパスのうち最大の辺のコストと最大の頂点のコストの積がパスのコストとして定められる。d(i, j)を頂点iと頂点jを結ぶ経路の最小のコストとする。0 <= i < j <= n-1 の全てのi,jの組についてのd(i, j)の和を出力する。

解法

　Writerの方の解説のapproach1の方法についてです。頂点、辺をコストの小さい順に見ていき矛盾する点がなく暫定の最短コストよりも小さければ最短コストを更新します。正直ちゃんと理解できているか怪しいので嘘が含まれているかも…