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

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

操作がEuclidの互除法に対応

AtCoder ARC 050 C - LCM 111 (試験管黄色)

レピュニット数を題材とした問題。 問題へのリンク 問題概要 を 個並べた数と、 を 個並べた数の最小公倍数を で割ったあまりを求めよ。 制約 考えたこと を並べた数をレピュニット数とよぶ。数学的に面白い性質が色々ある。 レピュニット数の最大公約数は、…

AtCoder ARC 105 B - MAX-=min (灰色, 300 点)

操作が「Euclid の互除法」っぽくなっている系の問題!!!そういう系の問題は次の一覧で示してる drken1215.hatenablog.com 問題へのリンク 問題概要 個の正の整数 に対して次の操作を繰り返し行う。 個の整数の最大値を 、最小値を とする。 なら手続きを…

AtCoder AGC 018 A - Getting Difference (緑色, 300 点)

操作の仕方が Euclid の互除法そのものになっているタイプの問題。 問題へのリンク 問題概要 要素数 の数列 が与えられる。これに対して以下の操作を好きな回数だけ行うことができる: 整数を 2 つ選び、その差の絶対値をとり、それを数列に新たに挿入する 整…

Codeforces Round #201 (Div. 1) A. Alice and Bob (R1600)

シンプルで楽しい感じ 問題へのリンク 問題概要 要素からなる数列 がある (互いに相異なる)。交互に以下の操作を行う 数列から 2 つの整数を選んで、その差を数列の末尾に追加する ただし、「その差の値」がすでに数列中に含まれる場合は、この操作を行うこ…

AtCoder AGC 001 B - Mysterious Light (500 点)

Euclid の互除法な操作過程をたっぷりと味わえる味わい深い問題。 問題へのリンク 問題概要 一辺の長さが の正三角形の図のような の地点からビームを発射する。このとき、既にビームが通ったところは新たに壁になる。ビームは必ず元の場所に戻ることが証明…

AtCoder ABC 118 C - Monsters Battle Royale (茶色, 300 点)

教育的!!! 問題へのリンク 問題概要 個の正の整数 が与えられる。今、以下の操作を好きな回数だけ行う。 個から 2 つの正の整数 () を選んで、 を で置き換える この操作を行うと、最終的には 個の と 1 個の正の整数が残る。残る整数の最小値を求めよ。 …

QUPC 2018 I - Buffalo

楽しいけど重くて、重いけど楽しい 問題へのリンク 問題概要 要素から成る数列 が与えられる。 個から 2 個選んでできる 通りのペア のうち、以下の条件を満たすものを数え上げよ。 容量が の容器を用意して、以下の操作によって水の量 を汲み取れる 操作 1:…

AtCoder AGC 026 B - rng_10s (青色, 600 点)

あーーーーーー、これは大好物系なん!!!!! 本番でやってみたかったん!!!!! 問題へのリンク 問題概要 (AGC 026 B) 整数 があたえられる。 最初は在庫に 個あって、 毎日 個ずつ消費される その日の最後に 個以下しか残っていなかったら 個補充され…