3匹の猫

みみねこの競プロ精進メモ

AtCoder Regular Contest 108参加記(~C問題)

300(1)-400-500-0-0-0で1ペナ3完1200点。

A - Sum and Product

N+M=Sを満たす正整数(N, M)の組はS-1個あり、これらの組全てに対してN\times M = Pかどうか判定すると、計算量O(S)で解ける。しかし今回は制約が1\le S, P\le 10^{12}と厳しいので、もっと効率の良い解法が必要となる。

N\times M = Pを満たす正整数(N, M)の組はPの約数の個数に等しい*1。また、問題文の条件がN, Mに対して対称なので、N\le Mを仮定すればN\times M = Pを満たす正整数Nの最大値は\sqrt{P}であることがわかる*2。よって、1\le N\le \sqrt{P}の範囲で(N, M)の組を全探索し、N+M=Sかを判定すると、計算量が改善されO(\sqrt{P})となり、実行時間制限に間に合う。

1\le N\le Pの範囲で(N, M)の組を全探索してしまい、TLEで1ペナ。

B - Abbreviate Fox

文字列中に部分文字列foxが存在していた場合、無条件に取り除いてよい(貪欲法)。これは、貪欲に取り除いてしまってもほかに取り除けるはずだった部分文字列foxの並びが崩壊することはない、ということからわかる。

実装時には注意が必要で、文字列を配列として扱うと一文字削除するごとにO(|S|)の計算量がかかってしまう。これを解決するためにスタックを用いて実装する。スタックに文字列の先頭から順に1文字ずつ挿入していき、末尾の3文字がfoxになった瞬間にその3文字ごと削除する。こうすれば、挿入・削除ともにO(1)で出来るため、全体の計算量がO(|S|)となる。

C - Keep Graph Connected

まず、YesNo判定問題と考えて、構築できないときそのグラフはどのような特徴を持つか考えてみる。完全グラフ、スターグラフ、二部グラフ、頂点数が極端に少ないグラフ、多重辺を含むグラフなど、さまざまなグラフで実験してみると、この問題の制約下で構築できないグラフは存在しないことが見えてくる。

よってここからは、グラフの各頂点に整数を振るアルゴリズムを考えていく。与えられるグラフは連結であることが保証されているため、BFSなどを用いることでN-1本の辺からなる部分木を取得できる。以下に整数の振り方の例を示す。

f:id:mmnkblog:20201121234649j:plain
構築例。*は親とつながっている辺のラベル以外なら何でもよい

木なので、どれか一つでも辺が欠けると非連結になってしまう。辺が残る条件は「辺の両端にある頂点に書かれた数字のうちどちらか一方のみが辺のラベルと一致する」である。これを言い換えると、辺が消える条件は「『頂点に書かれた2つの数字が両方とも辺のラベルと異なる』もしくは『頂点に書かれた2つの数字が両方とも辺のラベルと一致する』」となる。この条件を満たさないように回避するイメージで頂点に整数を振っていきたい。木の根(始点)に振る数はなんでもよい(理由は後述)ので、今回は1とする。根から葉にかけて整数を振っていく。

頂点に整数を振るアルゴリズムは以下のとおりである:

  • 親ノードに振られた整数をP、親ノードとつながっている辺のラベルをCとする。
  • P=Cなら、自ノードに振る整数をC以外の適当な数とする。
  • P\neq Cなら、自ノードに振る整数をCとする。

P=Cのときに適当な整数を振っても、考えているグラフは木なので、影響があるのは子ノードだけ。よって問題なく動作する。根に振る整数が何でもいい理由も、同様に説明できる。

実装するとき、BFSで木を探しながら同時進行で整数を振るようにした。計算量は、O(N+M)

D - AB

解けなかった。数え上げの問題なのでもう少し時間を掛ければ解けそう。

感想

レートが上がってうれしいです

*1:Pの約数の一つをAとすれば、N=A, M=P\div Aとして(N, M)の組を構築できるからである。P\div Aが割り切れることはAPの約数であることからわかる。

*2:Nが最大となるのはN=Mのときで、N\times N = PよりN = \sqrt{P}がわかる。