ICPC2017 Asia Regional Tsukuba E Black or White
Dむずくて通せてないですごめんなさい。
問題
n個のセルが黒または白で塗られている。
セルの初期状態およびゴールの状態が与えられる。
セルは一度の操作で連続する1〜k個を好きな色に塗ることができる。
最小で何回の操作で全てのセルをゴールの状態にできるか求めよ。
制約条件
n, k≦50万
ICPC2017 Asia Regional Tsukuba C Medical Checkup
問題
とても読みにくい問題文。
n人の人がt秒以内に機械(m1, m2, m3, ...)を使う。
- 同時に一人一個の機械しか使えず、一つの機械は同時に一人でしか使えない
- 各人はm1から順にとばさずに機械を使う必要がある
- 各機械は、1番目の人から順に使用する。i番目の人の使用が終わったら即座にi+1番目の人に渡す
- i番目の人が機械を使うとき、どの機械もh[i]の時間がかかり、中断はできない
- 機械を渡された人が別の機械を使用中のとき、渡された機械はその人がその前の機械を全て使い終わってから（即座に）使い始める
このとき、各人が何個目の機械を使用中、あるいは何個目の機械を待っている状態であるかを求めよ。t秒の時点でちょうど機械を使い終わった場合、次の機械を待っている状態であるとする。
制約条件
n≦10万
h[i], t≦10^9
ICPC2017 Asia Regional Tsukuba B Parallel Lines
問題
平面上にm個の点が与えられる。その中から相違なる2n点を選び、n本の線分を作る。（nは自由）
n本の線分のうち、平行であるペアの個数を最大化したい。
そのようなペアの個数の最大値はいくつか。
制約条件
m≦16
座標は絶対値1000以下の整数
ICPC2017 Asia Regional Tsukuba A Secret of Chocolate Poles
問題
黒と白の円盤を積み上げてタワーを作る。タワーは以下の条件を満たす必要がある
- 一枚以上の円盤がある
- 円盤の厚さの合計はl以下
- 最も外側の円盤は黒
- 同じ色同士の円盤が隣り合ってはいけない
黒の円盤は厚さ1またはkのどちらかを選ぶことができて、白の円盤は厚さ1だけ。
条件を満たすタワーは何通りあるか。
制約条件
l≦100, k≦10
ICPC2017 国内予選 H 等積変形
問題
面積の等しい三角形A, Bが与えられる。
三角形Aに対し等積変形（二頂点を固定し、残り一頂点を三角形の面積が変わらないように動かす操作）を繰り返し三角形Aを三角形Bに重ねたい。
必要な操作の最低回数（あるいは4回以内にはできない）を求めよ。
