AtCoder Regular Contest 184 A,B,C問題メモ

AtCoder Regular Contest 184

A - Appraiser

• この問題は インタラクティブ な問題であり、ジャッジは適応的(adaptive)です。
  • 適応的: ジャッジは、これまでの回答に矛盾しない範囲で自由に答えを変更できる。
  • （＝一意に確定していないまま解答するとWAの可能性がある）
  • 問題文中のパラメータは $N=1000,M=10,Q=950$ で固定されています。
• 硬貨が $N$ 枚あり、 $1,2,\dots,N$ の番号が付けられています。これらの硬貨のうち、丁度 $M$ 枚が偽物です。
• 鑑定士は $1$ 度の鑑定で $2$ つの硬貨が同種か異種かを判定できます。厳密には、
  • $2$ つの硬貨が「双方とも本物」「双方とも偽物」のどちらかであれば、同種と判定する。
  • そうでないとき、異種と判定する。
• $Q$ 回以下の鑑定で、全ての偽物の硬貨を特定してください。

• $N = 1000$
• $M = 10$
• $Q = 950$

論理パズルでありそうな問題。

偽物は10個しか無いので、11個以上の同種があったら必ず本物。

例えば「硬貨1と、2～1000をそれぞれ比較する」と、同種となる10個がわかる。ただし999回かかるのでWA。

これは、グループ分けすることで回数が多少節約できて、20個ずつの50グループに分けると、

• グループ1: 硬貨1と、2～20を比較する。
• グループ2: 硬貨21と、22～40を比較する。
• …

として、各グループにおいて少数派の方が偽物とわかる。
1グループ19回の判定で、50グループ950回に収まる。

ただし問題は、「1グループの中に偽物が全て存在し、10 vs 10 になってしまう」ことがある。
この場合のみ、少数派がどちらか分からず、グループに対して追加の調査が必要になる。
仮に21個ずつのグループに分けるとこういう問題は発生しなくなるが、最悪回数が950回を超えてしまう。

場合分けする。

• グループ1～49の中で、10vs10グループが見つかったとき
  • 少なくとも操作回数はグループ50の19回分が残っている。
  • 10vs10グループ以外の硬貨は全て本物。1枚持ってきて、10vs10グループの1枚($x$)と比較する。
  • 同種なら、$x$ と同種のものが本物。異種なら、$x$ と違う方が本物。
• グループ1～49が、全て本物だったとき
  • グループ50は、判定するまでもなく10vs10グループ確定。操作回数は19回残っている。
  • グループ50以外から本物と確定した硬貨を1枚持ってきて、グループ50の19枚と比較する
  • 異種と判定されたのが偽物。
  • 偽物が9枚しか見つからなければ、判定してない20枚目も偽物。

これで、950回以内に判定できる。

Python3

（ACの上では不要だが）より回数が少なく済む方法。

• 解説 - AtCoder Regular Contest 184 の (1)

「解答が一意に決まった」ことを判定するにはどうすればよいかを考えると、以下の方法が思いつく。

• 硬貨を頂点、問われた2硬貨間の情報を（同種異種問わず）辺として扱う。
  • 連結になった任意の2硬貨の同種・異種は特定できる。
  • 同種同士を同じグループとして、2つのグループに分けられる。
  • $i$ 番目の連結成分の2グループの頂点数をそれぞれ $X_i,Y_i$ とする。
• 以下のDPをおこなう
  • $\mathrm{DP}[i,k]:=i$ 番目の連結成分まで「$X_i,Y_i$ のいずれか一方を選び合計する」ことをした時の、総和が $k$ となる方法の個数
  • 全ての連結成分について処理後、$k=10$ にする方法が1通りか判定する。

「10にする方法が1通り」なら、答えは一意に決まっている。
（ジャッジが矛盾する答えを返すことはしないので、0通りとなることは考えなくてよく、2通り以上となるのがダメ）
この条件を満たせる中で、なるべく辺数＝クエリ数を減らしたい。

まず、既に同じ連結成分に属する頂点を改めてクエリで調べる必要は無く、各連結成分は木であるとしてよい。
すると、グラフが森の時、「辺数=頂点数-連結成分数」で求められるので、連結成分の個数は多い方がよい。

ここで、例えばある $i$ で $X_i \ge 11$ だと、選べるのは $Y_i$ に一意に決まる。
全ての $i$ で片方のグループが11個以上となるように森を構成すると、 全ての選び方が一意に決まるので「10にする方法が1通り」を満たす。

本物は990枚あるので、1つの木にちょうど11個の本物が属するようにすると、木は90個できる。
この時の辺数を考えると、910本となる。よって、910回の質問で答えを確定できる。

具体的な構築方法は冒頭の解説記事参照。

もしかしたら「$X_i,Y_i$ のいずれも $11$ 未満となる連結成分があっても、 現在の状況から10にする方法は1通りに決まる」ような状況を判定し 回数を更に突き詰めることはできるかもしれないが、複雑な条件分岐が必要になりそう。

B - 123 Set

• 正整数 $N$ が与えられます。空集合 $S$ があり、あなたは以下の操作を何回でも行うことができます。
  • 正整数 $x$ を自由に選ぶ。$x, 2x, 3x$ それぞれについて、もし $S$ に含まれなければ追加する。
• $\{1, 2, \dots ,N\} \subseteq S$ を満たすまでに必要な操作回数の最小値を求めてください。

• $1 \leq N \leq 10^{9}$
• 実行制限時間: 8秒

少しずるい埋め込み解法。

追加する数がダブってしまうことを、なるべく減らしたい。

ダブる心配があるのは、$x=2^a3^by$ のように2と3のみについて素因数分解をした結果、残る $y$ を同じくする数同士のみとなる。
また、そのような数たちを $y$ で割ってやると、その構造はどれも同じである。

■ 2^a * 3^b * y と表せる数
y
1:  1,  2,  3,  4,  6,  8,  9, 12, ... を効率よく追加する方法
5:  5, 10, 15, 20, 30, 40, 45, 60, ... を効率よく追加する方法
7:  7, 14, 21, 28, 42, 56, 63, 84, ... を効率よく追加する方法

「何番目に小さい数まで追加すればよいか（何番目でNを超えるか）」は
y ごとに異なるものの、仮にそれが同じなら、必要な操作回数も同じ！
↓
前計算できそう。

以下の関数を定義する。

• $F(M):=M$ 以下の全ての「$2^a3^b$ と表せる数」を $S$ に追加するのに必要な操作回数

これが仮に求まっているとすると、たとえば $N=25$ のとき、

• $y=1$ のとき、$F(25)$
• $y=5$ のとき、$x=2^a3^b5$ が $N$ を超えない、つまり $F(N/y)=F(5)$ までを追加すれば良い
• $y=7$ のとき、$F(25/7)=F(3)$
• $y=11$ のとき、$F(25/11)=F(2)$
• …

というのを、$y \le N$ まで続けていけば、その総和が答えとなる。

$y$ の取り得る値は「2の倍数でも3の倍数でもない数」、 要は「6で割って1または5余る数」なので数が多く、1つ1つ求めていてはTLEだが、 $y \ge \sqrt{N}$ あたりを境目に $N/y$ の値が同じものが増えるので、 それらをまとめれば、考慮するのは $2\sqrt{N}$ 個程度の区間で済む。

$y$ として取り得る値が任意の $[l,r)$ 区間の中にいくつあるかはすぐに計算できる。

で、残る問題は、$F(M)$ をどうやって求めるかとなる。

$M \le 10^9$ の範囲で $2^a3^b$ と表せる数は300個程度なので、 事前に時間をかけてでもそれぞれの解を求めてしまえば、コードに埋め込むことは十分可能。

問題を少し言い換えると、以下のような、↓に進むと2倍、→に進むと3倍になる表において、

 1  3  9  27  81    M=108 として、108以下の値のみからなる表。
 2  6 18  54
 4 12 36 108        ■■ というスタンプを何個押せば、
 8 24 72            ■
16 48               全てのマスにスタンプを押した状態にできますか？
32 96               というのが、F(108) に相当する。
64

段を下がる毎に1列減ったり減らなかったり形が不規則なので、貪欲法だと埋め方が見えづらい。

DPをする。

• $\mathrm{DP}[i,S]=i$ 行目より下は全て埋め、$i$ 行目で既に押された列の集合が $S$ である場合の、最小操作回数
  • $i$ が大きい方から埋めていく

スタンプの形状を考えると、下から考えた方が「押してない箇所を埋めるにはどこに押せばよいか」が一意に確定するので 考えやすいかなと思ってこのようなDPにしたが、まぁ、上から（$i$ が小さい方から）でも別にいいと思う。

シンプルに、遷移で「次にどこに置くか」を全探索する実装をすると、 状態数が $\log_2{M} \times 2^{\log_3{M}}$、遷移が $2^{\log_3{M}}$ なので、なかなか重い。
まぁ、$i$ が大きいうちは2の指数も小さく、定数倍で何分の一かになる。
また、必ず置かなければならない場所には置くなど適当に枝刈りしつつ実装すると、数分で全て計算できた。

ただ、この解法では、埋め込まずに制限時間内に計算するとなると （$N$ に対して必要な $F(M)$ のみ求めれば良いとしても）8秒だと厳しいか。

Python3

必要な $F(M)$ は少ない。

• $Q(N):=$ 正整数 $k$ によって $N/k$（切り捨て）と表されうる数のリスト

とすると、$M$ として調査すべきは $Q(N)$ に登場する数のみでよい。
また、直近で自身より小さい $2^a3^b$ と表される数が同じ同士はキャッシュしておけば繰り返し計算する必要は無い。
（たとえば、$M=12,13,14,15$ などはいずれも $F(M)$ が等しいので、$F(12)$ のみ求めればよい）

こうすると、実際に計算するべき $F(M)$ の個数はある程度減らせる。
（とはいえ、最大の $N=10^9$ で実行すると $241$ 回は計算しなければならないようなので、最悪計算量が激減するわけではないが）

こちらが本質。

DPの意味を少しだけ変える。

• $\mathrm{DP}[i,S]=i$ 行目より下は全て埋め、$i$ 行目で「少なくとも」既に押された列の集合が $S$ である場合の、最小操作回数

S1 = ***.**..* のとき DP[i,S1] = 3 なら、（*=押した、.=押してない）

S1の部分集合である以下のようなSに対するDP[i,S]も、3で最小値を更新できるとする。

     ***..*..*
     *.*.**..*
     .........

「次の行に遷移するときに、本当は押したけど押してないことにする列をいくつか作り、次の行でもまた押すようなケースを考慮するよ」ということなので、こうしても答えは正しく求まる。

そして、こうすると高速ゼータ変換が使えて計算量を減らせる。

$\mathrm{DP}[i+1,S_1]$ から $\mathrm{DP}[i,*]$ への遷移を考える。
ひとまず必要最小限の箇所だけに押した箇所を更新し、、、

S1 = ***.**..*
                   **  スタンプの[*]の位置を
        ^  ^^     [*]  「^」にあわせて押せば、
                       1つ上のi行目で押された箇所S2は
S2 = ...**.***         左のようになり、
                       DP[i,S2] ←chmin-- DP[i+1,S1]+3 で更新できる。

同じ遷移を $S_2$ の全ての部分集合に対しても行いたいのだが、 それは全ての $S$ について $\mathrm{DP}[i+1,S]$ からの更新後、 最後に高速ゼータ変換で畳み込むことでおこなえる。

こうすることで、1行あたり $O(\log_3{M} 2^{\log_3{M}})$ の計算量で済むようになり、実行中に求めても間に合うようになる。

Python3

C - Mountain and Valley Folds

• 厚さを無視できる細長い紙があります。
• 右端を持ち上げ、中央を折り目にして左端に合わせて折りたたむ操作を $100$ 回行い、もとに戻します。
• このとき紙には折り目が $2^{100} - 1$ 個あり、これらは山折り、谷折りの $2$ 種類に分類できます。

• 長さ $N$ の非負整数列 $A = (A_1, A_2, \dots ,A_N)$ が与えられます。
• $1$ 以上 $2^{100} - A_N - 1$ 以下の整数 $i$ に対し、 $f(i)$ を以下のように定義します。
  • $k = 1, 2, \dots ,N$ のうち、左から $i + A_k$ 番目の折り目が山折りであるものの個数
• $f(1), f(2), \dots ,f(2^{100} - A_N - 1)$ の最大値を求めてください。

• $1 \leq N \leq 10^3$
• $0 = A_1 \lt A_2 \lt \dots \lt A_N \leq 10^{18}$

問題文では厚さを無視できるとしているが、 仮に紙に0.1mmの厚さがあったら、100回折るとその厚みは約134億光年になる。Omoinotakeかよ。

どんなスピードで追いかけたら どんな法則で折り目が付いていくのか考える。

最初に中央で折ると、「左は表が上」「右は裏が上」という状態になる。

0:谷折り, 1:山折り, F:表が上, B:裏が上
        F               B
|---------------0---------------|

この状態で2回目を折ると、「表が上になっている区間は谷折り」「裏が上になっている区間は山折り」になる。
また、「隣り合う区間は裏表が異なる」ので、紙の裏表は“FBFB”と交互になる。
（表が上の区間を1回折り曲げた隣の区間は、谷折りでも山折りでも、間に他の紙が挟まっていても、絶対裏が上）

    F       B       F       B
|-------0-------0-------1-------|

これは再帰的に続く。

  F   B   F   B   F   B   F   B
|---0---0---1---0---0---1---1---|

つまり、「$k$ 回目に折ったときについた折り目」は、$k$ が同じもの同士で左から「0101…」となる。

k
1  |---------------0---------------|
2  |-------0---------------1-------|
3  |---0-------1-------0-------1---|
4  |-0---1---0---1---0---1---0---1-|
5  |0-1-0-1-0-1-0-1-0-1-0-1-0-1-0-1|
:

この法則で作られる01数列に対して、上手くオフセット $t$ を決めて、 なるべく多くの $A_i+t$ の位置に“1”が来るようにすればよい。

ところで上記のように階層別に分けた表はフラクタル構造をしていて、 上記は一番上の5階層を示したものだが、同じ構造は最下層にも現れる。

後続の説明のため、$k$ を最下段から $0,1,2,...$ と振りなおす。

:
4  |---------------0---------------|---------------1---------------|---------------0--...
3  |-------0---------------1-------|-------0---------------1-------|-------0----------...
2  |---0-------1-------0-------1---|---0-------1-------0-------1---|---0-------1------...
1  |-0---1---0---1---0---1---0---1-|-0---1---0---1---0---1---0---1-|-0---1---0---1---0...
0  |0-1-0-1-0-1-0-1-0-1-0-1-0-1-0-1|0-1-0-1-0-1-0-1-0-1-0-1-0-1-0-1|0-1-0-1-0-1-0-1-0-...

ここで、“1”が現れる座標というのは、以下のようになっている。

• 0階層目は、2で0回割った値が奇数である座標の折り目が決まり、うちその値を4で割って3余る箇所に“1”が来る
• 1階層目は、2で1回割った値が奇数である座標の折り目が決まり、うちその値を4で割って3余る箇所に“1”が来る
• 2階層目は、2で2回割った値が奇数である座標の折り目が決まり、うちその値を4で割って3余る箇所に“1”が来る
• …
• $k$ 階層目は、2で $k$ 回割った値が奇数である座標の折り目が決まり、うちその値を4で割って3余る箇所に“1”が来る

なので、オフセット $t$ の2進数での下の桁から、“0”,“1”を置いた場合をそれぞれ試していく再帰的な解法がとれそう。

• ※ざっくり解法（不正確）
• $k$ 階層目では、$t$ の2進数で下 $k$ 桁目の “0”,“1” を仮定する。
• その階層で折り目がつく $A_i$ が決まる。（オフセット含みの値が奇数となるもの）
  • うち山折りになる数を数える。
• その階層で折り目が付かない $A_i$（偶数となるもの）は、それらだけ抽出して2で割ったものを新たな $A$ として、$k+1$ 階層目に引き継ぐ
  • すると、$k$ 階層目と全く同じ構造で、$k+1$ 階層目も再帰的に処理できる。
• $k$ 桁目を “0”,“1” にした場合の (その階層での山折りの個数 + 引き継いだ結果の最適解) をそれぞれ求め、大きい方を採用する。

これは、階層ごとに2通りに分割していくので一見、計算量がかかりそうだが、 1つの $A_i$ に対して考えれば引き継がれる回数は $O(\log{A_i})$ 回なので、 全体で $O(N \log{A_{\max}})$ で動作する。

ただ、大枠はよいが、上記のままだと上手くいかない。
山折りになるかどうかが「mod 4」で決まるので、「$k$ 階層目で山折りになる個数」を仮定するには、 「$t$ の $(k,k+1)$ 桁目の2つの桁を仮定しなければならない」から。

最初の $k=0$ 階層目はよいが、$k=1$ 以降は「1つ下の階層で既に $k$ 桁目は決められていて、$k+1$ 桁目しか自由には決められない」ことになる。

つまり、$k=1$ 以降で追加分のオフセットとして試すのは $0,2$ の2通りになる。
この時点で引き継がれて残っている $A_i$ が奇数のものにこの階層で折り目が付くことは既に決定していて、 「4で割って1余る」「3余る」のいずれの方に“1”を合わせにいくかの2通りを選ぶことになる。

数列を引数に取る $f(B)$ を以下で定義する。

• $|B|=0$ の場合、0を返す。
• $|B|=1$ の場合、その1個を任意に調整して“1”にあわせることができるので、1を返す。
• それ以外の場合、
  • $M_s$ を「$B_i$ のうち、$B_i+s$ を4で割って3余るもののの個数」とする。
  • $C_s = \left( \frac{b_i+s}{2} \mid b_i \in B, b_i \text{ is even} \right)$ とする。
  • $\max(M_0 + f(C_0), M_2 + f(C_2))$ を返す。

$f(A)$、$f(Aの各要素を+1したもの)$ の大きい方が答えとなる。

Python3