L = 33000

任意の2つの頂点の組に対してクエリを送ることで、それぞれの頂点間に辺があるかを判定できます。質問回数は32640回なので制約に収まります。

L = 10000

L=6400と同じ方針で少し非効率な探索をするとL=8000~9000程度になります

L = 6400

貪欲に頂点を追加して、頂点が連結にならないように取ってその頂点を色1とします。そしてその頂点を除いて同じことを繰り返すと、未染色の頂点の連結成分の最大の大きさが1回ごとに半分以下になることが示せるので、高々8色で染色できます。 ここで全ての頂点に対して、その頂点と異なる色全て+その頂点 のようなクエリを行うことでその頂点とその色間に辺があるかどうかがわかり、同じ色は隣接していないので二分探索をすることで8回の質問で1辺が特定できます。これを適切に実装すると、\(L=256 \times 8 + 256 \times 7 +255 \times 9 = 6135\)となり、制約に収まります。

L = 4600

まず最初の染色順を乱択することで、十分高い確率で7色以下になります。 最後の色は塗れるものとしてよく、また、辺を特定していくパートでbfsのような順で特定していくと残りの頂点数に応じて二分探索の回数が減り、ならし7回になります。 ここまでで\(L = 255 \times 6 + 255 \times 6 + 255 \times (7 + 1) = 5100\) となります。 ここから場合分けをします。

• 7染色になった場合 条件を考えると、1色塗った段階で64頂点以上の未染色の連結成分、2色塗った段階で32頂点以上の未染色の連結成分…が必要となり、その条件を考えると1色目は64頂点以上、2色目は32頂点以上,,,存在することになります、なので最初の探索の回数が減り、\(64 \times 5 + 32 \times 4 + 16 \times 3 + 8 \times 2 + 4 \times 1 \geq 509\)となり、509回以上減ります

• 6染色以下になった場合 1回の判定で染色のパートと辺特定のパートで255回ずつ質問が減るので、509回以上質問が減ります。

よって全てのケースで\(L = 5100 - 509 = 4591\) を達成することができ、満点を得られます。

• おまけ 最初の乱択は多くの場合4染色以下に収まるのでそれを用いるとACを得るのは容易になってしまうかもしれませんが、0.2%程の確率で5染色になるグラフや0.03%程の確率で6染色になるようなグラフを構築できたので、満点制約はこのようにしました。それで満点を得られた方はおめでとうございます。