AtCoderの競技プログラミングの大会に参加したので、C/D 問題のみ思考過程込みで解説をしていきます。

AtCoder Regular Contest #102

問題一覧：

C - Triangular Relationship

問題概要：整数 N, K が与えられる。a, b, c を N 以下の正の整数とする。 a + b, b + c, c + a がすべて K の倍数であるような (a, b, c) の組み合わせを数えよ。

a ≤ N という条件があるので剰余の世界では完結しませんが、とりあえず剰余で計算してみます。x が K の倍数であるとは x≡0 (mod K) なので、条件の後半は a + b ≡ 0, b + c ≡ 0, c + a ≡ 0 という連立方程式になります。

とりあえず変数が多い上に対称的なので、a (≤10^6) を全列挙すると仮定します。(1つの変数を全列挙するというのは問題を考えやすくする常套手段です。最終的には全列挙しませんが。)

a は定数として扱えます。式変形すると b ≡ -a, c ≡ -a, b + c ≡ 0 ≡ -2a です。2a ≡ 0 (mod K) から、K が奇数なら a ≡ 0 でなければならないことが分かります。

ここで K が偶数か奇数かで場合分けしました。(おそらく模範的な解法には不要な場合分けをしているという予感はありましたが、模範解に一発で到達できない以上は必要経費です。最悪、似たようなコードを2回書くだけですし。最終的には消せました。)

いま K は奇数です。2a ≡ 0 だから a は K の倍数です。b ≡ -a ≡ 0, c ≡ -a ≡ 0 だから a, b, c はすべて K の倍数に限られます。逆に、a, b, c が K の倍数なら条件を満たします。だから 1 以上 N 以下の K の倍数の個数を数えて (ただの割り算)、3乗すればOK。a についてループする必要はなかったっぽい。

以降、K は偶数です。

2a ≡ 0 だから a ≡ 0 または a ≡ K/2 ですが、a ≡ 0 のケースは上と同じなので、a ≡ K/2 を考えます。b ≡ -a ≡ -K/2 ≡ K/2 であり、c も同様に c ≡ K/2 と分かります。逆に a, b, c がすべて K/2 (mod K) なら条件を満たします。これも1以上N以下の整数で K/2 (mod K) であるものの個数を3乗すればOK。解けました。大変だった。

提出：

D - All Your Paths are Different Lengths

問題概要 (長い)：整数 L が与えられる。以下の条件を満たす重みつき DAG (閉路のない有向グラフ) が少なくとも1つ存在するので、いずれかを求めよ。

1. 頂点数 N は 20 以下
2. 辺数 M は 60 以下
3. 点 1 から N へのパスがちょうど L 個存在し、重みの総和が 0, 1, ..., L-1 である

なるべく簡略化しましたが、やはり分かりづらいので問題文とサンプルを見てください。頂点の番号づけに細かい条件 (u→v なら u < v) がありますが、出力時に適当な書き換えをすればいいので考察中は無視します。

入力例1の方法は一般化できそうですが、頂点数が O(L) 個必要なのでダメです。頂点数 20 で重みを L (≤ 10^6) 程度にするには非常に重い辺が必要で、なおかつ重みの総和にギャップが生じないようにする必要があります。たぶん2進法ですね💡

例えば L=8 とします。点 1 → 2 → 3 に2本ずつ辺を張って、片方の重みを 0 、他方をそれぞれ 4,2,1 とすれば重みが 0~7 である8個のパスが存在することになります。L=2^p なら同様に可能。あとはそうでない場合。

     →_0       →_0       →_0
[1]       [2]       [3]       [4]
     →_4       →_2       →_1

例えば L=10 とします。 2^3 < 10 < 2^4 だから p=3 として、上述のように3つの点を配置すれば重み 8 未満のパスが作れます。

あとは重み 8~9 の2つのパスがほしい。

点1からNへのパスに重みが重複するものは許されないので注意。これらのパスは、必ず重み 8 以上の辺を通るようにしましょう。逆に重み 8 以上の辺を1度通った後に通るのは重み 0~1 のパス。これは上記と同様に作れるのでは？ というか点 [3] に遷移すればいいのでは？

     ->_0      ->_0      ->_0
[1]       [2]       [3]       [4]
     ->_4      ->_2      ->_1

  \------------------^_8

できた！

L=11 や L=12 ではさらに辺の追加が必要ですが、同じ方法が再帰的に使えます。一般的にみて、重み S ~ (S+2^q) へのパスを生み出すには、点 1 から重み S の辺を張ればいい。だから次の手順で再帰的に解けます。

1. S = 2^p とする
2. S + 2^q <= L となる最大の q を探して辺を張る
3. S = S + 2^q で更新して S = L になるまで繰り返す (重みS未満のパスがすべて存在するというループ不変条件が成立しています)

ここまで本番中に到達できたんですが、点1から1へのループ辺が生成されてしまうケースがあったせいでWAが出て、アルゴリズムを見直しているうちに終了しました。実際のところ q <= p に制限すればいいだけです。

また、10^6 は約19ビットなので頂点数の上限をぎりぎり超えてしまいます。2進法ではダメ。基数を大きくすれば頂点数を減らせますが、代わりに辺数が増えるので、頑張って計算して制約を満たす基数を探しましょう？　というのが模範的な思考ですが、問題文をよく見るとヒントがあって、頂点数：辺数 = 1:3 だから3進数だといけそう。

提出 (コンテスト終了後)：

まとめ

C完でした。D問題が自力ACだったので上々。レートは減少。