AtCoder Regular Contest 108参加記(~C問題)
300(1)-400-500-0-0-0で1ペナ3完1200点。
A - Sum and Product
を満たす正整数の組は個あり、これらの組全てに対してかどうか判定すると、計算量で解ける。しかし今回は制約がと厳しいので、もっと効率の良い解法が必要となる。
を満たす正整数の組はの約数の個数に等しい*1。また、問題文の条件がに対して対称なので、を仮定すればを満たす正整数の最大値はであることがわかる*2。よって、の範囲での組を全探索し、かを判定すると、計算量が改善されとなり、実行時間制限に間に合う。
の範囲での組を全探索してしまい、TLEで1ペナ。
B - Abbreviate Fox
文字列中に部分文字列fox
が存在していた場合、無条件に取り除いてよい(貪欲法)。これは、貪欲に取り除いてしまってもほかに取り除けるはずだった部分文字列fox
の並びが崩壊することはない、ということからわかる。
実装時には注意が必要で、文字列を配列として扱うと一文字削除するごとにの計算量がかかってしまう。これを解決するためにスタックを用いて実装する。スタックに文字列の先頭から順に1文字ずつ挿入していき、末尾の3文字がfox
になった瞬間にその3文字ごと削除する。こうすれば、挿入・削除ともにで出来るため、全体の計算量がとなる。
C - Keep Graph Connected
まず、YesNo判定問題と考えて、構築できないときそのグラフはどのような特徴を持つか考えてみる。完全グラフ、スターグラフ、二部グラフ、頂点数が極端に少ないグラフ、多重辺を含むグラフなど、さまざまなグラフで実験してみると、この問題の制約下で構築できないグラフは存在しないことが見えてくる。
よってここからは、グラフの各頂点に整数を振るアルゴリズムを考えていく。与えられるグラフは連結であることが保証されているため、BFSなどを用いることで本の辺からなる部分木を取得できる。以下に整数の振り方の例を示す。
木なので、どれか一つでも辺が欠けると非連結になってしまう。辺が残る条件は「辺の両端にある頂点に書かれた数字のうちどちらか一方のみが辺のラベルと一致する」である。これを言い換えると、辺が消える条件は「『頂点に書かれた2つの数字が両方とも辺のラベルと異なる』もしくは『頂点に書かれた2つの数字が両方とも辺のラベルと一致する』」となる。この条件を満たさないように回避するイメージで頂点に整数を振っていきたい。木の根(始点)に振る数はなんでもよい(理由は後述)ので、今回はとする。根から葉にかけて整数を振っていく。
頂点に整数を振るアルゴリズムは以下のとおりである:
- 親ノードに振られた整数を、親ノードとつながっている辺のラベルをとする。
- なら、自ノードに振る整数を以外の適当な数とする。
- なら、自ノードに振る整数をとする。
のときに適当な整数を振っても、考えているグラフは木なので、影響があるのは子ノードだけ。よって問題なく動作する。根に振る整数が何でもいい理由も、同様に説明できる。
実装するとき、BFSで木を探しながら同時進行で整数を振るようにした。計算量は、。
D - AB
解けなかった。数え上げの問題なのでもう少し時間を掛ければ解けそう。
感想
レートが上がってうれしいです