2018-10-13

Educational Codeforces Round 52 参加記録＆解説（A～F）

Codeforces プログラミング競技プログラミング

Dashboard - Educational Codeforces Round 52 (Rated for Div. 2) - Codeforces

結果は4完で194位。DがHackで落ちました…

f:id:betrue12:20181012201409p:plain

A～Fの6問を振り返ります。

A. Vasya and Chocolate

Problem - A - Codeforces

問題概要

以下の問題 $t$ 個に答えよ。

所持金 $s$ ルーブルで、1つ $c$ ルーブルのチョコを買えるだけ買う。また、チョコを $a$ 個買うごとに追加で $b$ 個のチョコがもらえる。入手できるチョコの総数を求めよ。

制約

$1 \le t \le 100$
$1 \le s, a, b, c \le 10^{9}$

解法

買えるチョコは $n_{1} = \lfloor\frac{s}{c}\rfloor$ 個です。これを $a$ 個1組とすると $\lfloor\frac{n_{1}}{a}\rfloor$ 組買っているので、追加でもらえるチョコは $n_{2} = \lfloor\frac{n_{1}}{a}\rfloor \times b$ 個です。 $n_{1} + n_{2}$ が答えです。

ACコード

（C++）Submission #44119682 - Codeforces

B. Vasya and Isolated Vertices

Problem - B - Codeforces

問題概要

$n$ 頂点 $m$ 辺の単純な無向グラフの中で、孤立点が最も少ないグラフと、最も多いグラフを考える。それぞれの孤立点の数を求めよ。

制約

$1 \le n \le 10^{5}$
$0 \le m \le \frac{n(n-1)}{2}$

解法

孤立点を最も少なくするには、孤立点同士を辺で結んでいくのがよいです。1本の辺につき孤立点が2個減るので、孤立点の最小数は $\max(0, n-2m)$ となります。

孤立点を多くするには、なるべく少ない頂点だけで全部の辺を持ちたくなります。そのため、完全グラフを作るように辺を張っていくとよいです。 $k$ 頂点の完全無向グラフの辺数は $\frac{k(k-1)}{2}$ 本なので、 $m \le \frac{k(k-1)}{2}$ であれば $k$ 頂点で $m$ 本の辺を持てます。この不等式を満たす最小の $k$ を求めて、孤立点の最大数は $N-k$ となります。

ACコード

Submission #44123483 - Codeforces

C. Make It Equal

Problem - C - Codeforces

問題概要

ブロックが積まれてできた $n$ 本の塔があり、それぞれの高さはブロック $h_{i}$ 個である。

以下の操作を、全ての塔の高さが等しくなるまで繰り返す。操作回数の最小値を求めよ。

ある高さを決める。このとき、その高さ以上にあるブロックの個数が $k$ 個以下でなければならない。その高さ以上のブロックを全て取り除く。

制約

$1 \le n \le 2\times 10^{5}$
$n \le k \le 10^{9}$
$1 \le h_{i} \le 2 \times 10^{5}$

解法

毎回の操作で、 $k$ 個を超えないギリギリまでブロックを取り除くのがもちろん最適です。そのため、上から数えたブロック数が $k$ 個を超えない最小の高さを求めたくなります。

「今の操作で除去できる残りブロック数」を管理しておいて、今の操作でどこまで除去できるか1段ずつ調べます。このとき「今の時点で一番高さが高い塔の本数」を管理しておくと、1段下げたときいくつのブロックが除去されるかが分かります。

残りブロック数が足りなくなった時点で、次の操作に移ります。これを一番低い塔の高さに到達するまで繰り返します。

$h_{i}$ の上限が少ないので、これで十分間に合います。

ACコード

（C++）Submission #44183329 - Codeforces

本番ではもう少しまとめて計算するようなコードを書いていて、こっちだと $h_{i}$ が大きくても対応できるのですが、そのぶん実装が少しだけ複雑です。

D. Three Pieces

Problem - D - Codeforces

問題概要

$N \times N$ のチェス盤の各マスに、 $1, 2, ..., N^{2}$ の数字が1つずつ記載されている。このチェス盤上で、以下の操作を行う。

1のマスに、ルーク・ビショップ・ナイトのうち好きな種類の駒を置く。
以下の操作を好きな順番で繰り返し、の順にマスを訪れる。途中で他のマスを経由しても良い。
- チェスのルールにおける駒の動き方に則って駒を1手分動かす。
- 駒をルーク・ビショップ・ナイトのいずれかに交換する。

$N^{2}$ が書かれたマスに到達するまでの操作の合計回数を $a$ 、そのうち駒の種類を交換した回数を $b$ として、 $(a, b)$ を辞書順最小にしたい。そのような $a, b$ を求めよ。

制約

$3 \le N \le 10$
マス $(i, j)$ に書かれた数を $A_{ij}$ として、 $1 \le A_{ij} \le N^{2}$ でありこれらは互いに異なる

解法

駒の交換と移動があり、遷移が複雑です。グラフに帰着して、最短路問題などのアルゴリズムを使って上手く処理したいです。

状態として「位置」と「駒の種類」の組み合わせを考え、それぞれが1頂点となるようなグラフを考えます。頂点の数は $V = 3N^{2} \le 300$ です。駒の移動も交換も、この頂点間の遷移として考えることができます。

頂点間の距離は、求める答えと同じように $(操作回数, そのうちの駒交換回数)$ のペアで定義し、辞書順比較します。駒の移動と交換に対応する遷移を辺として追加し、ワーシャルフロイド法を用いると、ある状態からある状態までの最短距離を計算することができます。 $V \le 300$ なので $O(V^{3})$ のワーシャルフロイドが間に合うのがポイントです。

これを用いて答えを求めましょう。 $1, 2, ..., N^{2}$ を順に通る最短路を求めるにあたり、「頂点 $1, ..., i$ までの巡回が完了し、今の駒が $j$ であるときの、最初の状態からの最短距離」を $dp\lbrack i \rbrack \lbrack j \rbrack$ としてDPができます。 $dp\lbrack i+1 \rbrack \lbrack j \rbrack$ を求めるときには、 $dp\lbrack i \rbrack \lbrack 0 \rbrack, dp\lbrack i \rbrack \lbrack 1 \rbrack, dp\lbrack i \rbrack \lbrack 2 \rbrack$ すべてからの遷移を試して最も小さいものを採用します。これを $i=N^{2}$ まで回せば答えが求められます。

ACコード

（C++）Submission #44180256 - Codeforces

E. Side Transmutations

Problem - E - Codeforces

問題概要

$|A|$ 種類の文字があり、その一部または全部で構成される $n$ 文字の文字列を考える。

整数 $b_{1}, ..., b_{m}$ が与えられる。文字列 $S$ と $T$ は、 $S$ に以下の操作を0回以上行って $T$ と一致させることができる時、「等しい」と呼ぶ。

$b_{i}$ を1つ選ぶ。操作対象の文字列の前 $b_{i}$ 文字と後ろ $b_{i}$ 文字を、それぞれ反転して交換する。

「等しい」文字列は区別せず1種類と数えることにしたとき、 $n$ 文字の文字列の種類数を数え上げて、 $998244353$ で割った余りを出力せよ。

制約

$2 \le n \le 10^{9}$
$1 \le m \le \min(\frac{n}{2}, 2\times 10^{5})$
$1 \le |A| \le 10^{9}$

解法

問題文の操作を繰り返すことで、何が起こるでしょうか。例えば、2つの異なる箇所で操作を行うと、以下のように文字列が変化します。

f:id:betrue12:20181012224005p:plain

$b_{i}$ の位置を区切りとして、左右それぞれ対応するペアを考えます。操作を繰り返すことで、任意のペアを入れ替えることができます。つまりこのペアをいくつか入れ替えることで一致するような文字列が、今回の問題でいう「等しい」文字列です。

ペアの入れ替えを独立に考えられるので、場合の数も独立に考えて掛け算することができます。 $b_{1} - b_{0}$ 文字のペア、 $b_{2} - b_{1}$ 文字のペア…というように、それぞれのペアについて独立に「反転で一致するものを同一視したときに文字列が何通りあるか」を数えて、これを掛け算すればよいです。（ $b_{0} = 0$ としておくと便利です）

ただし真ん中の部分の文字列は反転できないので、単純に「文字列が何通りあるか」を数えて掛け算します。それらを全て掛け合わせたものが答えです。

各ペアについての場合の数を考えます。 $d_{i} = b_{i+1} - b_{i}$ と置くと、求めたいものは「長さ $2d_{i}$ の文字列を、反転すると一致するものは同一視して数えたときの場合の数」です。「反転すると一致する」文字列は、文字列が回文でない場合は1対1で相手が存在し、回文である場合は反転しても自分自身になるので相手が存在しません。

そのため反転を同一視しない全ての文字列の数を $n_{all}$ 、回文になっている文字列の数を $n_{pal}$ とすると、回文になっていない文字列が同一視で半減することから、求めたい数は $\frac{n_{all} - n_{pal}}{2} + n_{pal}$ となります。具体的に計算すると $n_{all} = |A|^{2d_{i}}$ 、 $n_{pal} = |A|^{d_{i}}$ であるため、これらを全て計算していけばよいです。

ACコード

（C++）Submission #44153485 - Codeforces

F. Up and Down the Tree

Problem - F - Codeforces

問題概要

根を頂点1とする $n$ 頂点の根付き木と、整数 $k$ が与えられる。頂点1にトークンを置いた状態から、以下の操作を0回以上繰り返す。

いまトークンが置かれている頂点をとして、
- $v$ が葉でない場合、 $v$ 以下の部分木に含まれる葉のうちいずれかにトークンを移す。
- $v$ が葉である場合、 $v$ から最大 $k$ 回親を辿った先の頂点にトークンを移す。

頂点1にトークンを置いた状態からスタートし、なるべく多くの葉を訪れたい。その最大数を求めよ。

※接続されている辺の数が1本である頂点を葉と呼ぶが、今回は根である頂点1は葉ではないとして扱う。

解法

ある頂点から葉に降りたときに、元の頂点に戻って来れる場合と来れない場合があります。イメージとしては、葉が深いところにあり、途中で経由できるような葉もないときは戻ってこれません。

そのため、ある頂点以下の部分木でなるべく多くの葉を訪れようとすると、以下のような戦略になります。

全ての子に対して、まずは降りた後に自分自身に戻って来れる範囲で葉を回収する。
最後に1つだけ子を選んで降り、戻って来れない範囲の葉も回収し、操作を終える。

これは再帰的に処理していくことができます。つまりそれぞれの頂点に対して、

$dp_{1}\lbrack i \rbrack$ = 頂点 $i$ 以下の部分木で、 $i$ から始めて自分自身に戻って来ることが必要な場合、いくつ葉を回収できるか
$dp_{2}\lbrack i \rbrack$ = 頂点 $i$ 以下の部分木で、 $i$ から始めて自分自身に戻って来なくてもよい場合、いくつ葉を回収できるか

を葉のほうから決めていくような木DPができます。 $dp_{2}\lbrack 1 \rbrack$ が答えです。

このDPの遷移を考えます。ある頂点 $i$ に着目し、その子 $j$ を順に見ていきます。

子 $j$ から $i$ に（ $j$ 以下のいずれかの葉を経由して）移動できる場合は、 $i$ から $j$ 側に降りて $dp_{1}\lbrack j \rbrack$ 個の葉を回収し、また $i$ に戻ってくることができます。もし最後に子 $j$ 側に降りるのであれば、追加で $dp_{2}\lbrack j \rbrack - dp_{1}\lbrack j \rbrack$ 個の葉を回収することができます。
子 $j$ から $i$ に移動できない場合は、葉を回収して戻ってくることができません。ただし、最後に子 $j$ 側に降りるのであれば $dp_{2}\lbrack j \rbrack$ 個の葉を回収することができます。

このようにそれぞれの子からの情報を得て、「戻ってこれる範囲で回収できる葉の数」の合計を $dp_{1} \lbrack i \rbrack$ とし、「最後に子 $j$ に降りるのであれば追加で回収できる葉の数」の最大値を $dp_{1} \lbrack i \rbrack$ に足したものを $dp_{2} \lbrack i \rbrack$ とします。

ここで「子 $j$ から親 $i$ に移動できるか」は、 $j$ から見て一番浅い位置にある葉の深さで決まります。そのような葉 $l$ から $i$ までの距離が $k$ 以下であれば、 $j \to l \to i$ という遷移ができます。

ACコード

（C++）Submission #44148563 - Codeforces

さいごに

Dが落ちたのは完全に不注意。実装がキツい問題だと思っていたけど、ちゃんと整理して書くと意外とスッキリ書けました。

Eは本番最後に方針が見えたので惜しかったです…。Fが解けそうだったので先にそっちに行きました。木DP好き。

2018-10-11

CF495 F. Sonya and Bitwise OR

Codeforces プログラミング競技プログラミング

コンテスト参加記録だけじゃなくて、過去問を解いた時も時々記事を書いていこうかなと思います。

自分用なので、解説というよりは考察・学習メモ。いつもよりは雑になります。

問題情報

リンク

Problem - F - Codeforces

問題概要

長さ $n$ の数列 $a_{1}, ..., a_{n}$ と整数 $x$ が与えられる。以下のクエリ合計 $m$ 個を処理せよ。

1 i y : $i$ 番目の要素 $a_{i}$ の値を $y$ に変更する。
2 l r : 区間 $\lbrack l, r \rbrack$ に含まれる部分区間 $\lbrack L, R \rbrack$ であって、その区間に含まれる要素 $a_{L}, ..., a_{R}$ のビットORを取ったものが $x$ 以上になるものの個数を出力する。

制約

$1 \le n, m \le 10^{5}$
$0 \le x, a_{i} \lt 2^{20}$
クエリ1について、 $1 \le i \le n$ 、 $0 \le y \lt 2^{20}$
クエリ2について、 $1 \le l \le r \le n$

考察

クエリ2を区間和問題に帰着

まず考えたこと。

区間に関する大量のクエリ。セグ木っぽい。
ORは要素を足していくと単調増加するので、1クエリに $O(n)$ 使っても良いならしゃくとりできる。でも今回はクエリが多いので間に合わない。
1クエリにかけていい時間が $O(1)$ か $O(\log n)$ くらいなので、区間和とかを使ってまとめて計算したい。

というところで、各インデックス $i$ ごとに「左端を $i$ とした区間で、条件を満たすものの個数」のような値を持っておき、BITやセグ木で区間和を取れないかと考えた。ただ、これだと少し扱いにくい。

これを少し修正し、単調性があることを利用して「左端を $i$ とした区間が条件を満たすときの、一番小さい右端の位置」とする。こうすると、そのような右端の位置は $i$ を増加させると単調増加していくので、扱いやすそう。

「左端を $i$ とした区間が条件を満たすときの、一番小さい右端の位置」を保持しておき、これを $b_{i}$ と表記する。これが求まっていると、クエリ 2 l r に対する答えは以下のように求められる。

$b_{i} \le r$ となる最大の $i$ を求める。 $b_{i}$ が $i$ について単調増加なので、これは二分探索できる。
以下の図のように、長方形の面積から $b_{i}$ の区間和を引き算することで、求めたい区間の数が求められる。

f:id:betrue12:20181011214713p:plain

これなら、

二分探索は要素アクセスが $O(1)$ であれば $O(\log n)$ 。ただし $b_{i}$ がセグ木に乗っている場合は、単純にやると $O((\log n)^{2})$ 。
区間和は $O(\log n)$ 。

ということで、 $O(m (\log n)^{2})$ であればなんとか通りそう。次は $b_{i}$ をどのように維持するかを考える。

クエリ1の処理

$b_{i}$ の初期値は、区間ORをセグ木に入れて二分探索をすると全要素 $O(n (\log n)^{2})$ で求められる。最初にこれを計算しておく。

問題はクエリ1の処理。 $a_{i}$ の値が変更されると、もちろん $b_{j}$ の値も変わる可能性がある。より具体的には、クエリ 1 i y に対して、

$j \le i$ を満たす位置 $j$ であって、
変更前の値 $b_{j}$ が $i \le b_{j}$ を満たすもの

は、 $b_{j}$ の値が変わる可能性がある。（ $b_{j} \lt i$ であるときは、 $a_{i}$ の値が変わっても $b_{j}$ は変化しない）

この条件を満たす全ての $j$ を見ていくのは非常に大変だが、ここでORの性質を思い出す。要素を追加していったとき、ORの値は「今までになかったビットが増えた」ときにしか増えない。

つまり $i$ を起点にして、左側に区間を広げるにしろ、右側に区間を広げるにしろ、「新しいビットが登場」するポイントでのみORの値が変わるため、そこだけを調べればよいことがわかる。

ということで、「要素 $i$ から見て、左側/右側それぞれ、一番近いところで $k$ 番目のビットが立っているのはどこか」が各ビット位置 $k$ について欲しくなる。もしこれが分かっていれば、

左端は $i$ から始めて、ビットが増える点ごとに左に伸ばしていく。
それぞれの左端 $j$ に対して、右端をどこまで伸ばせばORの値が $x$ 以上になるかを調べる。このときも、ビットが新しく立つ点のみを調べれば良い。
これで、ある左端 $j$ について $b_{j}$ が求まった。ここで、 $j$ から次にビットが増える直前まで左端を伸ばしても、右端の値は変わらないはずである。なので、区間に対して $b_{j}$ を同じ値で上書きすることができる。

というような更新が $O(B^{2})$ でできる。ここで $B$ は $a_{i}$ の最大ビット数であり、すなわち $B = 20$ である。

ということで、「要素 $i$ から見て、左側/右側それぞれ、一番近いところで $k$ 番目のビットが立っているのはどこか」が必要になる。この値もクエリ1によって変動するが、区間更新できるようなデータ構造に乗せておけば更新は難しくない。

必要な道具の整理

ここまでの考察から、必要な道具を整理する。

まず、 $b_{i}$ の初期値を求めるために

の初期値の区間ORの値
- 必要な操作：1点更新、区間OR

が必要であり、これはセグメント木で可能である。そのほかに、

要素から見て、左側/右側それぞれ、一番近いところで番目のビットが立っているのはどこか
- 必要な操作：区間更新、1点取得
左端をとした区間がクエリ2の条件を満たすときの、一番小さい右端の位置
- 必要な操作：区間更新、区間和

これらが必要である。

区間更新を行うには、遅延評価セグメント木を用いることができる。書いたことが無かったので、以下の記事を参考にしつつ、区間更新、区間和ができるものに修正した。（つたじぇーさんありがとうございます！）

遅延評価セグメント木をソラで書きたいあなたに - hogecoder

これで必要な道具が全部揃った。

ACコード

Codeforces

実行時間はギリギリだった。実装もなかなか重め。

余談

公式解法は違う解き方をしていて、遅延評価セグメント木を使っていない。何故か英語の解説がないが、親切な人がロシア語解説からの翻訳を書いてくれている。

感想

OR演算の単調性をフル活用した。難しい問題だと、このレベルのテクは呼吸するように使うことが求められる。
「区間の数」の数え上げは愚直だと $O(n^{2})$ 以上かかり、これを工夫で $O(n)$ や $O(n \log n)$ にすることはよくある。今回はそこからさらに落とすための発想が必要だった。
「答えを得るために必要な値は何か」「その値を得るために必要な値は何か」…というように、難しい問題でも段階的に考察を進めていくことができた。本番でもこれができるようになりたい。
遅延評価セグメント木を初めて使った。初めて使う道具で重い問題に挑むのは無謀。今回もかなりバグらせた。

2018-10-07

Codeforces Round #514 (Div. 2) 参加記録＆解説（A～E）

Codeforces プログラミング競技プログラミング

Dashboard - Codeforces Round #514 (Div. 2) - Codeforces

結果は4完で88位。

f:id:betrue12:20181006175548p:plain

本番後に通したEも含めて5問振り返ります。

A. Cashier

Problem - A - Codeforces

問題概要

$0 \le t \le L$ の区間を考える。この中に、 $n$ 個の「選択不能区間」 $t_{i} \le t \le t_{i} + l_{i}$ が存在する。選択不能区間および他の選択区間と端点以外で重ならないように、 $0 \le t \le L$ の区間の中から長さ $a$ の区間をできるだけ多く選択する時、その個数を求めよ。

制約

$0 \le n \le 10^{5}$
$1 \le L \le 10^{9}$
$1 \le a \le L$
$0 \le t_{i} \le L-1, 1 \le l_{i} \le L, t_{i} + l_{i} \le t_{i+1}, t_{n} + l_{n} \le L$

解法

区間と区間の間から長さ $a$ の区間を取れるだけ取ります。両端を区間の1つとして扱うと実装が楽です。

ACコード

Submission #43832898 - Codeforces

B. Forgery

Problem - B - Codeforces

問題概要

# と . で構成された $n \times m$ のマス目が与えられる。# が黒、. が白を示す。

$n \times m$ の全てのマスが白い状態から、「以下のような中央に穴の空いた形をした $3\times 3$ のハンコを、この向きのままマス目の好きな位置に押す」ことを0回以上繰り返し、与えられたマス目を再現したい。これが可能かどうか判定せよ。

###
#.#
###

ハンコの黒い部分が押されたマスは黒になり、中央の穴に相当するマスは変化しない。マス目からはみ出すようにハンコを押すことはできない。

※問題文がちょっと曖昧なので、問題文に明記されていないことも含めて補足をしています…

制約

$3 \le n, m \le 1000$
与えられるマス目は $n$ 行 $m$ 文字の文字列で、# と . からなる

解法

まず、全部白のマス目を用意します。盤面から切り取れる全ての $3 \times 3$ のマス目について、「与えられたマス目において、その $3 \times 3$ の位置のうちハンコの形状通りの8マスが全て黒であれば、用意したマス目において同位置の8マスを黒く塗る」という操作をします。真ん中の色がどちらか、は気にしません。

これで、ハンコを押して良い位置が全て押されたことになります。この操作によって与えられたマス目を全て再現できている場合答えは YES となり、そうでない場合は NO となります。

盤面から切り取れる $3 \times 3$ のマス目は全部で $(n-2)(m-2)$ 個あり、計算量が $O(nm)$ となりますが、この制約では十分間に合います。

ACコード

Submission #43839595 - Codeforces

C. Sequence Transformation

Problem - C - Codeforces

問題概要

正整数 $n$ が与えられる。「操作」の数列を $1, 2, ..., n$ 、「結果」の数列を空として、以下の操作を $n$ 回繰り返す。

「操作」の数列全ての要素の最大公約数（GCD）を、「結果」の数列の末尾に追加する。
「操作」の数列から、好きな要素を1つ取り除く。

この操作の結果となる「結果」の数列を、辞書順最大にしたい。そのときの「結果」の数列を出力せよ。

制約

$1 \le n \le 10^{6}$

解法

最初の状態では、GCDは1です。辞書順最大を求めたいので、「なるべく早くGCDを1より大きい値にしたい」と考えます。つまり、1以外でなるべく多くの要素のGCDとなっているものを探して、それ以外の要素を取り除きたいです。ただし、要素数が同数の場合は大きいほうのGCDを採用します。

最初の $1, 2, ..., n$ の状態では、ほとんどの場合そのようなGCDは2です。GCDを2にするため、まずは奇数を取り除きます。

奇数を取り除くと、数列は $2, 4, ..., \lfloor\frac{n}{2}\rfloor$ となります。次は何が一番多いでしょうか？　既に最大公約数となっている2を無視すると、この数列はやはり $1, 2, ..., n^{\prime}$ のような形をしています。同じように考えると、やはり一番多いのは2、すなわち元の数列で言う4です。

このように、 $1, 2, ..., n^{\prime}$ の $2^{k}$ 倍の形状をした数列から奇数番目の要素を取り除き、そうするとその結果はやはり $1, 2, ..., n^{\prime\prime}$ の $2^{k+1}$ 倍になっていて…という操作を繰り返すことで、多くの場合解を求めることができます。

ただし問題ページ中のサンプルにもあるように例外があります。それは数列が $1, 2, 3$ であるとき、もしくは操作の途中でその $2^{k}$ 倍になったときです。このとき、2も3も含まれる要素の個数は同じ1個なので、大きい方である3を残さないといけません。

ACコード

Submission #43843969 - Codeforces

D. Nature Reserve

Problem - D - Codeforces

問題概要

$xy$ 平面上に $n$ 個の点 $(x_{i}, y_{i})$ が配置されている。以下のような条件を満たす円が存在する時、その半径の最小値を求めよ。または存在しないことを判定せよ。

その周上または内部に $n$ 個の点を全て含む。
$x$ 軸（直線 $y=0$ ）に1点で接する。

制約

$1 \le n \le 10^{5}$
$-10^{7} \le x_{i}, y_{i} \le 10^{7}$ , $y_{i} \ne 0$

解法

まず条件を満たすためには、 $y_{i}$ が正または負に全て固まっていることが必要です。 $x$ 軸に接する円は、 $y$ が正負どちらか片方の領域にしか存在できないからです。逆に正または負に固まっている場合、半径をものすごく大きくとればいつかは全ての点が収まるので、解は存在します。

以降、 $y$ 座標が全て負の時は反転し、全て正としておきます。

半径を $r$ とします。条件を満たす $r$ の範囲は単調（求めたい最小値を $r_{\min}$ とすると、 $r \ge r_{\min}$ の範囲の $r$ は全て条件を満たす）なので、二分探索をします。つまり半径 $r$ を固定して、条件を満たすかどうかのYes/No問題を解きたいです。

$x$ 軸に接するということは中心の $y$ 座標は $r$ であり、円内部の方程式は中心の $x$ 座標を $a$ として

$(x-a)^{2} + (y-r)^{2} \le r^{2}$

です。与えられた座標点 $(x_{i}, y_{i})$ が円内部に存在する条件は、この座標を代入して $a$ についての方程式を解くと求められます。

$n$ 個の点全てについて $a$ が存在すべき範囲を求めて、それらが共通点を持てば、条件を満たす円が存在するので判定はYesです。このようにYes/No問題を解いて、二分探索をすることができます。

最後に、二分探索の初期範囲を考えます。半径が小さすぎると、 $y$ 座標が大きな点にそもそも届きません。先程の方程式でいうと「実数解が存在しない」ということに相当します。全ての $y_{i}$ に届くよう、下界は $\frac{\max y_{i}}{2}$ とします。

そして上界ですが、これが意外と大きくなります。点群に、 $(-10^{7}, 1)$ と $(10^{7}, 1)$ のように $y$ 座標がとても小さくて $x$ 座標がとても離れた点が存在すると、必要な半径は大きいです。実際に求めてみます。

f:id:betrue12:20181006192949j:plain

このケースにおいて三平方の定理を使うと $r = \frac{10^{14}+1}{2}$ となります。おそらくこれが最大です。大きく取りすぎても反復回数が数回増えるだけなので、どんぶり勘定で大きめに取っておいてもいいとは思います。

計算量は1回のYes/No問題が $O(n)$ 、反復回数は初期範囲と終了範囲の長さの比を取ったものの $\log$ オーダーで、ほとんどの場合100回以内に収まるんじゃないかと思います。（私は100回指定でループしています）

ACコード

Submission #43849835 - Codeforces

E. Split the Tree

Problem - E - Codeforces

問題概要

頂点 $n$ 個の根付き木が与えられ、各頂点には重み $w_{i}$ が設定されている。

これらの頂点を、互いに交わらない、以下の条件を満たす集合に「垂直分割」する。その集合の個数の最小値を求めよ。

集合に含まれる要素は、ある要素から親を辿ったもの、またその親を辿ったもの…というように、縦一列に並んでいる。
集合の要素数は $L$ 以下である。
集合に含まれる要素の重み合計は $S$ 以下である。

制約

$1 \le n \le 10^{5}$
$1 \le L \le 10^{5}$
$1 \le S \le 10^{18}$
与えられる木は頂点1を根とする根付き木である

解法

木DPを考えてみます。子のほうから順に処理をしていって、ある頂点に注目したとき、パスの取り方としてどのようなものがあるでしょうか。

子から伸びてきている「未完成の集合」のうち、高々1つに自分を加える。残りはその時点で完成した集合となる。
その後、自分（または自分を加えた集合）を、「未完成の集合」として親に伸ばす。

ここで難しいのが、「子から伸びてきている集合のうち、どれを採用して上に伸ばすか？」です。将来性があるものを上に伸ばしたいですが、長さと重み合計という2つの条件があるので、短いものがいいのか軽いものがいいのか単純には決められません。

ただこの問題の場合、親を順に辿っていくようにしか要素が追加されないため、将来的に追加されていく要素とその順番は決まっています。そのため「いまこの集合から、あと上にいくつの要素を足せるか？」というものを事前に計算してしまうことができます。これを計算し「上に足せる要素数が最も多いもの」を選べば、当然それが最適になるということです。

ということで、次は「いまこの集合から、あと上にいくつの要素を足せるか？」を効率的に求める方法を考えます。これを毎回1つずつやっていると間に合わないので、ダブリングという方法を使います。これは

ある点から、
- 上に1個足したときの増加重み合計はXXで、1つ上の親は○
- 上に2個足したときの増加重み合計はXXで、2つ上の親は○
- 上に4個足したときの増加重み合計はXXで、4つ上の親は○

というように、2の冪乗ごとに「 $2^{k}$ 進んだときの情報」を事前計算しておく方法です。これを計算しておけば、「いまこの集合から、あと上にいくつの要素を足せるか？」を計算する時は逆順に「8個要素を足せるか？」「4個要素を足せるか？」「2個要素を足せるか？」…　のように考えていくことで、効率的に計算をすることができます。

解法をまとめると、

まず事前計算として、各頂点について「親を $2^{k}$ 個辿ったときの重み合計」と「辿った先の親」を、 $2^{k} \le n$ である $k$ それぞれについて計算する。
葉から木DPをする。を「頂点を含んでいる集合から、上にいくつ要素を足せるか」とする。
1. 子の中で、「上にいくつの要素を足せるか」が正のものが存在する場合、その値が最も大きいものを採用し、その集合に自分を含める。つまり子 $j$ のうち $dp\lbrack j \rbrack \gt 0$ であるものが存在する場合、その中で最大のものを選んで $dp\lbrack i \rbrack = dp\lbrack j \rbrack - 1$ とし、残りの集合は完成させる（答えの個数に加算する）。
2. 1で自分を含めた集合がなかった場合は、自分自身を始点とする新しい集合を作る。このとき「上にいくつの要素を足せるか」を事前計算の結果を使って効率的に計算し、 $dp\lbrack i \rbrack$ とする。
3. 1, 2いずれの場合においても、これ以上上に伸ばせない場合、つまり $dp\lbrack i \rbrack = 0$ であるときは、集合を完成させる。また見ている頂点が根である場合も、もう上はないので集合を完成させる。
完成させた集合の個数が答えである。

のようになります。

ダブリングについては以下の記事が図説スライド付きで分かりやすいのでオススメです。また、蟻本にも載っています。

ダブリング - sataniC++

ACコード

Submission #43889325 - Codeforces

さいごに

順位としてはまあまあ。Eは解きたかったですね…

2018-10-06

ABC112 参加記録＆解説

AtCoder プログラミング競技プログラミング

AtCoder Beginner Contest 112 - AtCoder

結果は26分台全完で42位。まあまあ。

f:id:betrue12:20181006213126p:plain

A - Programming Education

解法

分岐してそれぞれ処理。年商10億円突破楽しみにしています。

ACコード

（Ruby）Submission #3341720 - AtCoder Beginner Contest 112

B - Time Limit Exceeded

解法

求めたいコストを $c$ として、ループを回して $t_{i} \le T$ であれば $c$ を $\min(c, c_{i})$ で置き換える、を繰り返します。

$c$ の初期値としては、どの $c_{i}$ よりも大きい値を設定しておくとよいです。今回であれば1001や10000など。ここから一度も更新されなければ TLE という判定ができます。

ACコード

（Ruby）Submission #3342869 - AtCoder Beginner Contest 112

C - Pyramid

解法

ちょっとだけ設定が複雑に見えますが、条件として与えられる点の数 $N \le 100$ 、中心座標の候補が $0 \le C_{x}, C_{y} \le 100$ であることから全探索が可能です。中心座標を全探索します。

中心座標 $(C_{x}, C_{y})$ を固定した時、その中心座標について「全ての条件を満たすようなピラミッドの高さ $H$ が存在するか？」を調べます。もしそのような $H$ が存在すれば、制約より解は1組だけしか存在しないため、見つかったものを出力して終了すればよいです。

条件となっている点 $(x_{i}, y_{i})$ を順番に見ていきます。式を見やすくするため、 $(x_{i}, y_{i})$ から中心までのマンハッタン距離を $d_{i} = |C_{x} - x_{i}| + |C_{y} - y_{i}|$ と表記します。問題文中の式は $h_{i} = \max(H - d_{i}, 0)$ と書き換えられます。

中心を固定し、条件となっている点 $(x_{i}, y_{i})$ を1つチェックし、その高さが $h_{i}$ となるために中心の高さ $H$ が満たすべき条件を考えます。その条件は、 $h_{i} = 0$ のときとそうでないときで以下の図のように異なります。

f:id:betrue12:20181009200752p:plain

のとき
- このとき、これを満たす $H$ はただ1つであり、 $H - d_{i} = h_{i}$ より $H = d_{i} + h_{i}$ である。
のとき
- このとき、これを満たす $H$ の候補は1つに絞られない。ただし、「 $H$ は $d_{i}$ 以下である」という条件は満たされる必要がある。 $H$ がこれより大きいと $H - d_{i}$ が正になり、すなわち $h_{i}$ も正になってしまうため。

これを全ての点について調べ、矛盾がなければそれを出力して終了です。矛盾があれば、次の中心座標を試します。これを繰り返せば、制約上どこかで解が見つかります。

ACコード

D - Partition

解法

$a_{1}, ..., a_{N}$ の公約数を $d$ とします。このとき、以下の2つが成り立つことが必要です。

$d$ は $a_{1} + ... + a_{N} = M$ の約数である。
$a_{i} \ge d$ であることから、 $M = a_{1} + ... + a_{N} \ge Nd$ である。

逆にこれらを満たす時は、 $\frac{M}{d}$ 個の $d$ を最低1個ずつ適当に $a_{i}$ に割り振れば、 $d$ は $a_{1}, ..., a_{N}$ の公約数になります。

つまりこれら2つの条件を満たす中で最大の $d$ が、求めたい「最大公約数の最大値」です。

ということで、まず $M$ の約数を列挙しましょう。素因数分解を使う方法もありますが、1から $\lfloor\sqrt{M}\rfloor$ までの整数で割ってみる方法が楽です。もし $i$ で割り切れたら、その $i$ と $\frac{M}{i}$ が約数になるので、これを集めます。

約数が列挙できたら、 $Nd \le M$ を満たすものだけを抜き出し、その中の最大値が答えです。制約 $N \le M$ より $d = 1$ は必ず条件を満たすので、解無しとなる可能性はないです。

ACコード

（Ruby）Submission #3352713 - AtCoder Beginner Contest 112

最後に

前回のABCオンリー回も、Dは約数絡みの問題でしたね。最近の流行り？

2018-09-30

ARC103 参加記録＆解説（C～E）

AtCoder プログラミング競技プログラミング

AtCoder Regular Contest 103 - AtCoder

結果はCE2完+D部分点で73位。黄色復帰！

今回、この獲得点数の人が180人くらいいたので、スピードも功を奏したと思います。

f:id:betrue12:20180930102724p:plain

C～Eを振り返ります。

C - /＼/＼/＼/

↑半角バックスラッシュが円マークになるので全角にしました…

C - /\/\/\/

解法

偶数番目と奇数番目に分けて考えます。変更個数を少なくするためには、それぞれ元から一番多かった数字を残したくなります。

一番多かった数字が異なっていれば、それらをそのまま採用できます。もし同じ数字だった場合は 数列に現れる数はちょうど2種類 という条件に反しないよう、片方を諦めて2番手にする必要があります。「奇数1番手+偶数2番手」と「奇数2番手+偶数1番手」の両方を試して、登場回数合計の多い（＝変更が少ない）ほうを採用します。

ACコード

D - Robot Arms

解法

必要条件を導出する

まず、解が存在する必要条件を考えます。いったん $x$ と $y$ の区別をなくし、「それぞれの腕が正負どちらの方向に伸びているか？」を考えます。これを符号付きで全部足し算したものが、最終到達地点の座標を足したもの、つまり $X_{i} + Y_{i}$ となります。

ある腕を、負から正に変更したとします。その腕の長さを $d_{i}$ とすると、 $-d_{i}$ だったものが $+d_{i}$ になるため、最終地点の座標の和は $+2d_{i}$ 加算されます。逆に正から負に変更した場合は $-2d_{i}$ です。

より一般的に言うと、腕の正負を入れ替えた時、その長さの2倍だけ座標和が変動します。奇数の長さで変動することはありません。つまり作らなければいけない最終到達地点 $(X_{1}, Y_{1}), ..., (X_{N}, Y_{N})$ について座標和を考えると、それらの差は全て偶数である、言い換えると偶奇が一致している必要があります。

まずこれが必要条件になります。

構成方法を考える

では、構成方法を考えましょう。作りたいパターン数が $N \le 1000$ というのはそこまで多い数ではないですが、何と使える腕の本数が $m \le 40$ しかありません。1つ1つのパターンを見て腕の長さを決めていく方法は無理そうです。どんな数でも作れる「必勝法」を考えたいです。

「どんな数でも作れる」の定石は $n$ 進数です。2進数を使うとすると、作りたい座標は $0 \le |X_{i}|, |Y_{i}| \le 10^{9} \fallingdotseq 2^{30}$ であり、腕40本でも足りそうな雰囲気です。ただ、 $x, y$ をそれぞれ作るとなると、それぞれに腕が30本必要そうに見えますし、不必要な腕をどう調整するかも難しく思えます。

ではどうすればいいかというと、 $x, y$ を それぞれ作る をやめて、同時に作る ようにします。1本の腕の方向を選ぶことで $x, y$ 両方の値を操作できれば、腕の数が足りそうです。もちろんこのままでは無理ですが、それを可能にするのが座標変換です。

$u = x+y, v = x-y$ として、 $uv$ 座標系を考えます。これは、座標平面を45度回転しているような変換です。

f:id:betrue12:20180930114650p:plain

このように変換すると、腕の4方向が「 $u$ と $v$ それぞれ、正負どちらの方向にはたらくか」の4通りに対応します。2つの値を同時に操作することができて、かつ「 $u$ は増やしたいけど $v$ は減らしたい」みたいな要求4パターン全てに対応できるのが嬉しいポイントです。

目的地の座標も変換して $(U_{i}, V_{i})$ と書くことにします。そうすると $0 \le |U_{i}|, |V_{i}| \le 2\times 10^{9} \fallingdotseq 2^{31}$ と値の範囲が変わりますが、腕は40本あるので大丈夫です。各腕に $1, 2, 4, 8, ..., 2^{30}$ を割り振って、これらの足し算引き算だけで目的の値を作ることを考えます。

普通の0 or 1の2進数とは違い、-1 or 1の2進数（？）となっていますが、以下のように「大きい方から選ぶ」ことを考えればよいです。

f:id:betrue12:20180930115950p:plain

常に目的の値に近づく方向に正負を採用していけば、最後は目的の値に辿り着きます。実際には目的の値が「3」のような小さな数のときでも、もっと大きな値を組み合わせて作ることになりますが、その場合でも考え方は同じです。

ただしこれがキレイに収まるのは $U_{i}, V_{i}$ が奇数の場合で、偶数の場合は最後にもう1つ1を付けて調整してあげる必要があります。

※ $U_{i}$ と $V_{i}$ の偶奇は一致するため、片方では追加で1が必要だけどもう片方では余計、という事態にはならないので安心です。

f:id:betrue12:20180930120955p:plain

これで解けました。解法をまとめると、

まず目的地の座標和の偶奇が一致しているかチェック。一致していなければ解なしで終了。
座標変換を行う。
腕の長さとして $2^{30}, ..., 4, 2, 1$ の値を用意する。目的地の座標和が偶数の場合、さらに1を足す。
それぞれの目的地ごとに、大きい方の腕から方向を決めていくことで目的の値を作る。

これで解けます。

ACコード

（C++）Submission #3305898 - AtCoder Regular Contest 103

※部分点解法は、全部の腕の長さを1にしても足りるので、偶奇チェックした後は全部1で作ります。部分点獲得コードはこちら。

E - Tr/ee

解法

必要条件を導出する

これも、まず必要条件を考えます。

サイズ1の連結成分は必ず作れる。葉だけを切断するとサイズ1の連結成分になるため。
サイズ $n$ の連結成分は必ず作れない。サイズ $n$ の木を切断するとそれぞれの部分木のサイズは $n$ 未満になるため。
サイズ $i$ の連結成分が作れるならば、サイズ $n-i$ の連結成分も作れる。切断によってサイズ $i$ の連結成分ができたとき、もう片方はサイズ $n-i$ になっているため。

入力がこれらの条件に反する場合、条件を満たす木は構築不可能です。

構成方法を考える

サイズの小さいほうから考えていきましょう。根付き木として考えたとき、深いほうから順に構成していきます。

先ほど見たように、サイズ1は必ず作れます。では「サイズ2が作れる」と「サイズ2が作れない」は、どのように差を付ければ良いでしょうか。

f:id:betrue12:20180930123643p:plain

サイズ2を作りたい場合、サイズ2の部分木の上に親を作ればよいです。逆に作りたくない場合は、サイズ2の部分木で親となっている頂点に、さらに子を生やせばよいです。これを繰り返すことで目的の木を作ることができて、もう少し丁寧に書くと

構築している木がサイズで、次に番目の頂点を付ける時に、
- サイズ $i$ の連結成分を作りたい場合は、現在親となっている頂点のさらに親に $i+1$ 番目の頂点を置く。
- サイズ $i$ の連結成分を作りたくないときは、現在親となっている頂点の子として $i+1$ 番目の頂点を置く。

このように構成することができます。以下は「1, 3, 6, ...」が作れる木の例です。

f:id:betrue12:20180930124619p:plain

ACコード

（C++）Submission #3296518 - AtCoder Regular Contest 103

さいごに

Dの満点解法、2進数よりも45度回転の発想のほうが難しいかなと個人的には思いました。さっさと部分点だけ獲得したのは、結果的には正解でした。

木の問題はけっこう好きなので、Eは速く解けたかなと思います。Fも好きなタイプの問題だったので、本番で通せるようになりたい…

2018-09-24

Codeforces Round #512 参加記録＆解説（Div1 A, B）

Codeforces プログラミング競技プログラミング

Dashboard - Codeforces Round #512 (Div. 1, based on Technocup 2019 Elimination Round 1) - Codeforces

結果は355位で、レートが結構下がってしまいました…

f:id:betrue12:20180924113227p:plain

Div1のAとBを振り返ります。Div2ではDとEに対応しています。

A. Vasya and Triangle

Problem - A - Codeforces

問題概要

正整数 $n, m, k$ が与えられる。 $xy$ 平面上の $0 \le x \le n$ かつ $0 \le y \le m$ の領域内に格子点3つを取り、それらを結んだ三角形の面積が $\frac{nm}{k}$ となるようにせよ。またはそれが不可能であることを判定せよ。

制約

$1 \le n, m \le 10^{9}$
$2 \le k \le 10^{9}$

本番はかなり面倒な構成方法をした挙げ句にシステスで落ちましたが…簡単な構成方法があります。

格子点のみを頂点とする多角形の面積に関して、「ピックの定理」というものがあります。この定理から、このような多角形の面積は必ず $\frac{1}{2}$ の整数倍になります。

$\frac{nm}{k}$ が $\frac{1}{2}$ の整数倍でなければならないので、 $2nm$ が $k$ で割り切れない場合、答えは NO となります。以降、割り切れる場合を考えます。

仮に $(0, 0), (n, 0), (0, m)$ の3点をとった場合、その面積は $\frac{nm}{2}$ です。作りたい面積はその $\frac{2}{k}$ 倍です。先程「 $2nm$ が $k$ で割り切れる」という条件を調べたので、 $k$ の素因数は2を除いて $n, m$ どちらかの素因数になっています。このことから、以下のように考えることができます。

$k$ が2で割り切れる場合、まず $k$ を2で割って $k^{\prime} = \frac{k}{2}$ とする。その後 $k^{\prime}$ の素因数を、 $n$ または $m$ の割れる方から割っていく。
$k$ が2で割り切れない場合、先に $k^{\prime}$ の素因数を、 $n$ または $m$ の割れる方から割っていく。その後 $n, m$ のうち、素因数で1回以上割ったほうをどちらか選んで2倍する。（素因数で1回以上割ると値が $\frac{1}{2}$ 倍以下になるので、2倍することで $n, m$ が元の値よりも大きくなることはない）

このようにして小さくした $n, m$ で3点 $(0, 0), (n, 0), (0, m)$ を取り三角形を構成すると、作りたい面積が実現できます。

ACコード

（C++）Submission #43341268 - Codeforces

B. Vasya and Good Sequences

Problem - B - Codeforces

問題概要

長さ $n$ の数列 $a_{1}, ..., a_{n}$ が与えられる。この数列の連続部分列のうち、以下を満たすものの個数を求めよ。

「要素を1つ選び、その2進数表記におけるビット2箇所を選んで入れ替える」という操作を好きなだけ行うことで、数列全体のXORを0にできる。

制約

$1 \le n \le 3\times 10^{5}$
$1 \le a_{i} \le 10^{18}$

解法

これも本番はかなり面倒なしゃくとりを書いていて、何とか通ったからまだいいのですが、シンプルな解法で解説してみます。

「「要素を1つ選び、その2進数表記におけるビット2箇所を選んで入れ替える」という操作を好きなだけ行うことで、数列全体のXORを0にできる」まずはこの条件を言い換えてみます。1要素内で好きなだけビットを入れ換えられるので、ビットの位置は気にしなくて良いでしょう。区間内の各要素のビットの個数を考えたときに、以下の2つが満たされていればよいです。

ビットの個数の総和が偶数である。
1つの要素が、ビット総数の過半数を持っていない。

f:id:betrue12:20180924125238p:plain

「ビット総数が偶数となる区間」だけであれば累積和で簡単に求められますが、2番目の条件が厄介です。

ここで、1つの要素が持つビット数の範囲を考えます。 $1 \le a_{i} \le 10^{18}$ という制約から、まず下限は1個です。そして2進数で1を60個並べた数がおよそ $1.15 \times 10^{18}$ で制約を超えてしまうことから、上限は59個です。上限もさることながら下限が1というのも効いていて、例えばビット数59個の要素があっても、それ以外に要素が59個あれば絶対に過半数を占めることはありません。

このことから、過半数の条件を真面目に考えなければいけないのは長さ59以下の区間だけで、それ以上の区間は累積和を使えばよいことが分かります。これなら高速です。

解法をまとめると、

各要素のビット数を数える。
ビット数の累積和と、累積和の偶奇ごとの個数を数える。
左端を固定する。左端から長さ59以下の区間は、区間和と区間内の最大値を計算して真面目に条件判定する。
それ以降は累積和の差分を取って高速に計算する。

これで解けます。

※公式解説とほぼ同じですが、公式解説では累積和の条件だけで全区間を足してしまった後、過半数の条件に違反するものを引き算するという方法になっています。どちらでもよいです。

※実装上は、よほど制限時間が厳しくない限り59というギリギリを攻める必要はなくて、「60くらい」と考えて長さ65くらいまで真面目に条件判定する実装をしてもよいですし、そちらのほうが安全です。

ACコード

（C++）Codeforces

さいごに

どちらも、無駄に難しい解法に走って失敗してしまった回でした。そしてDiv1の人々はやっぱり強いです…Bを300人以上が通しているとは。厳しい戦場です。

2018-09-24

ABC110 参加記録＆解説

AtCoder プログラミング競技プログラミング

AtCoder Beginner Contest 110 - AtCoder

もはや参加記録というより解説メインになっているので、今回からタイトルに「解説」って付けます。

結果は20分台全完で11位。1桁順位の壁は厚い。

f:id:betrue12:20180924005239p:plain

A - Maximize the Formula

解法

作れる式の形は xy+z または x+yz しかなく、どちらも「10の位の数字が1つ、1の位の数字が2つ」という構成になっています。入力のうち一番大きいものを10の位に割り当てると最大になります。

ACコード

（Ruby）Submission #3249599 - AtCoder Beginner Contest 110

B - 1 Dimensional World's Tale

解法

「 $X$ と $x_{1}, ..., x_{N}$ 」が左に、「 $Y$ と $y_{1}, ..., y_{m}$ 」が右にキレイに分かれればよいです。 $X$ 側の最大値 $X_{\max}$ と $Y$ 側の最小値 $Y_{\min}$ を出して、 $X_{\max} \lt Y_{\min}$ であれば No War です。

ACコード

Submission #3250414 - AtCoder Beginner Contest 110

C - String Transformation

解法

「2つのアルファベットを選んで入れ替える」という操作を繰り返すと、どのようなことが起こるでしょうか。

「aをbに、bをaに置き換える」という操作を行うと、元文字列の a は b に、 b は a になる。
その状態からさらに「bをcに、cをbに置き換える」という操作を行うと、元文字列の a は c に、b は a に、c は b になる。

このように繰り返していくと、26文字のアルファベットが、それを1対1の対応で置換されたものに置き換わります。ここで言う「1対1対応」は数学用語には「全単射」というものですが、このレベルの問題であれば直観的な「1対1対応する」のイメージを持っていれば十分です。つまり、

同じ文字が異なる文字に変換されない。
異なる文字が同じ文字に変換されない。

の両方が満たされていれば Yes です。

実装においては、変換をmapなどで管理して $S, T$ の文字を順番に調べていき、同じ文字なのに前と違う変換先になっていれば1の理由で No 。最後に変換先の文字を全部調べて重複があれば2の理由で No とすればよいです。他に、 $S \to T$ と $T \to S$ の両方について1だけを調べる、という方法もあります。

ACコード

（Ruby）Submission #3252530 - AtCoder Beginner Contest 110

D - Factorization

Submission #3253308 - AtCoder Beginner Contest 110

解法

$a_{1} \times a_{2} \times \cdots \times a_{N} = M$ が成り立つということは、 $a_{1}, ..., a_{N}$ は $M$ の素因数を分配したものになっています。含まれる素因数が異なれば必ず値は異なるので（素因数分解の一意性、ですね）、この問題は「素因数の分配の仕方は何通りあるか？」と言い換えることができます。また素因数それぞれについての分け方は独立なので、全部の素因数について分配の仕方を考えて、それを全て掛け算すればよいです。

f:id:betrue12:20180924015211p:plain

ある素因数を $p$ とし、それが $M$ に $k$ 個含まれているとします。求めたいのは「 $a_{1}, ..., a_{N}$ に、 $k$ 個の区別されない要素を分配する方法は何通りあるか？」ですが、これは「重複組合せ」と呼ばれるもので、結果は $_{N-1+k}C_{k}$ になります（リンク先に、「なぜそうなるのか？」を丸と仕切りを用いて解説した記載もあるので見てみてください）。これを全て掛け算すると答えになります。