けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

操作:整数をreplaceしていく

AtCoder ARC 155 D - Avoid Coprime Game (赤色, 800 点)

モノグサ社内で同僚と一緒に解いた! 問題へのリンク 問題概要 要素からなる数列 が与えられる。各 に対して次の問に答えよ。 先手と後手が交互にプレイする。整数 を管理する。最初 である。 先手は初手は を選び、 と に更新し、数列からその整数は削除す…

AtCoder ABC 235 D - Multiply and Rotate (緑色, 400 点)

最小回数を求めるには BFS!!(素振り) 問題へのリンク 問題概要 黒板に整数値 が書かれています。次のいずれかの操作を最小回数繰り返すことによって、整数値 の値を にしたいとします。 を 倍して にする を十進法表記したときに、末尾の値を先頭に持って…

AtCoder ABC 077 D - Small Multiple (ARC 084 D) (橙色, 700 点)

これほどシンプルな問題がグラフ最短路問題になるのは感動的ですね! 問題へのリンク 問題概要 の正の倍数をすべて考えたときの、各桁の和として考えられる最小値を求めてください。 制約 うまく数字を並べるゲームと捉える の倍数をひたすら試す方法をまず…

AOJ 3189 Mod Rush (HUPC 2020 day3-E)

これ好き!楽しい!! 問題へのリンク 問題概要 長さ の数列 で定義される、全 ステップの操作が与えられる。操作は整数 に対して行うものであり、 回目の操作は次のものである: を % で置き換える 個の整数 それぞれに対して ステップの操作を行って得られ…

AtCoder ABC 179 E - Sequence Sum (緑色, 500 点)

この手の 周期性を利用する ダブリングする のどちらでも解けるタイプの問題、最近めっちゃ多いね。 問題へのリンク 問題概要 を で割ったあまりを で表す。 整数 が与えられる。以下で定まる漸化式の最初の 項の総和を求めよ。 制約 考えたこと 最初誤読し…

AtCoder ABC 175 C - Walking Takahashi (茶色, 300 点)

ちょっと場合分けが怖い問題だけど、最後の動きは「ちょうどゴールにならないと、上がれないすごろく」を思い出すと納得できそう! 問題へのリンク 問題概要 現在、座標 にいる。以下のいずれかの操作をちょうど 回行う。 座標 にいるとき、 に移動する 座標…

AtCoder ABC 169 D - Div Game (茶色, 400 点)

久しぶりに素因数分解する問題が来た!!!!!!!!!!! 問題へのリンク 問題概要 正の整数 に対して、以下の操作を何回行うことができるか、その最大回数を求めよ。なお、素数 と正の整数 を用いて の形で表すことのできる整数を「素数べき」と呼ぶこと…

Judge System Update Test Contest 202004 D - Calculating GCD (400 点)

面白かった 問題へのリンク 問題概要 要素からなる正の整数列 が与えられる。以下の 個のクエリに答えよ 各クエリは整数 が与えられる の順に、 という更新を行う 初めて となる瞬間の を求めよ 最終結果が 1 より大きいときは、その値を答えよ 制約 解法 (1…

AtCoder ABC 161 C - Replacing Integer (灰色, 300 点)

これは問題文がいかめしいけど、ちょくだいさんのこのツイートが全てかなと思う! C問題、数学の問題といえばそうなんだけど、「無限に長いすごろくがあります。ゴールまでの距離がxです。Kマスずつ進めますが、ゴールを通り過ぎてしまう場合は折り返します…

AtCoder ABC 161 F - Division or Substraction (水色, 600 点)

めちゃくちゃ面白かった!!! 問題へのリンク 問題概要 整数 が与えられる。以下の条件を満たす 以上 以下の整数 の個数を求めよ。 整数 を用いて、 に対して操作を行っていく が で割り切れるならば を で置き換えて、そうでない場合には を に置き換える…

AtCoder ABC 126 C - Dice and Coin (茶色, 300 点)

確率を確実に 問題へのリンク 問題概要 正の整数 が与えられる。 最初に の整数値をランダムに出力する。以降コインを振って 表が出たら整数値を 2 倍する ( 以上になったら「勝ち」でゲーム終了) 裏が出たら整数値を 0 にする (こうなった時点で「負け」で…

AtCoder AGC 008 A - Simple Calculator (茶色, 300 点)

もれなく正確に解くための考え方とかが問われる感じ。 問題へのリンク 問題概要 整数 が与えられる。 に以下のいずれかの操作を最小回数行って に一致させよ: を 1 増やす を にする 解法 最適解は 最初に反転する (かしないか) 「1 増やす」を繰り返す 最後…