精進メモ 2021/09/27~

気温の変化にやられて一日中鼻かんでます。

AOJ-ICPC

2169 Colored Octahedra

素直に全探索します。
next_permutationで全列挙し、ひたすら回転させました。

2249 Road Construction

ダイクストラをしてから、近い順に最小全域木を計算していきます。

2302 On or Off

それぞれのマスで通る時刻はわかっているので、マスごとに計算すればよいです。
$dp[i][j] = i$ 回目に通った後、電気がオンになっている/オフになっている( $j$ )ようなスイッチの切り替え方における最小コスト
と定義して計算していけばよいです。

2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)

チーム練です。

D. Cycle String?

出てくる回数が最大のものが $n$ 以下であれば、適当にソートして出力でOKです。
そうでない場合、 $s_{n}$ と $s_{2n}$ に最大のもの以外を置き、あとは前から回数最大のものを順に詰めていきます。
最大のもの以外が3個以上あるか、種類が3種類以上であれば問題の条件を満たします。
そうでない場合は構築できません。

E. Life Transfer

BITを7本くらい用意してごり押しました。
年齢の降順にソートして、車、バイク、乗客、の順で選んでいきます。
車を運転する人の人数を全探索していけばよいです。

F. Game on a Tree

ずるしました。
昔かっつくんが解いた時のツイートを皆で思い出してしまいました…
移動できる頂点に辺を張り直し、完全マッチングが存在すれば後手の勝ちです。
適当にDFSをして、葉から貪欲にマッチングさせて頂点があまるかチェックすればおしまいです。

ABC221

可もなく不可もなく。

C - Select Mul

2回誤読してコードを書きなおしました。
ビット全探索して降順ソートです。
leading zeroは無視してOKです(どちらにしろ答えが0になるので正しい答えが出ます)。

D - Online games

イベントソートして日付ごとに処理をしました。

E - LEQ

得意分野なので自分の体感難易度とまわりがズレていました。
数列の最初と最後を決めると、間の要素を任意に選ぶか選ばないか、になります。2の冪乗です。
$i,j$ を決め打ったときの選び方は、累積積のようにして $O(1)$ で計算できます。
あとはBITで累積積をまとめて計算すればいいです。

F - Diameter set

直径の偶奇で場合分けをしました。
奇数距離の場合は、中心が2頂点に分かれます。それぞれの中心で木をわけたとき、それぞれで直径として選べる端点が計算できますが、2つの木のそれぞれから1つずつ選ぶしか方法がありません。
よって、それぞれの木の候補の数の積が答えです。
偶数距離の場合は、中心が1つになります。中心と隣接している頂点との辺で木を複数に分けたとき、先ほどと同様に直径として選ぶ候補がそれぞれの部分木で数えられます。それぞれの部分木から最大で1つ(0でもよい)頂点を選べるので、(個数 + 1)の漱石を計算します。
ここから、一つも選ばれないパターンと、一つだけ選ばれるパターンが条件を満たさないので引けば答えです。　　

ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。