gyouzasushi’s diary

競プロとか

近況

今週(広義)解いたAtCoderの問題たちです(黄diff以上)

AGC055 B - ABC Supremacy 🟨

(問題文)
状態 S に操作を施して状態 T にできますか?みたいな問題、(逆操作が存在する場合は )「S, T に操作を施して同じ状態 X にできますか?」と言い換えると見通しが良くなりがちな気がする。
これを念頭に操作を観察していると xABC を ABCx に変換できることに気づくので、ABCABCABCxx...xx みたいなやつを共通のゴール X に据えると解けそう→AC。
解説「f(S) が well-defined であることは明らかではありません。」→失礼しました…
(提出)

ARC057 B - 高橋君ゲーム 🧪🟨

(問題文)
N 日間で K以下ゲームに勝った場合の答えは簡単なDPで求まる。
勝ち数が増えたからと言うて機嫌のいい日が増えるとは限らない(例:サンプル2)のが悩ましいところやけど、そうなるのは \sum a = K なときだけだと思う(勘)ので解けた。
(提出)

ABC129 F - Takahashi's Basics in Education and Learning 🟧

(問題文)
愚直に計算すると O(L) とかになるけど、平方分割の要領で \sqrt L 項ずつ計算していくと O(\sqrt L) になった。
しかし  L \leq 10^{18} なのでまだ微妙。そこでもう一度同じ要領で高速化すると、なぜか O(L^{1/3}) になって通った。
そんなはずはないと思うので、どこかが二度手間ザウルスやったんやろなあ。
(提出)

ABC128 F - Frog Jump 🟧

(問題文)
A-BA を割り切るとき、戻ってきた先に蓮がなくて溺れうるので注意する。
ある x があって 2x+1 回目のジャンプでぴったりゴールしなきゃだめなので、 x(A-B) + A =N-1 が必要。
A, A-B を全探索する。(A,A-B) の組として考えられる個数は 1 から N-1 の約数の個数の和で抑えられて、これはまあ許せる個数そう。
→ あとは各 A-B でシミュレーションしていけば解けそう。
最後のシミュレーションが間に合うか諸説あるところやけど、小さい A-B の場合を前計算しておいたら通った。
(提出)

ABC135 F - Strings of Eternity 🟨

(問題文)
文字列の一致判定が高速にできると、グラフの最長パス?を求める問題に落ちるので解ける。
非本質なはずのグラフパートで無限に手こずってしまって悲しい。
以下学び

  • DAG の最長パスはトポロジカルソートからのDPで簡単に求まる。
  • トポロジカルソートに失敗すればDAGじゃない→サイクルがある。

今回はサイクルがあれば答えは必ず \infty なので、これで解けた。
(提出)

ABC226 F - Score of Permutations 🟨

(問題文)
まず問題文がちょっと難しくて困った…。
要するに、各 d について「\mathfrak{S}_n の元 \sigma のうち位数 d のものはいくつか?」が知りたい(たぶん)。そして \sigma の位数はその巡回置換型から簡単に計算できる(長さの LCM をとればOK)ところ、巡回置換型のパターン数は十分少ない(N の分割数で、N=50 のとき 204226 通り)。ので、解けた!
代数学入門入門が役に立って嬉しいね😊
(提出)

おまけ

AtCoder 黄色に戻ってきました!ぎりぎりで草。
f:id:gyouzasushi:20211108000547p:plain
とりあえず黄色を維持できるようにがんばる。