Codeforces Round #400 (Div. 1 + Div. 2, combined) ABCD
コンテストページのURLはこちらです。
Dashboard - ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) - Codeforces
A. A Serial Killer
問題概要
2つの文字列に対して、続く個の以下のクエリ:
「のうち、文字列である方を文字列で置き換える」
を処理するごとに、を出力する問題です。
ただし、、(各文字列長)です。
解法
ザ・やるだけ、な問題です。
問題に与えられた通り、実装していけば良いです。
ひとこと
これは特に引っかかるポイントはありませんね。
B. Sherlock and his girlfriend
問題概要
あるに対して、の数に次が成り立つよう色を塗ります。
「ある相異なる2つの数について、がの素因数になっている、つまりが素数かつがで割り切れるとき、との色が同じになってはいけない」
このとき、使う色の最小数とその色の塗り方を出力する問題です。
ただし、です。
なお、が最小であり塗り方が条件を満たしていれば、どのような出力でも構いません。
解法
まず条件から、明らかに合成数(素数ではない数)同士は同じ色で塗ってよいことがわかります。
ある2つの数を同じ色で塗ってはいけないとき、そのどちらかは必ず素数となるためです。
そして、同様に素数同士も同じ色で塗ってよいことが分かります。
ある2つの数を同じ色で塗ってはいけないとき、それら2数が両方素数だと、一方でもう一方は割ることが出来ないためです。
よって、素数と合成数をそれぞれ違う色で塗ればよいことが分かりました。
だからといっては常にであるかというと、そうではありません。
のとき、塗られる数はのみであり、
のとき、塗られる数はの2つとなります。
これらは、全て同じ色で塗っても良いため、となります。
なお、より大きい数では、ととが塗られる数に現れるため、となります。
(は素数であり、はで割り切れます)
コード(C++)
ひとこと
コンテスト中は、問題の示す通り各数に対して素因数であり同じ色であるものの色を変えていく、という実装にしていました
→コレ
しかし、このやり方でもそこまで計算量が大きくならなかったため、46ms程度で通りました。
あと、素因数ではなく因数でやってWAを貰っていた人が結構多かったみたいです。
(私も1WA頂きました)
C. Molly's Chemicals
解法
まずすぐに思いつくのは、全ての区間に対して和を求め、それがの非負整数乗となっているかを調べる方法です。
しかし、これでは区間の列挙に時間がかかってしまいます。
そこで、今回はあくまで条件を満たす区間の個数だけが分かればよいため、「累積和をmapでカウントする」という手法を取ります。
まず、の累積和を取ります。ここで、便宜上としておきます。
そして、このの値を、番号が大きい順にmapでカウントしつつ、差が(は非負整数)であるものの数を数えていきます。
この方法で、全ての条件を満たす区間を調べ上げることが出来ます。
実際に、具体例を見てみるとわかりやすいでしょう。
今、とします(これは問題でも与えられたサンプル2と同じものです)。
まず、累積和を取ると、となります。
次にこの累積和をmapでカウントしていきますが、これは横軸、縦軸の折れ線グラフを考えるとわかりやすいでしょう。
以下のスライドでこの具体例について述べているので、参照してください。
上記スライドでは、分かりやすいようにカウントしていない部分にを入れておきましたが、実際にを入れない方がいいです。
これは、mapへのアクセスに掛かる計算量が要素数の対数時間となっているためです。
アクセス時間が延びるのに何故mapを使うかについて簡単に説明します。
累積和の値は最小で、最大でほどになります。
これほど大きな区間を配列で管理することは出来ません。メモリ制限に引っかかってしまいます。
そこで、累積和の個数は個しか取らないため、これらを全てmapに入れたとしてもアクセスには時間しかかかりません。
また、(は非負整数)について、はいくらまで取ればよいかですが、
累積和は高々くらいの数をとります。
そのため、のとき、よりとなるため、くらいまで調べれば十分です。
今、の時については考えませんでしたが、このとき、を何乗してもその絶対値は変わりません。
具体的には、の時はのみ、の時はとのみの値しか取りません。
そのため、の時をコーナーケースとして別に処理してやると良いでしょう。
ひとこと
この問題はコンテスト中に解くことが出来ませんでした。
この「累積和をmapで管理する」というテクに名前等はついているんですかね?
D. The Door Problem
問題概要
ドアの数、スイッチの数、各ドアの初期状態鍵が開いている鍵が閉まっているの値を取る、
各スイッチに繋がれたドアの数、および各スイッチについて繋がれたドアの番号が与えられます。
あるスイッチをONにすると、そのスイッチに繋がれたドアの状態が全て逆になります(すなわち、開いているドアは閉まり、閉まっているドアは開きます)。
このとき、スイッチを適切に選択することで全ての鍵が同時に開いている状態にすることが出来るかを答える問題です。
ただし、
であり、ドアには丁度2つのスイッチが繋がっていることが保証されます。
解法
まず初めに、押すスイッチについての簡単な性質を挙げておきます。
- スイッチを押す順は関係ない
- 同じスイッチは2回以上押す必要はない
このことからすぐに思いつく解法としては、全てのスイッチを押す/押さないで全探索するものがあります。
しかし、これでは計算量がとなり、とても間に合いません。
ここで、制約にある「ドアには丁度2つのスイッチが繋がっている」というものに注目すると、次のことが成り立ちます。
- 閉じているドアに対して繋がっている2つのスイッチは、どちらか1つだけ押す必要がある
- 開いているドアに対して繋がっている2つのスイッチは、両方押すか、両方押さないかのどちらかである必要がある
このことから、「あるスイッチの状態を決めると、そのスイッチが繋がるドアを介して別のスイッチの状態が決まる」ということが分かります。
この手の問題は、充足可能性問題(satisfiability problem, SAT)と呼ばれ、一般にはNP完全です。
しかし、この問題のように「状態を決めるものが(高々)2個しかない」という場合、2-SATと呼ばれ、関係式全体の大きさの線形時間で解くことが出来ます。
さらにこの問題では、2-SATの特殊な場合としてより簡単に考えることが出来ます。
詳しくは、以下のスライドを参照してください。
(一般の2-SATとの違いは最後の方にあります)
コード(C++)
ひとこと
2-SATについては、この問題に出会う数日前にF: Flags - AtCoder Regular Contest 069 | AtCoderを見て初めて知りましたが、コンテスト中に解くことが出来ました。
AtCoder様様ですね。
最後に
以上でABCD問題の解説を終わります。
EFG問題は別の記事に分けましたので、そちらを参照してください。
(まだ書き上げていないので少々お待ちください…)