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

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

yukicoder

yukicoder No.2422 regisys?

めっちゃいい Greedy 問題だった!! 問題へのリンク 問題概要 個の商品があり、 番目の商品は、一般客は 円で購入でき、MMA 部員は 円で購入できる。なお、MMA 部員が一般客と比べて得できる商品もあれ得て、損する商品もあり得る。 人がいて、 人目は「一…

yukicoder No.2423 Merge Stones

ビットベクターで高速化するのは、いつも見落としてしまう! 問題へのリンク 問題概要 円環状に 個の魔法石があり、 番目の魔法石は、価値が 、色が である。色は 1 以上 50 以下の整数で表される。 今、これらの魔法石に対して、隣り合う魔法石の色の差が …

yukicoder No.2417 Div Count

整数の入門にいい感じの問題! 問題へのリンク 問題概要 正の整数 と非負整数 が与えられる。次の条件を満たす正の整数 の個数を求めよ。 を で割った余りが である 制約 解法 を で割ったときの商を とおくと、 と表せる。これを式変形すると となる。この…

yukicoder No.2410 Nine Numbers

平衡三進法! 問題へのリンク 問題概要 次の条件を満たすサイズ 9 の整数列 を求めよ。 である 以上 以下の任意の整数 に対して、次の操作を繰り返す操作列が存在して、整数列中に整数 が存在する状態にできる 操作 1:数列から 2 つの要素 を選び、その 2 …

yukicoder No.269 見栄っ張りの募金活動

分割数で鮮やかに解ける! 問題へのリンク 問題概要 人のクラスで総額 円を集めることにした。 このクラスの生徒は皆見栄っ張りであり、出席番号順が1つ前の生徒に比べて 円以上高い金額を寄付しないと気が済まない。 この条件を満たす方法の個数を 1000000…

yukicoder No.2066 Simple Math !

floor sum のいい感じの練習問題! 問題へのリンク 問題概要 正整数 が与えられる。 非負整数 を用いて という形で表せる正の整数のうち、 番目に小さいものを求めよ。 ( 個の入力ケースが与えられる) 制約 考えたこと いかにも二分探索という問題。次の判定…

yukicoder No.2032 Let's Write Multiples!!

floor sum の練習! 問題へのリンク 問題概要 以上 以下の の倍数をすべて十進表記で 1 回ずつ書き出した時、数字 が書かれる回数を求めよ。 (テストケースが 個与えられる) 制約 考えたこと 各桁ごとに考える。整数 の右から 桁めが である条件は を で割っ…

yukicoder No.763 Noelちゃんと木遊び

いわゆる「木上の最大安定集合問題」です! 超典型問題です。 問題へのリンク 問題概要 頂点数 の木が与えられます。木からいくつかの頂点を選んで削除します。その結果、木はいくつかの連結成分に分かれます。 分かれた連結成分の個数の最大値を求めてくだ…

yukicoder No.931 Multiplicative Convolution

原始根 + NTT 問題へのリンク 問題概要 素数 と、数列 、 が与えられる。 各整数 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 添字積 convolution はできるのかと一瞬戸惑う。しかし が素数であることに着目すると、原始根 を介…

yukicoder No.843 Triple Primes

エラトステネスの篩の練習問題に良さそう 問題へのリンク 問題概要 以上 以下の素数の組 であって、 を満たすものの個数を求めよ。 制約 考えたこと のときは明らかにダメ。 また、偶数かつ素数である整数は 2 のみであることに注意する。 がともに奇数とす…

yukicoder No.226 0-1パズル

ずっと前にこれを作問して出題していたので記録を。 時は流れて AGC 026 D - Histogram Coloring でよく似た設定の問題が出たときはビックリした (実際はそんなに似てない)。 問題へのリンク 問題概要 のグリッドが与えられる。各マスは '0', '1', '?' のい…

yukicoder No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)

(x - a)(x - b) ... (x - z) みたいなやつの計算 問題へのリンク 問題概要 個の箱がある。箱 には色 のボールが入っている。以下の 個のクエリに答えよ。 各クエリは 以下の整数 が与えられる 各箱から 個ずつボールを取り出す方法であって、取り出されたボ…

yukicoder No.1145 Sums of Powers

形式的冪級数すごい 問題へのリンク 問題概要 個の整数 が与えられる。各 に対して を 998244353 で割ったあまりを求めよ。 制約 考えたこと いっそ 次までではなく、無限級数にしてしまう。そして として、 の各次数の係数を求めたい。ここで、 と計算でき…

yukicoder No.3046 yukicoderの過去問

FPS の inv 関数が使える問題 問題へのリンク 問題概要 階段で一度に登れる段差が であるとする。ちょうど 段を登る方法が何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと として、 の 次の係数を求める問題となる。 の計算量でできる。…

yukicoder No.155 生放送とBGM

戻す DP シリーズのトレーニング 問題へのリンク 問題概要 (入力形式は多少改変) 正の整数 と、 個の正の整数 が与えられる。これらをランダムシャッフルする。 を満たす最小の を考える。この値の期待値を求めよ (要求精度は )。 制約 考えたこと 各要素 に…

yukicoder No.321 (P,Q)-サンタと街の子供たち

kirika さんの「整数論テクニック集」より。 問題へのリンク 問題概要 二次元平面平面上において から の合計 8 方向に移動できる。今、 個のクエリが与えられる。各クエリは座標 が与えられる。原点から出発して、上述の移動を好きな順序で好きな回数だけ繰…

yukicoder No.980 Fibonacci Convolution Hard (母関数)

すごい面白かった!!! 問題へのリンク 問題概要 整数 が与えらえたときに、漸化式 を満たす数列 が与えられる。これに対して以下の 個のクエリに答えよ: 1 つのクエリは 2 以上の整数 が指定され、 を満たすような正の整数 に対して、 の総和を求め、10000…

yukicoder No.979 Longest Divisor Sequence

LIS の亜種だけど、雰囲気違って面白い! 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。この部分列であって 狭義単調増加 後の index に出てくるやつは前の index にでてくるやつの倍数になっている という条件を満たすものの最長の長さを求め…

yukicoder No.974 最後の日までに

めちゃくちゃ面白い!!! 問題へのリンク 問題概要 (意訳) 思いを寄せている先輩に 週後に告白したいので、その日までに先輩の好感度を最大化しておきたいです。最初、「所持金」と「好感度」はともに 0 です。毎週、以下のいずれかの行動を起こすことがで…

yukicoder No.973 余興

Deque に似てる。けど、Deque と違って、先手と後手がとりうる選択肢は常に一緒 (最初、先手は左から、後手は右からと誤読した)。 問題へのリンク 問題概要 長さ の数列に対し、先手は左から順に、後手は右から順にとっていく。どのターンもとった値の合計値…

yukicoder No.972 選び方のスコア

すごく面白かった!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。ここから何個か選ぶ。選んだ値を としたとき、そのスコアを以下のように定義する。 選んだ値のメディアンを とする 奇数個の場合は真ん中の値 偶数個の場合は真ん中の 2 つの値の…

yukicoder No.968 引き算をして門松列(その3)

その 2 と雰囲気は似ているけど、一気に考えづらくなった! 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっている 以下のクエリに 回答…

yukicoder No.967 引き算をして門松列(その2)

ものすごく間違いやすい雰囲気だったので、探索候補を絞ってから力技で全探索した!!! 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっ…

yukicoder No.886 Direct

添字 GCD 畳み込みの練習に 問題へのリンク 問題概要 の格子点上の二点対であって、その二点を結ぶ線分上に格子点をもたないものが何個あるかを数え上げよ。(1000000007 で割ったあまりで) 制約 解法 1:添字 GCD 畳み込み この問題は、線分として 軸や 軸に…

yukicoder No.819 Enjapma game

好き! 確かに天才系問題だけど、実験を積み上げると見えて来る感じが最高!!! 問題へのリンク 問題概要 × の盤面に何個かのコマが置かれている。先手と後手が交互に、以下のいずれかの動作を繰り返す: コマを 1 つ選び、それを 1 マス左か下に動かす (た…

yukicoder No.140 みんなで旅行

スターリング数っぽい数え上げの練習 問題へのリンク 問題概要 組の夫婦がいて、合計で 人がいる。 人をいくつかのグループにわける方法のうち、各グループに夫婦が 組以上いるような場合の数を で割ったあまりを求めよ。 制約 考えたこと ひとまずグループ…

yukicoder No.391 CODING WAR

写像12相の 玉は区別する 箱も区別する 各箱の玉は 1 個以上 という場合の問題!!! 問題へのリンク 問題概要 個の互いに区別できる玉を、 個の互いに区別できる箱に入れる。 ただし、どの箱についても玉が 1 個以上入るようにするな方法が何通りあるか、10…

yukicoder No.184 たのしい排他的論理和(HARD)

何度も出題されて典型となった「XOR 和が K となる部分集合は何通りか」という問題の亜種。 連立方程式を解くのとはちょっと違う趣向の、でもランクを求める感じの問題。 問題へのリンク 問題概要 個の正の整数 が与えられる。これらのうちから何個か選んで …

yukicoder No.803 Very Limited Xor Subset

F2 線形代数大好き! 問題へのリンク 問題概要 個の整数 の部分集合を選んで XOR 和を にする方法のうち、 個の区間 [ ] () について 区間の中から選ぶ個数は偶数個か奇数個かが指定される という制約を満たすものが何通りあるか求めよ。 制約 考えたこと 実…

yukicoder No.801 エレベーター

累積和による DP 高速化のすごく面白い問題! 問題へのリンク 問題概要 階建てのビルに 個のエレベーターがあり、 番目のエレベーターは区間 [ ] の間を動いており、区間内の任意のフロアから任意のフロアへと移動することができる (同じフロアへの移動もエ…