2017/10/21の精進

AtCoder400点埋め

・ABC051D Candidates of No Shortest Paths

ワーシャルフロイドで全点対に対して最短距離を求める。頂点iから頂点jまでの最短距離をdist(i,j)、頂点iと頂点jを結ぶ辺のコストをedge(i,j)としたとき、dist(s,i)+edge(i,j)==dist(s,j)となるような始点sが存在するならばこの辺は最短経路に含まれ、そうでないなら含まれない。

・ABC054D Mixing Experiment

DPの練習問題でやった奴。

・ABC057D Maximum Average Sets

ソートして大きい方からA個の平均が明らかに最大。大きい方からi番目の値をv[i]とし、全体にv[A-1]はx個、大きい方からA個の中にv[A-1]はy個あるとしたとき、v[0]==v[A-1]ならx個からi(A≦i≦B)個選ぶ組み合わせの数の和を、そうでないならx個からy個選ぶ組み合わせの数を求めればいい。

・ABC061D Score Attack

スコアの符号を反転すれば、頂点1から頂点Nまでの最短距離になってベルマンフォードでとける。ただし、頂点1から負のループに含まれる頂点を経由して頂点Nに行く経路がある場合の判定をしなければならない。このような負のループがない場合、高々N-1回の更新で頂点1から頂点Nまでの最短距離が求まるが、ある場合はさらに更新していくと高々N-1回でこの最短距離が更新されるので判定できる。

・ABC064D Insertion

文字列を先頭から見ていって余っている左カッコの数xを数えていく。x=0のとき')'がきたら加えるべき左カッコの数lを1増やす。最終的にx=rとなったとすると、(l個の'(')+S+(r個の')')が答え。

・ABC070D Transit Tree Path

頂点Kを根とした木を作って、各頂点から根までの距離を計算しておくだけ。

・ABC073D joisino's travel

ワーシャルフロイドで全点対の最短距離を求めておくと、R個の町の訪れ方それぞれについて移動距離が簡単に計算できる。

・ABC075D Axis-Parallel Rectangle

長方形の左上と右下の座標を決めれば面積を求めるのは簡単。ここで、左上(右下)のx座標は点のx座標に現れるもの、y座標は点のy座標に現れるもののみを候補としていいので全て試せる。

・ARC058D いろはちゃんとマス目

(1,1)→(B,y)→(B+1,y)→(H,W)と移動すると考えればいい。

・ARC059D アンバランス

実はaa or a*aという形の部分文字列を含んでいればそれが答えで、含んでいなければアンバランスな部分文字列は無いということがわかる。(例えばa**aという形ではaを1文字増やすときaでない文字を2文字増やすことになるのでアンバランスに出来ない)

・ARC061D すぬけ君の塗り絵

(x,y)を黒く塗ったとき、(x,y)を中心とする3×3の正方形の各マスのみに関係する。周りが1つ以上黒く塗られるマスはO(N)個なのでmapなどで管理できる。

・ARC063D 高橋君と見えざる手

「町i-1までの最安値でリンゴを買い、町iでリンゴを売る」ということを差が一番大きい所でやるのが最適。町iでリンゴを買って町jでリンゴを売るのが最適になるような全ペア(i,j)について町iのリンゴの価格を1円上げれば高橋君の利益を1円下げられる。(町iのリンゴの価格は町1~町i-1までのリンゴの価格より安いので、得をすることはない、また各ペアは独立なので)

 ・ARC065D 連結

道路/線路に対応するUnionFind木における、頂点iの親をそれぞれroad[i]/rail[i]とする。頂点iとjが道路・線路で連結⇔road[i]==road[j]かつrail[i]==rail[j]なので、各頂点iについて(road[i],rail[i])==(road[j],rail[j])となるjがいくつあるか数えればよい。

言われればそうだけど、自力でおもいつけなかった。

・ARC068D Card Eater

同じ数が3枚以上あるときは、2枚ずつ消していけるので同じ数は2枚以下にできる。さらに2枚ある数を組み合わせるとどちらも1枚にできる。(3 3 4 4から3 3 4/3 4 4と選んで消すと3 4になる)そうすると2枚ある数が高々1個あって、それ以外の数は全て1枚という状況になる。2枚ある数がのこったときは、1枚の数と組み合わせて消すしかない。

・ARC073D Simple Knapsack

選ぶ個数をk個に固定すると、重さ0~3のものがあって重さの合計がW-w1*k以下となるよう選んだときの価値の最大値を求める問題になる。Wは非常に大きくなりうるが、重さが3以下でものは100個以下だから、W-w1*k≧300のときは全て選べるので関係ない。