Educational Codeforces Round 54
A. Minimizing the String
問題概要
長さ の文字列 s が与えられる。1文字削除して辞書順最小の s' を出力せよ。
制約
考え方
辞書順最小の文字列を求めるには、前から順番に辞書順最小の文字列で構成していくことになります。よって なる
が存在した場合は
を除くことで辞書順最小が達成されます。
Submission #45970471 - Codeforces
B. Divisor Subtraction
問題概要
以下の操作をするとき、操作の回数を求めよ。
操作
ならば操作を終了する。そうでなければ
の最小の素因数
をもとめ、
から
を引く
制約
考え方
一度 が偶数になった場合はその後は常に
が最小の素因数になるため、
を引き続けることになります。よって
が奇数の場合は最小の素因数
を求め
をし、残りの数を
で割った回数が解となります。
Submission #45970778 - Codeforces
C. Meme Problem
問題概要
かつ
を満たすような
を求めよ。誤差は
まで許容される。クエリが
個与えられるのでそれぞれに答えよ。
制約
考え方
二分探索なのかと思いきや、2次方程式の解を求めることに帰着します。解の公式 に代入して解が求まりますが、判別式
となる場合は解なしのため
N
と出力します。
Submission #45971338 - Codeforces
D. Edge Deletion
問題概要
頂点の
本の辺をもつ重み付き無向木が与えられる。
から各頂点
への最短経路を
とする。
今、多くとも 本の辺が残るようにして、いくつかの辺を削除したい。削除したときに
から
への最短経路が
に一致する場合は
は良い頂点という。良い頂点を最大化するように辺を削除せよ。
制約
考え方
頂点 からの各頂点への最短経路は Dijkstra法で求めることができます。そのとき頂点
から各頂点への最短経路木を求めておけば、
から
辺たどることができる木が求める辺の集合となります。
Dijkstra法は各頂点の更新は高々 回なので、ある頂点を更新したときに使用した辺は最短経路木に必要な辺になります。このようにすると最短経路木に必要な辺の集合が求めることができるので、そのうち
個を出力すればよいです。