読者です 読者をやめる 読者になる 読者になる

sataniC++

C++、競プロ、数学などについて色々考えたりします。

Codeforces Round #400 (Div. 1 + Div. 2, combined) ABCD

競プロ参加 競プロ参加-Codeforces

コンテストページのURLはこちらです。
Dashboard - ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) - Codeforces

A. A Serial Killer

Problem - A - Codeforces

問題概要

2つの文字列S_1,S_2に対して、続くn個の以下のクエリ:
S_1,S_2のうち、文字列sである方を文字列tで置き換える」
を処理するごとに、S_1,S_2を出力する問題です。
ただし、1\leq n \leq 10^3、(各文字列長)\leq 10です。

解法

ザ・やるだけ、な問題です。
問題に与えられた通り、実装していけば良いです。

コード(C++)

ひとこと

これは特に引っかかるポイントはありませんね。


B. Sherlock and his girlfriend

Problem - B - Codeforces

問題概要

あるnに対して、2,3,\cdots ,n+1の数に次が成り立つよう色を塗ります。
「ある相異なる2つの数p,qについて、pqの素因数になっている、つまりp素数かつqpで割り切れるとき、pqの色が同じになってはいけない」

このとき、使う色の最小数kとその色の塗り方を出力する問題です。
ただし、1\leq n \leq 10^5です。
なお、kが最小であり塗り方が条件を満たしていれば、どのような出力でも構いません。

解法

まず条件から、明らかに合成数(素数ではない数)同士は同じ色で塗ってよいことがわかります。
ある2つの数を同じ色で塗ってはいけないとき、そのどちらかは必ず素数となるためです。

そして、同様に素数同士も同じ色で塗ってよいことが分かります。
ある2つの数を同じ色で塗ってはいけないとき、それら2数が両方素数だと、一方でもう一方は割ることが出来ないためです。


よって、素数合成数をそれぞれ違う色で塗ればよいことが分かりました。


だからといってkは常に2であるかというと、そうではありません。
n=1のとき、塗られる数は\mathtt{2}のみであり、
n=2のとき、塗られる数は\mathtt{2,3}の2つとなります。

これらは、全て同じ色で塗っても良いため、k=1となります。


なお、n=3より大きい数では、\mathtt{2}\mathtt{4}とが塗られる数に現れるため、k=2となります。
\mathtt{2}素数であり、\mathtt{4}\mathtt{2}で割り切れます)

コード(C++)

ひとこと

コンテスト中は、問題の示す通り各数に対して素因数であり同じ色であるものの色を変えていく、という実装にしていました
コレ

しかし、このやり方でもそこまで計算量が大きくならなかったため、46ms程度で通りました。


あと、素因数ではなく因数でやってWAを貰っていた人が結構多かったみたいです。
(私も1WA頂きました)


C. Molly's Chemicals

Problem - C - Codeforces

問題概要

整数n,kと、数列a_1, a_2, \cdots, a_nが与えられます。
このとき、区間[a_l, a_r](l\leq r)に含まれる項の和がkの非負整数乗となるような区間が何通りあるか、を答える問題です。
ただし、1\leq n\leq 10^5, 1\leq |k|\leq 10, -10^9\leq a_i\leq 10^9です。

kの非負整数乗とは、k^0, k^1, k^2, \cdotsを指します)

解法

まずすぐに思いつくのは、全ての区間[a_l, a_r](l\leq r)に対して和を求め、それがkの非負整数乗となっているかを調べる方法です。

しかし、これでは区間の列挙にO(n^2)時間がかかってしまいます。


そこで、今回はあくまで条件を満たす区間の個数だけが分かればよいため、「累積和をmapでカウントする」という手法を取ります。

まず、a_iの累積和s_iを取ります。ここで、便宜上s_0 = 0としておきます。
\displaystyle s_i = \sum^i_{j=1}a_j

そして、このs_iの値を、番号が大きい順にmapでカウントしつつ、差がk^p(pは非負整数)であるものの数を数えていきます。


この方法で、全ての条件を満たす区間を調べ上げることが出来ます。



実際に、具体例を見てみるとわかりやすいでしょう。

今、n=4, k=-3, a=\{3, -6, -3, 12\}とします(これは問題でも与えられたサンプル2と同じものです)。

まず、累積和を取ると、s=\{0,3,-3,-6,6\}となります。

次にこの累積和をmapでカウントしていきますが、これは横軸i、縦軸s_iの折れ線グラフを考えるとわかりやすいでしょう。
以下のスライドでこの具体例について述べているので、参照してください。

上記スライドでは、分かりやすいようにカウントしていない部分に0を入れておきましたが、実際に0を入れない方がいいです。
これは、mapへのアクセスに掛かる計算量が要素数の対数時間となっているためです。


アクセス時間が延びるのに何故mapを使うかについて簡単に説明します。
累積和の値は最小で10^{-14}、最大で10^{14}ほどになります。
これほど大きな区間を配列で管理することは出来ません。メモリ制限に引っかかってしまいます。

そこで、累積和の個数はn+1個しか取らないため、これらを全てmapに入れたとしてもアクセスにはO(\log n)時間しかかかりません。



また、k^p(pは非負整数)について、pはいくらまで取ればよいかですが、
累積和s_iは高々10^{14}くらいの数をとります。
そのため、|k|>1のとき、2^p < 10^{14}よりp<46.5\cdotsとなるため、p=50くらいまで調べれば十分です。

今、|k|=1の時については考えませんでしたが、このとき、kを何乗してもその絶対値は変わりません。
具体的には、k=1の時は1のみ、k=-1の時は-11のみの値しか取りません。


そのため、|k|=1の時をコーナーケースとして別に処理してやると良いでしょう。

コード(C++)

ひとこと

この問題はコンテスト中に解くことが出来ませんでした。
この「累積和をmapで管理する」というテクに名前等はついているんですかね?

D. The Door Problem

Problem - D - Codeforces

問題概要

ドアの数n、スイッチの数m、各ドアの初期状態\{r_1, r_2, \cdots, r_n\}(0:鍵が開いている,1:鍵が閉まっている,2値を取る)
各スイッチに繋がれたドアの数\{x_1, x_2, \cdots, x_m\}、および各スイッチについて繋がれたドアの番号\{d_0, d_1, \cdots, d_{x_i-1}\}が与えられます。

あるスイッチをONにすると、そのスイッチに繋がれたドアの状態が全て逆になります(すなわち、開いているドアは閉まり、閉まっているドアは開きます)。
このとき、スイッチを適切に選択することで全ての鍵が同時に開いている状態にすることが出来るかを答える問題です。

ただし、
2\leq n\leq 10^5, 2\leq m\leq 10^5, 0\leq r_i\leq 1, 0\leq x_i \leq n, 1 \leq d_i \leq n
であり、ドアには丁度2つのスイッチが繋がっていることが保証されます。

解法

まず初めに、押すスイッチについての簡単な性質を挙げておきます。

  • スイッチを押す順は関係ない
  • 同じスイッチは2回以上押す必要はない

このことからすぐに思いつく解法としては、全てのスイッチを押す/押さないで全探索するものがあります。
しかし、これでは計算量がO(2^m)となり、とても間に合いません。



ここで、制約にある「ドアには丁度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問題は別の記事に分けましたので、そちらを参照してください。
(まだ書き上げていないので少々お待ちください…)