2019/11/20

2019-2020 ICPC Yokohama regional B

最小値(盤面構築)

高さが与えられた盤面からそれぞれBFSをして、各グリッドについて達成可能な最低の高さを求める

→最低の高さの和が答え

(明らかな下界が答えとなる)

 

Codeforces 1255 B

グラフ構築

どの頂点も二つ以上の異なる頂点とつながっていればよい

→適当にすべての頂点を通る閉路を作り、残りの辺はすべて最小コストとなる頂点間に張る

場合分けの条件式に抜けがあった 提出前に確認するべき

 

Codeforces 1255 C

数列構築

最初の二つを決めれば漸次決定できる

multimapのあるイテレータ内を探索するとき、map.equal_range(key)でそのkeyの範囲をpairで取得できる

 

Codeforces 1255 D

盤面構築

連結にしたい→ヘビ型

ヘビ型の操作→一行おきに行をreverseしておくと楽

 

 

 ARC11 B - ルイス・キャロルの記憶術

構文解析

出力フォーマットに注意 空白は前に付ける方が例外処理がしやすい

(最後尾より先頭の方が検出しやすい)

 

Codeforces 1255 E

最小値

各箱の中身の数を同じ数で割れるようにしたい

0,1だけなら総和の因数でグループ分けしていけばよさそう

→素因数でいいね

→0,1以外でもそれでいいね

 

2*3*5*7...*31≒10^12なので、総和の素因数ごとに調べて間に合う

素因数個ごとにチョコをグループ分けして、グループのチョコのindexの中央値にまとめる