AGC002 knot puzzle

https://atcoder.jp/contests/agc002/submissions/6740547

所感

AGC500も大した事ねえなガハハ(on 調子)

問題概要

N本のロープがあり、i番目のロープの長さはa_iである。
i番目のロープの右端とi+1番目のロープの左端が結ばれているとする。
長さL以上の繋がったロープのみ結び目をほどくことができるとき、すべての結び目をほどくことはできるか判定し、可能ならその手順を出力せよ。

取った方針

まず、ロープを結び目を含まないロープと結び目を一つ含む長さL以上のロープに分割できることが必要だと考える。(結び目を2つ以上含む場合、一つの結び目を解決した時点で長さがL未満になる可能性があるのでNG)
"結び目を一つ含む長さL以上のロープ" につながっている結び目のうち一番端のものは、ほどいても残るロープの長さがL未満になることはないので、ほどくことができる。
よって、"長さの和がLを超える隣り合ったロープが存在する" という条件を満たせば可能で、"長さの和がLを超える隣り合ったロープ" 以外の結び目を端から順番に解いていけばよい。

正しい方針

同上

得られた知見

・構築->必要条件から攻める

解くのに必要な要素

・必要条件を列挙したらなんだかんだで十分だったというアレ

周辺調査によって得られた知見

特になし