えでゅふぉ 55
題意: n ページからなる本があり現在 x ページ目にいる。一度操作をすると前に d ページもしくは後ろに d ページ分飛ぶことができる（ただし0以下なら1になりn+1以上ならnとなる）このとき y ページ目に到達することができるか。できるなら最小で操作何回でいけるか。
このクエリを t 回分解く。
解法: ためす。mod d的には3通りしかないので。
反省:実装・題意把握 遅 最初例が間違っているのに騙された
題意: GもしくはSからなる文字列がある。今文字列のどこかを一回入れ替えることができる。Gの連続部分長は最大でいくつになるか。
解法: まず連続している部分ごとにまとめる。Sの長さが1なら両隣をくっつけることができる。Gの連結成分の数によって場合分けが生じるので注意。
反省:実装 遅 場合分けの処理が下手でバグりまくった。
1082C - Multi-Subject Competition
題意: n 人の人と m 個の科目があり，それぞれの人には担当できる科目（一つ）とそれに対するスキル（-1000〜1000） が定まっている。
正整数 k およびいくつかの科目を選び，各科目ごと担当できる k 人を選んで全員のスキルの和をチームのスキルとみなす。
チームのスキルの最大値を求めよ。
解法:科目ごとに担当できる人のスキル値を保持し，大きい順にソート（nlogn）。上からx人目までの和をvec_score[x]に挿入。
vec_score[x]のなかで正の値をとるもののみ加算し値をans[x]としたときans[x]の最大値を求めれば良い。
反省:素直な問題だが発想にてこずった。実装は比較的ストレートにかけたがオーバーフローした（アホ）
1082D - Maximum Diameter Graph
題意: n 個の頂点があり，各頂点には正整数 a_i が書かれている。この n 個の頂点を用いて木を作る。ただし頂点 i から伸びる辺は a_i 個以下である。
このような木を作ることが可能か判定せよ。構成可能ならそのうち直径が最大になるものをひとつ与えよ。
解法:まず１より大きい数字をもつ頂点を横一列につなげる。そこに次数1の頂点をどんどん付け足すだけで良い。a_i = 1となる頂点が m 個あるとすると，直径は (n-m) + min(m, 2) となるのであとは頂点の対応をきちんと求めればok
反省:最小だと思って「大きい数字を持つ頂点をどんどん繋げて」とか考えて時間食ってました。問題文はよく読もう。ただ最小と言う誤読をしたことを加味しても実装がめっちゃ遅かったけど。流石に難易度的に最小だと決めつけてやっていた自分が悪い。
題意: 長さ n の数列がある。ある区間 [l,r] と整数 k を選んで区間 [l,r] 内の数に全て +k するという操作を行うことができる。(kは負でもよい)この操作後に数列内に c は最大でいくつ存在するか。
解法:整数 d に対して f(d,[l,r]) を [l, r] 内にある d の個数とすると，求めるべきは
f(c,[1, l-1]) + f(d, [l, r]) + f(c, [r+1, n])
の最大値と言うことになる。これは以下のように式変形可能
f(c,[1, n]) + f(d, [l, r]) - f(c, [l, r])
一項目は定数で三項目を小さくしたいので[l,r]についてa[l]=a[r]=dであることが必要となる。したがって数列内に存在するdに対してa_i=dになる添字を取ってきて，上記部分和の最大値を求める。この部分和問題については添字の個数xに対してO(x)で解くことができ，したがって全体でO(n)で解くことができる。
実装中。
反省:最大部分和がdpで求まることを学んだ。
題意:未読
題意: 単純グラフが与えられ，頂点と辺それぞれに重みが定まっている。このグラフの部分グラフの重みを (辺の重みの和) - (頂点の重みの和) で定める時，その最大値を求めよ。
解法:考え中
