ABC062 http://abc062.contest.atcoder.jp
ARC074 http://arc074.contest.atcoder.jp
【ARC074/ABC062】
— AtCoder (@atcoder) 2017年5月20日
コンテストは終了しました。ご参加ありがとうございました。
解説PDF:https://t.co/Wpk2kKKcJz
解説動画:https://t.co/6I4t8RR6Ru
以下、解説
A. Grouping
http://abc062.contest.atcoder.jp/submissions/1299697
色んな書き方があるかと思うが、mapでグループ番号を保持してやった
B. Picture Frame
http://abc062.contest.atcoder.jp/submissions/1299731
これもいろんな書き方があると思うが、出力の際につけるようにやった
C. Chocolate Bar
http://arc074.contest.atcoder.jp/submissions/1295788
分け方を全通り試した。
関数solAでは縦に3つ分ける、横に3つ分ける方法を試す。
これはなるべく均等にやればよい。
関数solBでは縦に1度切ってから片方を上下に切るか、横に1度切ってから片方を左右に切る。
上下に切る、左右に切るときは、なるべく均等に分けるのが最適なので、そのようにやる。
D. 3N Numbers
http://arc074.contest.atcoder.jp/submissions/1296819
要素を消す前に前半と後半に分ける部分を全探索する。
全探索する部分を適切に探せるようになると良い。
前半x個、後半y個であるとすると、前半からx個中N個大きい方から取ってくる、後半からy個中N個小さい方から取ってくるようにすると、スコアを最大化できる。
その為、
B[i] := [0,i]で大きい方からN個取ってきた時の総和
C[i] := [i,3N-1]で小さい方からN個取ってきた時の総和
を適切に計算できれば、スコアを計算できる。
この計算はpriority_queueを使って行う
例えば最大値を取ってくる処理ならpriority_queueで最小値が出てくるようにしておいて、
queueのサイズがNを超えたら、queueから最小のものをとって総和から引く。
これを繰り返すと高速に計算できる。
E. RGB Sequence
http://arc074.contest.atcoder.jp/submissions/1300197
dp[r][g][b] := 最も右に赤がある位置がr,緑がg,青がbであるときの塗り方の組合せ
dp[0][0][0] = 1として、ループを回しながら数え上げていく
dp[r][g][b]では、既に塗られているのはma = max(r,g,b)マスまでだと分かる
そのため、塗り方としては、
- ma + 1マスに赤を塗る dp[ma+1][g][b] += dp[r][g][b]
- ma + 1マスに緑を塗る dp[r][ma+1][b] += dp[r][g][b]
- ma + 1マスに青を塗る dp[r][g][ma+1] += dp[r][g][b]
として更新していく。
あとは、制約についてだが、これはma == Rとなった時に判定を行えば良い。
この判定は、自分はmax,min,middleを用意して、それとLとの境界で行った。
もし、ルールを破っているならば、dp[r][g][b]=0としてしまえば良い。
あとは、ma==Nとなっているdp[r][g][b]の総和をとって答え。
F. Lotus Leaves
http://arc074.contest.atcoder.jp/submissions/1297740
最小カット問題に帰着でき、これを知らないと解くのは難しい。
hamayanhamayan.hatenablog.jp
こういう辺を消すのではなくて、頂点を消すような最小カット問題では、出ていく頂点xと入っていく頂点x'の2倍の量の頂点を用意するのが普通。
以下のように辺を張ってSからT'まで流す
- 移動できる頂点間(u,v)の頂点uから頂点v'へ容量1の辺
- 全ての頂点xの頂点x'からxへ容量1の辺