問題ページ Planning Rolling Blackouts | Aizu Online Judge 解法 func(sx,sy,gx,gy) = (指定範囲で実現できる最大のグループ数, グループの需要のうち最大) とする。その領域を分割しないか、縦に分割するか、横に分割するかの3通りの遷移がある。 分割し…

問題ページ D - Many Go Round 解法 普通に部分和を求めるDPをしようとするとsum(a)<=10^8で状態数が大きすぎて不可能。ここで考察をすると持っておくべき合計は高々Mであることがわかる。dp[i][j] = (i番目の燃料までで休憩所jにたどりつくのに必要な最小の…

問題ページ C - 嘘つきな天使たち 考えたこと とりあえずグラフを書きたくなる 天使に隣接しているのは悪魔、悪魔に隣接しているのは天使になる 隣り合う頂点を違う色で塗り分けられればいいのでこれは二部グラフをつかって判定できる 二部グラフでなければ-…

問題ページ B: 駆け抜けろ！埼大山車部！！ - Maximum-Cup 2018 | AtCoder 考えたこと 制約が小さいし全探索 d[y][x][向き][右折した回数][左折した回数] = (通ったか) としてBFSをする 左折がa回、右折がb回なのに逆にしてたり曲がる回数の条件を達成する前…

問題ページ A: フィギュアスケート界の貴公子埼大選手 - Maximum-Cup 2018 | AtCoder 解法 距離dの位置にt+10秒のタイミングでm個投げ込まれる。距離dの位置はd秒で通過するのでd<=t+10であればその位置のぬいぐるみを取れる。 ソースコード #include <bits/stdc++.h> using</bits/stdc++.h>…