SRM629Div1Medium
問題
N個の飴の売店がある。飴には、N種類の形とN種類の味がある。各店は1種類の形で違う味の飴をそれぞれN1、N2個ずつ売っている。ひとつの味には2つの形が必ず存在する。
N種類全部の飴を手に入れるのに必要な飴の数を求めよ。
解法
ひとつの味には2つの形が存在するという条件により、ループ状のグラフになる。
一つの店に対しては
- 0: 何も買わない
- min(N1, N2) + 1: どちらかを買う
- max(N1, N2) + 1: どちらも買う
という操作が可能である。
ループを左回りと右回りで探索することにより、答えを求められる。
再帰を使って探索できるが、直線となるので直前の値を記憶するだけで十分である。
計算量
O(N)
