はまやんはまやんはまやん

hamayanhamayan's blog

AtCoder Beginner Contest 062 / AtCoder Regular Contest 074 解説

ABC062 http://abc062.contest.atcoder.jp
ARC074 http://arc074.contest.atcoder.jp

以下、解説















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の辺