SRM 736 Div1

DigitRotation

問題

整数が文字列で与えられる。 この整数の3桁を選んでローテーション操作を行い生成される全ての整数の和をmod 998244353で求めよ。

メモ

n \leq 500なのでO(n^3)の全探索。

SRM 736 Div1 Easy · GitHub

MinDegreeSubgraph

問題

n,m,kが与えられる。 ALL, SOME, NONEのいずれか判別せよ。

  1. ALL : n頂点m辺の全ての単純グラフが最小次数kのサブグラフを持つ。
  2. SOME : n頂点m辺のいくつかの単純グラフが最小次数kのサブグラフを持つ。
  3. NONE : n頂点m辺の全ての単純グラフが最小次数kのサブグラフを持たない。

メモ

まず少なくとも一つの最小次数kのサブグラフを持つ条件を考える。 K_{k}を含むグラフは最小次数kのサブグラフを持つので頂点数がk+1以上、辺数が\frac{k(k+1)}{2}以上ならALL or SOME、そうでなければNONE。

残るはALLかSOMEの判別。 任意のサブグラフの最小次数がk未満となるようなグラフは、元のグラフに次数k未満の頂点が存在し、その頂点を取り除くとまた次数k未満の頂点が現れ、それを取り除くとまた現れ…これを繰り返し頂点数が0となるようなグラフ。 f(n,k)n頂点で最小次数k未満のとなる最大の辺数とすると、1頂点だけk-1の頂点があり、それを取り除くとまた1頂点だけk-1となるようなグラフが最大の辺数となるので

f(n,k)=f(n-1,k)+k-1

f(k+1,k)=\binom{k+1}{2}-1

SRM 736 Div1 Med · GitHub

参考

Subpolygon

問題

メモ