「みんなのプロコン 2018」決勝 A - Uncommon
問題概要
個の異なる整数
と整数
が与えられる。
以上
以下のそれぞれの整数
について、
のうち
と互いに素であるものの個数を求めよ。
制約
解法
ある数 について、
のうち
と互いに素であるものの個数を求めるとき、愚直に1つずつ試して
でやると全体で
となりTLEする。
よって、互いに素であるものをまとめて計算することを考える。
6と互いに素なものは2の倍数でも3の倍数でもないものであるということを考えると、 と互いに素であるものは、
の約数の倍数を全体から引いたものであると考えられる。
前計算として、
f[ ] :=
のうち
の倍数であるものの個数
を求めてあげることで、包除原理を使って と互いに素であるものの個数は高速に求めることができる。
Codeforces Round 498(Div.3) E. Military Problem
問題概要
頂点の根付き木が与えられる。根は1である。
ある頂点が命令を与えられると、自分の子のうちまだ命令が与えられていない1つの頂点（複数あれば頂点番号が最も小さい頂点）に命令を与える。命令が葉まで伝搬すると、自分の子のうちまだ命令が与えられていない1つの頂点（複数あれば頂点番号が最も小さい頂点）に命令を与えることを繰り返す。
個のクエリが与えられる。
番目のクエリでは頂点
に命令を与えた時に
番目に命令が伝えられる頂点を答える。
制約
解法
事前に頂点0からDFSをして、命令が伝わる順番を計算しておく。このとき、ある頂点に命令が伝わる順番を記録しておくことによって、各クエリにで答えることができる。
全体の計算量は
Codeforces Round 498(Div.3) D. Two Strings Swaps
問題概要
長さ の2つの文字列a,bが与えられる。文字列はともに小文字のアルファベットから構成される。
はじめに、好きな回数だけ以下の置換操作を行うことができる。
となる
を一つ選び、
を任意のアルファベットに置換する
その後、以下の3つの操作を繰り返して文字列a,bを等しくしたい。
を入れ替える
を入れ替える
と
を入れ替える
最初の置換操作の回数の最小値を求めよ。
制約
解法
の3つの操作をすることによって、{,
,
,
}を自由に入れ替えることができる。
また、 のとき、{
,
,
,
}と{
,
,
,
}は独立している。
よって、について置換操作の回数を計算して足し合わせればよい。
{,
,
,
}の4つの文字が全て等しければ置換操作はしなくてよい。
また、{,
,
,
}に2つの等しい文字が含まれているときも置換操作はしなくてよい。
そうでないとき、と
の片方だけを置換すればいいか、両方とも置換する必要があるかを調べればよい。
[追記:解法が一部間違っていたので訂正しました]
Codeforces Round 498(Div.3) C. Three Parts of the Array
Codeforces Round 498(Div.3) A Adjacent Replacements
問題概要
長さ の数列Aが与えられる。
次の操作を順番に行う。
- 数列Aに出現する
を全て
に置き換える
- 数列Aに出現する
- 数列Aに出現する
を全て
に置き換える
- 数列Aに出現する
- 数列Aに出現する
を全て
に置き換える
- 数列Aに出現する
- …
- 数列Aに出現する
を全て
に置き換える
- 数列Aに出現する
すべての操作が終わった後の数列Aを答えよ。
解法
が奇数だった場合,
になった直後の操作で
に戻る。
が偶数の場合は
になった後は何も変化しない。
よって, が偶数の場合のみ1を引く。
AGC019 C Fountain Walk
問題概要
東西方向と南北方向にそれぞれ本の道路があり、となりあう道路間の距離は
メートルである。すべての東西方向の道路はすべての南北方向の道路と直交し、すべての交差点は、交差する南北方向の通りの番号を
、東西方向の通りの番号を
として組 (
,
) で表される。
個の噴水があり、
番目の噴水は交差点(
,
)に設置されている。
噴水がある交差点には、交差点を中心とした半径 メートルの円が噴水の外周として描かれており、その内部に道路はない。
交差点(,
)から交差点(
,
)に移動するのに歩く最短距離を求めよ。
制約
のとき
のとき
交差点(,
) , (
,
) は異なり、どちらも噴水は設置されていない
解法
交差点で曲がるときは、噴水のある交差点で曲がる方が歩く距離は短くすむ。
交差点で曲がらない場合は噴水がない方が距離は短くすむ。
よって、(,
) から (
,
)に向かうときに、できるだけ噴水のある交差点を通りながら曲がりたい気持ちになる。
このとき、経由する噴水の数を最大化すると最短距離となるので、噴水の最大の数を求めたい。
簡単のため、(,
) が左下、 (
,
)が右上にあるとすると、右方向と上方向の移動だけ考えればよい。
よって最短距離に関係のある噴水は、(,
) を左下、 (
,
)を右上とする長方形領域に含まれる噴水のみである。
長方形の左下から右上に移動する際に経由できる噴水に最大数は、噴水の座標の集合をx座標でソートして、y座標でLISを求めてあげるとよい。（制約よりx座標やy座標が等しくなる噴水は存在しないので、特別な処理はいらない）
よって、噴水がない場合の(,
) から (
,
) への最短距離から、LIS の数だけ噴水を経由する距離を引いてあげ得ると答えがでる。（
または
で、長方形領域（実際は直線）に噴水が含まれる場合に注意する）
LISを求めるのは でできるので、全体の計算量は
となる。
