2020-11-22

AtCoder Regular Contest 108参加記(～C問題)

300(1)-400-500-0-0-0で1ペナ3完1200点。

A - Sum and Product

$N+M=S$ を満たす正整数 $(N, M)$ の組は $S-1$ 個あり、これらの組全てに対して $N\times M = P$ かどうか判定すると、計算量 $O(S)$ で解ける。しかし今回は制約が $1\le S, P\le 10^{12}$ と厳しいので、もっと効率の良い解法が必要となる。

$N\times M = P$ を満たす正整数 $(N, M)$ の組は $P$ の約数の個数に等しい*1。また、問題文の条件が $N, M$ に対して対称なので、 $N\le M$ を仮定すれば $N\times M = P$ を満たす正整数 $N$ の最大値は $\sqrt{P}$ であることがわかる*2。よって、 $1\le N\le \sqrt{P}$ の範囲で $(N, M)$ の組を全探索し、 $N+M=S$ かを判定すると、計算量が改善され $O(\sqrt{P})$ となり、実行時間制限に間に合う。

$1\le N\le P$ の範囲で $(N, M)$ の組を全探索してしまい、TLEで1ペナ。

B - Abbreviate Fox

文字列中に部分文字列foxが存在していた場合、無条件に取り除いてよい（貪欲法）。これは、貪欲に取り除いてしまってもほかに取り除けるはずだった部分文字列foxの並びが崩壊することはない、ということからわかる。

実装時には注意が必要で、文字列を配列として扱うと一文字削除するごとに $O(|S|)$ の計算量がかかってしまう。これを解決するためにスタックを用いて実装する。スタックに文字列の先頭から順に1文字ずつ挿入していき、末尾の3文字がfoxになった瞬間にその3文字ごと削除する。こうすれば、挿入・削除ともに $O(1)$ で出来るため、全体の計算量が $O(|S|)$ となる。

C - Keep Graph Connected

まず、YesNo判定問題と考えて、構築できないときそのグラフはどのような特徴を持つか考えてみる。完全グラフ、スターグラフ、二部グラフ、頂点数が極端に少ないグラフ、多重辺を含むグラフなど、さまざまなグラフで実験してみると、この問題の制約下で構築できないグラフは存在しないことが見えてくる。

よってここからは、グラフの各頂点に整数を振るアルゴリズムを考えていく。与えられるグラフは連結であることが保証されているため、BFSなどを用いることで $N-1$ 本の辺からなる部分木を取得できる。以下に整数の振り方の例を示す。

f:id:mmnkblog:20201121234649j:plain — 構築例。＊は親とつながっている辺のラベル以外なら何でもよい

木なので、どれか一つでも辺が欠けると非連結になってしまう。辺が残る条件は「辺の両端にある頂点に書かれた数字のうちどちらか一方のみが辺のラベルと一致する」である。これを言い換えると、辺が消える条件は「『頂点に書かれた2つの数字が両方とも辺のラベルと異なる』もしくは『頂点に書かれた2つの数字が両方とも辺のラベルと一致する』」となる。この条件を満たさないように回避するイメージで頂点に整数を振っていきたい。木の根（始点）に振る数はなんでもよい（理由は後述）ので、今回は $1$ とする。根から葉にかけて整数を振っていく。

頂点に整数を振るアルゴリズムは以下のとおりである：

親ノードに振られた整数を $P$ 、親ノードとつながっている辺のラベルを $C$ とする。
$P=C$ なら、自ノードに振る整数を $C$ 以外の適当な数とする。
$P\neq C$ なら、自ノードに振る整数を $C$ とする。

$P=C$ のときに適当な整数を振っても、考えているグラフは木なので、影響があるのは子ノードだけ。よって問題なく動作する。根に振る整数が何でもいい理由も、同様に説明できる。

実装するとき、BFSで木を探しながら同時進行で整数を振るようにした。計算量は、 $O(N+M)$ 。

D - AB

解けなかった。数え上げの問題なのでもう少し時間を掛ければ解けそう。

感想

レートが上がってうれしいです

*1: $P$ の約数の一つを $A$ とすれば、 $N=A, M=P\div A$ として $(N, M)$ の組を構築できるからである。 $P\div A$ が割り切れることは $A$ が $P$ の約数であることからわかる。

*2: $N$ が最大となるのは $N=M$ のときで、 $N\times N = P$ より $N = \sqrt{P}$ がわかる。

2020-11-16

AtCoder Beginner Contest 183の解法・感想

競プロ解説参加記

ABCに出るのは久々でした。

100-200-300-400-500-0(2)で0ペナ5完1500点。

A - ReLU

問題文の通りの値を返す関数を実装する。入力された値によって出力される値が異なるので、条件分岐を用いて書けばよい。

計算量は、 $O(1)$ 。

B - Billiards

入試数学とかでよく見る考えで、「ある面で跳ね返る」というのは、「その面と対称な空間を考えたとき、面を跨いでその空間へ直線移動する」ことと同じである。

今回は始点と終点が決まっていて、反射するのは1回と決まっている。よって、例えば終点を $x$ 軸を対称軸として反転させた位置に設定すれば、「始点と移動後の終点を結んだ直線」と「 $x$ 軸」との交点を求める問題になる。

2直線の式が出ているので、方程式を解けば交点が求まる。「 $x$ 軸」と交わるというのは $y=0$ であることと等価なので、始点と終点を結んだ直線の式に $y=0$ を代入して $x$ を求めればよい。

計算量は、 $O(1)$ 。

C - Travel

制約より、どの2都市を選んでも移動可能である。都市 $1$ からすべての都市を通って戻ってくるようなルートの数は、都市 $2$ から都市 $N$ までの巡り方の数に等しく、 $(N-1)!$ 通りである。制約の最大値が $N=8$ であり、すべてのルートに対して移動時間を計算しても間に合いそうなので全探索する方針で実装する。

このように、その通り数が階乗で表されるような全探索を界隈では順列全探索と呼んだりする。実装の詳細は省く。長さが $N-1$ の順列を生成した後その各項の数を都市の番号と紐づけ、実際にかかる移動時間を計算する。

計算量は、 $O((N-1)!\times N)=O(N!)$ となり、実行時間制限に十分間に合う。

D - Water Heater

ある区間 $[S, T)$ が決まっていて、その区間内すべての要素に $P$ 足す…という処理を $N$ 回した数列が欲しい。ただ、愚直に実装すると計算量が $O(NT)$ となり間に合わないので、imos法を使って解く。アルゴリズムの詳細と実装方法の説明は省く。

imos法を用いることで、計算量を $O(N+T)$ に削減することができた。あとは、生成した数列の全ての項が $W$ を超えていないか愚直に判定すればよい。この処理自体は $O(T)$ で出来る。

全体の計算量は、 $O(N+T)$ 。

E - Queen on Grid

動的計画法で解けそうだが、遷移方法が複雑になりそうなので細かく分けて考える。

まず、横一列にマスがつながっている場合に、各マスに移動する方法がそれぞれ何通りになるのか考えてみる。最初のマスにはすでに駒が置かれているので $1$ 通りとして考えると、それぞれのマスに対する移動方法の通り数は以下の通りとなる。「あるマスより手前にあるマス」からならどのマスからでも移動可能なので、通り数はそのマスより前のマスの通り数の合計となる。

f:id:mmnkblog:20201116000600p:plain — 通り数を求めるには、赤の区間と青いマスの数値が必要

しかし、いちいちそれまでのマスの合計値を計算する方法だと、1つのマスを計算するのに $O(W)$ の計算量がかかってしまう。ここで、直前のマス（図の青の区間）とそれより前のマス（図の赤の区間）の合計が通り数となっていることがわかるので、この二つの情報を一つのマスにまとめて記憶させれば計算量は $O(1)$ となり高速になる。

これを、上方向・右上方向・右方向の3つについて考えれば、それぞれの解の合計値がそのマスへの移動方法の通り数となる。

f:id:mmnkblog:20201116000605p:plain

f:id:mmnkblog:20201116000612p:plain — H=3, W=5の場合の例（緑のマスが各マスの通り数）

あとはこの図を動的計画法に落とせば解ける。注意点として、壁のマスの場合、そのマスには遷移できないのですべての数値を $0$ にする。

計算量は、 $O(HW)$ 。

F - Confluence

ACコードを提出できなかった。以下に考察を残しておく。

集合を結合するクエリが存在する（しかも一度結合した集合がわかれることはない）ので、UnionFindを使って解けそうだと考える。ただし、もう一つのクエリである「生徒 $x$ が含まれる集合に含まれる生徒のうち、クラス $y$ に属する生徒の数を求める」のがやっかい。これを実現するために、各集合の親ノードに「どのクラスの生徒が何人いるか？」という情報を持たせるための辞書（map）を追加する。

しかし、これだと集合を結合するときに辞書データも結合しなければならず、毎回 $O(N)$ の計算量がかかるので、その集合に1人以上含まれるようなクラスだけ保持する集合（set）も親ノードに持たせることにして、結合時はその集合に含まれるクラスの情報だけを反映するようにした。こうすることで、いわゆるデータ構造をマージする一般的なテクと呼ばれるテクで、小さい方を大きい方にくっつけるようにすればならし計算量 $O(\log N)$ で結合できる…はず。

こうすれば計算量は $O(N + Q\log N)$ で（この計算量解析も怪しい）、問題が解けるはずだと考えたが、sample以外のテストケースでかなりWAが出ている~~ので嘘解法のような気がする…~~。

（追記）考察はあっていた。「生徒 $x$ が含まれる集合に含まれる生徒のうち、クラス $y$ に属する生徒の数を求める」クエリに答えるには、

生徒 $x$ が含まれる集合の根を取得する。 $O(\alpha (N))$
その根が持っている辞書データの中のクラス $y$ の値を取得する。 $O(\log N)$

という段階に分けられる。ここで、集合の根を取得するとき、UF内のメンバ関数root(x)を使うべきところを、同じくメンバ関数であるpar(x)と書いてしまっていた！root(x)は $x$ が含まれる集合の根（頂点）を返す関数であり、par(x)は $x$ の（一つ上の）親を返す関数である。あるノードの親が何になるかは実装により変わるので、基本的に外部からpar(x)を参照する必要はない。つまり、ただの実装ミスだった…。

（追追記）全然ちがーーーう！！！！！！
集合の根を取得するのはroot(x)という関数。par[x]は、今現在の $x$ の親を保存しているだけの配列。これを一緒くたにしてはいけない！！さらにいうと、root(x)が呼ばれたとき、par[x]の値が根の値に更新されるだけで、本当に親かどうかも外から見ただけではわからない。つまり、本当にpar[x]は外部から参照してはいけない！！！！！！！

parを外から弄るとバグの原因になるのでprivateにすると、よい！(無用なバグを防げるので(ぼくはprivateにしてないけど))
— 神崎 (@knzk_ate) November 15, 2020

嫁、ありがとう

感想

なんか全体的に簡単め？だった気がする。上位陣の全完スピードが異常だった。

2020-09-26

ACL Beginner Contestの感想

競プロ解説参加記

略称はABLらしい。明日から使えるムダ知識をあなたに

100-200-300(1)-0-0-0で1ペナ3完600点。

A - Repeat ACL

ACLという文字列を $K$ 回だけ出力する。 $K$ は5パターンしかないのでif文を用いて5通りの分岐を記述すると解ける。また、ループを用いると問題文の処理をそのまま実装できるので楽。

計算量は、 $O(K)$ 。

B - Integer Preference

$A$ 以上 $B$ 以下の範囲を $X$ 、 $C$ 以上 $D$ 以下の範囲を $Y$ と呼ぶことにする。

2人が好きな整数が存在するということは、範囲 $X$ と範囲 $Y$ が重なっているということ。ここで、①「範囲 $X$ の最大値が範囲 $Y$ の最大値より小さい」と仮定すると、範囲 $X$ の最大値が範囲 $Y$ の最小値より大きければ重なっていることがわかる（等しくても重なる）。これは入力の数値を用いて表現すると $C \le B$ で判定できる。もし①の条件を満たしていないなら $A$ と $C$ 、 $B$ と $D$ を入れ替えることで同様の判定式で判定できる。

計算量は、 $O(1)$ 。

f:id:mmnkblog:20200926233151p:plain — BよりDの方が大きいことを仮定した場合の範囲の重なり方

C - Connect Cities

都市を頂点、道路を辺と見たグラフを考える。1回の操作により、異なる2つの連結成分*1 を辺でつなぐことができる。初めの状態で連結成分が $X$ 個あるなら、この操作を $X-1$ 回行えば必ず連結成分が1個になるので、答えは $X-1$ である。

あとは連結成分の個数を数えられれば良い。これにはDFSを用いて全頂点を走査する方法や、UnionFindで頂点集合を管理する方法がある。今回はUnionFindを用いて実装した。

ACLでは、UnionFindという名前ではなく「DSU（Disjoint Set Union）」と呼ばれている。同じ集合に属するならばその集合の代表元も同じなので、setなどを用いて代表元の個数を数える。

計算量は、DFSを用いる方法で $O(N)$ 、UnionFindとsetを用いる方法で $O(N\log N)$ 。

D - Flat Subsequence

ここから解けなかったので簡潔に書く。

DP。単純に書くと遷移に $O(N^2)$ かかってしまうところを、セグ木を使うと $O(N\log N)$ で書ける。

E - Replace Digits

遅延セグ木を使うと $(Q\log N)$ で書ける。

F - Heights and Pairs

むずい

感想

水色なのに茶パフォとってしまったのでしばらく謹慎する

*1:無向グラフにおいて、辺でつながっている頂点のまとまりのこと

2020-09-26

実力もないのに数学力だけで水色に這い上がるな

※AtCoderとACLを非難する記事ではありません。

実力もないのに数学力だけで水色に這い上がって生きてきた僕は今回のABLで茶パフォを出しました。原因はACLに含まれているものを中心としたデータ構造の性質の理解と、その応用例に関する知識不足です。つまり僕が100%悪いです

克服するために少なくともACLのpracticeコンテストの問題全部通すまではコンテストに一切出ないことにします。精進する時間もとれなさそうなのでしばらくはコンテストに出ないと思います。

タイトルは自分を含めた競プロerに向けた警告です。数学力だけあってもだめです数学問が出ても周りは「数学問かよー」というだけで喜んでるのはお前だけですいいことは何一つないのでこれを読んでいる数学得意なまじめな人はコツコツ学んでコツコツレートをあげましょう

2020-09-20

AtCoder Beginner Contest 179の感想

競プロ解説参加記

「愚直にやると遅いから高速化する！」の考えは大事。

100-200(1)-300-400-500-0で1ペナ5完1500点。

A - Plural Form

文字列を複数形に変換する。文字列の末尾がsかそうでないかで処理が変わる。具体的な処理の流れとしては、入出力を除くと「文字列の末尾の文字を取得」「その文字がsかどうかを判定」「文字列の末尾に文字列を連結」の3つとなる。それぞれの処理の仕方がわからないときは素直にググるべし。

計算量は入出力がボトルネックで、 $O(|S|)$ 。

B - Go to Jail

各 $i$ に対して、サイコロの目がゾロ目かどうかを保存するboolean型の配列を用意する。この配列の中で、"true"が3個以上続いている箇所を調べたい。この判定は、「今"true"が何個続いているか？」という変数を用意して、前から順番に $i$ 番目と $i+1$ 番目の値を判定していくとできる。どちらも"true"なら変数の値を $1$ 増やし、そうでないなら変数を $0$ にする（ $0$ にするのを忘れて1ペナ）。変数の値を $0$ にする直前の値が連続でゾロ目が出た回数なので、この回数が1度でも $3$ 以上になったことがあるなら答えはYesとなる。

計算量は $O(N)$ 。

C - A x B + C

愚直に解くなら、 $1$ から $N$ までの範囲で $A, B, C$ を回して実際に計算するという方法がとれる。ただしこの方法だと計算量は $O(N^3)$ となりTLEしてしまうので、効率の良い別の解法を考える。

$N$ が固定されているので、他のもう1文字を固定して考えるとよさそうだと考える。どの文字を固定するかで解法が変わる。

$A$ を固定する場合

この場合、 $B$ を決めれば元の式を変形させることで $C = N - A \times B$ となり、 $C$ の値が1パターンに決まる。 $C$ の値は正でないといけないので、 $0 \lt C = N - A \times B$ である。変形すると $A \times B \lt N$ 、さらに変形すると $B \lt \frac{N}{A}$ となり、 $B$ の値も一意に決まることがわかる！（不等号を等号に直せば $B = \lfloor \frac{N-1}{A}\rfloor$ となる）
あとは $A$ に関するループを回して総和を取ればよい。計算量は、 $O(N)$ 。

$C$ を固定する場合

式変形すると $AB = N-C$ となるので、 $N-C$ の約数がいくつあるかを数えたい。ある整数に対して約数の個数を求めるのには $O(\sqrt{N})$ の計算量がかかるので、全体では $O(N\sqrt{N})$ の計算量となり、このままだと間に合わない可能性が高い。ここで、 $N-C$ の値は $1$ から $N-1$ まで連続した値をとるという特徴を利用すると、約数の個数の総和を計算量 $O(N\log N)$ で高速に計算することができる。やり方を書こうと思ったけどうまく書けなかったので、これは読者への課題とする…（ググって）
全体の計算量ももちろん $O(N\log N)$ 。

どちらの方法でもすぐ通せるようならかなり強いと思う。今回は $A$ を固定する方法で通した。

D - Leaping Tak

$dp[i]$ := マス $i$ まで移動する通り数
という風な1次元の動的計画法を考えたいが、移動方法は最大でN通りあるため、普通に書くと計算量が $O(N^2)$ となりTLEする。（公式解説を見ると、実は $O(N\log N)$ でも解けるらしい？）

現在見ているマスを $i$ とすると、入力が区間で与えられることから移動先となりうるマスはある程度固まっていることがわかるので、これを利用する。先ほどの配列dpのほかにもう一つの配列aを用意して、区間の始まりである $a[i+L]$ に $dp[i]$ を足し、区間の終わりである $a[i+R]$ に $dp[i]$ を引く。こうすることで、配列 $a$ に対して累積和を前から実行でき、マス $i$ まで見たときの $a[i]$ はまさにマス $i$ までの遷移方法の通り数となる。

計算量は、 $O(NK)$ 。

E - Sequence Sum

愚直に計算すると $O(N)$ だが、制約が大きいためTLEとなる。より高速な解法を考える。

数列 $A$ の各項はすべて $M$ で割った余りであるので、各項の値は $0$ 以上 $M$ 未満である。さらに数列 $A$ はひとつ前の項に対する漸化式によって定義されているため、同じ値が2回以上登場するなら、そこから周期的にループする。ここで鳩ノ巣原理より、第 $(M+1)$ 項までに値が重複するので、「第 $1$ 項から周期に乗るまでの総和」＋「周期を繰り返した回数× $1$ 周期の項の総和」＋「 $1$ 周できなかった分の余りの総和」が答えとなる。これを求めるには、周期の長さと $1$ 周期の総和がわかればよい。

計算量は、 $O(M)$ 。

ちなみにダブリングというテクニックでも解けるらしいがそちらの方はわかりません。一般に、周期に注目して解ける問題はダブリングでも解ける、は正しそうだけど、どうだろうか。

F - Simplified Reversi

解けなかった。愚直に石を置き換える解法だと、空間計算量の時点ですでに $O(N^2)$ かかるため現実的ではない。黒い石で構成された長方形領域を考えるとき、操作を加えても分割される長方形は高々1つだけで、すべてのクエリが終わっても領域の個数は $N$ 個ほどしかないな、ということには気づいた。これを使ってうまく解けないか悩んでいたがここでタイムアップ。この発想はかなり近いところまで行ってたようで、例えば縦のラインに白い石が置かれたとき、それより右側の黒い石が置き換えられるのは縦に置くようなクエリが飛んできた時だけなので、そのような列（同様に行も）をメモしておけばよかったっぽい。

終了時のTwitterのTLを見た限りでは、遅延セグ木で解いている人が多そうだった。遅延セグ木がわからないのでもっと精進します。

感想

D問題に少し時間をかけてしまったがしっかり5完できたのはよかった。

2020-09-13

AtCoder Beginner Contest 178の感想

競プロ解説参加記

具合が悪いのでさらっと書きます

100-200-0-400-0(3)-0でノーペナ3完700点。

A - Not

1なら0を、0なら1を出力する。if文で実装できるし、排他的論理和でエレガントに書くこともできる。 $O(1)$

B - Product Max

全通り試すと間に合わない。（B問題にしては厳しいね？）
負の数×負の数＝正の数　だったりするので場合分けをしようか迷うが、よく考えると範囲の最大値・最小値の組み合わせをすべて試せばそのどれかが最大値となる。
$\max (ac, ad, bc, bd)$ が答え。 $O(1)$

C - Ubiquity

考えられる数列の総数は $10^N$ 通り。0を使わない数列は $(10-1)^N$ 通り。9を使わない数列は $(10-1)^N$ 通り。0も9も使わない数列は $(10-2)^N$ 通り。
実はこれらの数値が求められれば、あとは包除原理で導出できる。 $10^N-2\times 9^N+8^N$ が答え。 $O(N)$

D - Redistribution

dpで解いた。
dp[i][j] := 数列の長さがiで、その総和がj
とする。遷移を簡単にするために、数列に0以上の整数、つまり3未満の数も含んでいいことにする代わり、答えを求めるときは数列の全要素に3を足したものとしてみる。
遷移は、dp[i+1][j] = dp[i][j] + dp[i][j-1] + ... + dp[i][0]となる。実装時は累積和を使って右辺を $O(1)$ で求める。
dp[i][S - 3 * i]の総和が答え。 $O(S^2)$

E - Dist Max

（追記：誤答の内容について）木の直径を求める感じで、「ある適当な点から一番遠い点」から一番遠い点までの距離を出力したがWAだった。2点間の距離は木ではなくグラフである。

Googleによると、45度回転させてマンハッタン距離をチェビシェフ距離に変換して軸ごとに見ると解けるらしい。やったことがないので解けませんでした。
ちなみに前にも45度回転させて考える問題を解けなかったので大反省。

F - Contrast

なんかAGCのA問題に出てきそうな問題。ちゃんと考えれば、元からソートされているのだから、Bを逆順にすれば $A_i=B_i$ となるような数字は高々1種類しかないので、その時に数字の位置をずらせるかどうかだけ考えればよいっぽい。
細かいところまでは詰めてないので穴があるかもしれません。

感想

寝不足は敵

2020-08-30

AtCoder Beginner Contest 177の解説・感想

競プロ解説参加記

100-200-300-400-500(1)-0で1ペナ5完1500点。

A - Don't be late

先週も同じような問題文見たな...（既視感）

2つの解法を紹介する。どちらも、「問題文で与えられたすべての変数を同時に見ない」のが特徴的。

解法1： $T$ 分後の待ち合わせ時刻に間に合うためには、どれだけの速さで移動すればいいか計算する。 $D$ メートルを $T$ 分で移動したい、つまり、 $1$ 分間で $\frac{D}{T}$ メートル移動したい。つまり、分速 $\frac{D}{T}$ メートル（以上）の速さで歩ければ待ち合わせ時刻に間に合わせることができる。ここで、高橋君は分速 $S$ メートルで歩けるので、 $\frac{D}{T} \le S$ なら間に合うことがわかる。

解法2：分速 $S$ メートルで歩けるので、待ち合わせ時刻までの $T$ 分間では $S\times T$ メートルまで移動することができる。ここで、待ち合わせ地点までは $D$ メートルあるので、 $D \le S\times T$ なら間に合うことがわかる。

どちらの解法も、最終的に同じ不等式が導出されていることがわかる。ただし解法1の不等式では整数同士の割り算が登場しており、切り捨ての処理などが発生すると正しい答えが得られない可能性があるので、「答えを小数で出す」「両辺に同じ数をかけて割り算を掛け算に直す」などの処理をした方が安心！

計算量は、 $O(1)$ 。

B - Substring

むずくないか？

文字列 $S$ の長さを $S.len()$ 、文字列 $T$ の長さを $T.len()$ とする。

文字列 $S$ のどこの文字をどんな文字に変更すれば最適なのかを調べたい。ここで、 $S$ の何文字目から $T$ と一致するのかを全探索する。 $1\le j\le S.len() - T.len() + 1$ を満たす $j$ に対して、 $S$ の $j$ 文字目からの $T.len()$ 文字を $T$ と一致させたい。逆に言えば、この $T.len()$ 文字以外の文字はどんな文字でも関係ない！ $1\le i\le T.len()$ を満たす $i$ に対して、 $S$ の $(j+i)$ 文字目と $T$ の $i$ 文字目が異なっている箇所が何か所あるか数えて、異なっている箇所が一番少なくなるような $j$ を選べばよい！（説明がむずい！）
聞かれているのは「何文字変えるか？」である。 $S$ と $T$ で異なっている箇所だけ変えればよく、その個数は先ほど数えたものそのままなので、それを出力すればよい。
計算量は、 $O(S.len()\times T.len())$ 。

C - Sum of product of pairs

計算量について学べる良い数学問。

問題文の通りに実装すると、計算量が $O(N^2)$ となり、実行時間制限に間に合わない（TLE）。なので、計算方法を工夫する必要がある。

$i\lt j$ であり、 $A_j$ とかけられる数は $A_1, A_2, \dots , A_{j-1}$ の $(j-1)$ 個ある。これらの総和は、分配則を用いると $A_j(A_1 + A_2 + \dots + A_{j-1})$ となる。このうち、 $A_1 + A_2 + \dots + A_{j-1}$ の部分は $j$ から $(j+1)$ に増えるとき $A_j$ だけ増えるので、 $j$ についてのループを前から回していけば計算することができる。この場合の計算量は、 $O(N)$ となり、高速に計算できるのでACとなる！

ちなみに、 $Sum = (全てのA_iの合計)$ として、 $((Sum - A_i) \times A_i)$ の総和を2で割ることでも答えを求められる（九九の表みたいなのをイメージするとわかりやすい）。

D - Friends

すぐ解けたのでよかった（小並感）

「人」を頂点、「人と人が友達であること」を辺と見ると、グラフの構造に落とし込める。さらに、友達の友達は友達であるという条件より、友達同士の人を集めた集合がいくつかできることもわかる。このような集合がいくつかあるN人をグループに分けるとき、同じグループに友達同士の人がいないようにするには、同じ友達同士の集合から2人以上選ばないようにすると良い。つまり、最大 $P$ 人の友達集合があるなら、少なくとも $P$ 個のグループを作ってそこに1人ずつ振り分ける必要がある。逆に、友達ではない関係の人は同じグループに何人いても問題ないので、 $P$ がいくつか求められれば良い！

友達同士の集合を構成するには、例えばUnionFindというデータ構造を用いると上手くいく。UnionFindでは、2頂点を連結したり、ある頂点がどの集合に属するかを調べたりするのをとても高速に行うことができる。入力を受け取る過程で集合を作り、その集合の要素数の最大数を求めればよい。計算量は、およそ $O(N)$ *1。

ほかにも、幅優先探索で連結成分を調べると同様に解ける。

E - Coprime

提出前にコーナーケースを確かめず1ペナしてしまった…。

この問題は、「pairwise coprimeであるか」「setwise coprimeであるか」の2種類の判定問題を解くことができれば正解となる。

2種類のうち、「setwise coprimeであるか」は比較的簡単に求められる。3つ以上の正の整数に対して、最大公約数を求める関数を $gcd()$ とすると、この関数は結合則が成り立つ。つまり、 $gcd(A_1, gcd(A_2, gcd(A_3, \dots)))$ という風に2組の最大公約数を順に求めていけば $N$ 個の数の最大公約数が求まる。このパートの計算量は、2数の最大公約数の計算に $O(\log A_i)$ かかるので、全体で $O(N \log A_i)$ となる。

残った「pairwise coprimeであるか」について。もしpairwise coprimeでないなら、共通する素因数が1つ以上存在するはずである。それぞれの数を素因数分解して素因数を調べることで、共通する素因数があるかどうかがわかる。一つの数を素因数分解するのに $O(\sqrt A_i)$ かかるので、全体で $O(N\sqrt A_i)$ となり、制約よりおよそ $10^9$ 回の計算が必要となるが、 $A_i$ 以下の素数の個数を $\pi(A_i)$ とすると、素数定理より $\pi(A_i) \fallingdotseq \frac{A_i}{\log A_i}$ と表せるあるため、鳩ノ巣原理より素因数が被った時点で探索を打ち切れば計算量はおよそ $O(\frac{A_i\sqrt A_i}{\log A_i})$ となる。この計算量の式に制約の最大値を代入して計算するとおよそ $5\times 10^7$ 回の計算となり、十分高速に計算できる。