ARC-C
面白かった！！ 問題へのリンク 問題概要 人がいて、それぞれ正直者であるか、嘘つきであるかのいずれかである。また、各人は混乱していないか、混乱しているかのいずれかである。 混乱していない正直者は、常に正しいことをいう 混乱している正直者は、常に…
この時代、この手の Greedy はたくさんあったのね！ 問題へのリンク 問題概要 長さ の数列 が与えられる。「数列の要素を 1 つ選び、+1 するか、-1 する」という操作を行うことで、次の状態を達成したい。ただし、 とする。 すべての に対して、 である すべ…
集計処理の応用問題 問題へのリンク 問題概要 一般に、文字列 からいくつかの文字を抜き出して、それを並び替えることによって文字列 を作れるとき、 から を作れるという。 英小文字からなる 個の文字列 が与えられる。 のいずれからも作れる文字列 のうち…
少し考察が必要になる問題。結局隙間なく作れる。 問題へのリンク 問題概要 最初、黒板に 0 という数が書かれている。 秒後には、黒板に書かれた数 を以下のいずれかに置き換えることができる。 黒板に書かれた数を にできるのは最短で何秒後か？ 制約 考え…
この時代多く見られた「グルーピング」の問題！ 問題へのリンク 問題概要 S 型ピース 1 個と c 型ピース 2 個を使って、下図のように Scc を 1 個作ることができる。 また、c 型ピース 2 個を使って S 型ピース 1 個を作ることもできる。 今、S 型ピースが …
ちょっとした算数の問題！ 問題へのリンク 問題概要 サイコロを転がしていく。サイコロの上の目の値を足していく。 その総和が 以上となるまでの最小回数を求めよ。 制約 考えたこと 6, 5, 6, 5, ... と繰り返していくのが最適である。それを求めるために、…
今の時代だとあまり見かけないタイプの数学ゲー問題。 問題へのリンク 問題概要 人 を一列に並べる方法のうち、次の条件をすべて満たすものの個数を 1000000007 で割った余りを求めよ。 人 について、左側にいる人数と右側にいる人数の差が に等しい 制約 考…
綺麗な言葉で条件を言い換えよう！ 問題へのリンク 問題概要 一列に白色碁石と黒色碁石が合計 個並んでいる。 左右のいずれかに白色碁石と黒色碁石を置いていく。このとき、オセロのルールに基づいて石の色がひっくり返る。 すべての色を同色にするのに必要…
問題文の理解が大変かもしれない 問題へのリンク 問題概要（意訳） 2 つの正の整数 を次のように 回更新していく。最初、 である。 回目の更新では 2 つの互いに素な正の整数 が与えられるので、 を満たすような 2 つの正の整数 を 1 つ求めて、 をそれぞれ …
素因数分解を上手に活用しよう！ 問題へのリンク 問題概要 正の整数 が与えられる。 の正の約数の個数を 1000000007 で割った余りを求めよ。 制約 考えたこと 「約数の個数」をまともに考察する場合には、素因数分解が役にたつことが多い。一般に正の整数 が…
とても教育的な Greedy 問題！ 問題へのリンク 問題概要 個の非負整数からなる数列 が与えられる。この数列に対して、 「正の整数である要素を 1 つ選び、-1 する」 という操作を繰り返すことで、どの隣接する 2 個の要素の和も 以下となるようにしたい。 こ…
これは面白かった。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすものの個数を 998244353 で割った余りを求めよ。 について、 である 制約 考えたこと グラフの問題として考えることにした。つまり、0-indexed で表現すると 頂点数 、…
コンテスト中には通しきれなかった。流石に疲れていて頭が働かなかった......これはメモ代わりに記す。 問題へのリンク 問題概要 整数値 が等確率で出てくるルーレットがある。 先手と後手が交互にルーレットを回す すべての整数値が揃ったら終了である すで…
備忘録として。解説よりもおそらく面倒な DP をした。 問題へのリンク 問題概要 考えたこと 基本的に木 DP のノリで考えることにした。 根を 1 つとったとき、異なる部分木間で交換される頂点はただだか 1 個以内である。そこで次の DP をした。 dp[v][k] ← …
今の時代なら確実に灰色 diff ですね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。 頂点 と頂点 とを結ぶ辺は存在しないことがわかっている。 ある頂点 から 2 本の辺を辿ることで頂点 に到達できるかどうかを判定せよ。 制約 …
単純な全探索で解ける！ 累積和で高速化したり DP したりしても OK 問題へのリンク 問題概要 のマス目があり、上から 行目、左から 列目のマスをマス と表すことにする。マス には 個のアメが置かれている。 あなたははじめ、左上のマス にいる。 右方向ま…
ABS (AtCoder Beginner Selection) の 9 問目に選んだ問題！ 問題へのリンク 問題概要 英子文字からなる長さ の文字列 が与えられます。 をいくつかの連続する文字列に分割して、かつそれらの文字列がすべて "dream", "dreamer", "erase", "eraser" のいずれ…
とても教育的かつ典型的な貪欲法の問題ですね。 問題へのリンク 問題概要 二次元平面上に、赤い点と青い点が 個ずつあります。 個目の赤い点の座標は であり、 個目の青い点の座標は です。 赤い点と青い点は、 座標と 座標がともに赤い点よりも青い点の方が…
面白かった。リハビリになった。 問題へのリンク 問題概要 長さ の "B", "W", "R" からなる文字列が与えられます。これに対して、次の操作を 回繰り返して、最終的に得られる文字 (1 文字) を答えよ。 それぞれの隣り合う 2 文字に対して それらが同じ文字な…
これ茶色はさすがにびっくりした！ 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…
lower_bound の練習に！！！ あと、「3 つのものを考えるときは、真ん中を固定して考える」という考え方の典型。 問題へのリンク 問題概要 3 つの数列 (長さ ) が与えられる。各数列から要素 を選ぶ方法のうち、 を満たすものの個数を求めよ。 制約 考えたこ…
「転倒数 = N-1 で Yes とする」という嘘解法が大量に通ったらしい 問題へのリンク 問題概要 の順列 が与えられる。 と を swap する と を swap する ... と を swap する という 種類の操作を、それぞれちょうど 1 回ずつ行う必要がある。その結果がソート…
DP でやったけど、もっと楽にできたみたい 問題へのリンク 問題概要 長さ の文字列 と、正の整数 が与えられる。 人がジャンケンのトーナメント戦を行う。 は "R", "P", "S" のみからなる文字列で、"R" はグー、"P" はパー、"S" はチョキを表す。 (0-indexed…
誤読したーーーーー 問題へのリンク 問題概要 頂点数 、辺数 の連結な無向グラフが与えられる (多重辺はありうるが、自己ループはない)。各辺には色がついていて、色は 以上 以下の整数値で与えられる。 各頂点に 以上 以下の色を割り振りたい。このとき、「…
面白かった 問題へのリンク 問題概要 の行列 と、整数 が与えられる。この行列は、 をちょうど一つずつ要素に含む。 sigma くんは、以下の 2 種類の操作を、好きな順序で 好きな回数 行えます。 全ての について を満たす を選び、行列の 列目をswapする 全…
本当にただ全探索するだけ！！！ でも意外とこういうのが思いつかれにくいかもしれない。 問題へのリンク 問題概要 (意訳) 長さ の整数列 が与えられる。今、整数 を 1 つ選ぶ。そして整数列をすべて に書き換える。それに要するコストは で与えられる。適切…
記念すべき新体制 AtCoder になってからの初の rated ABC の C 問題！！！ 問題のリンク 問題概要 以上の整数のうち、 種類の数値 のいずれも含まない最小のものを求めよ。 制約 考えたこと 真っ先に思い浮かぶ方法は、単純に と順々に試していって「 をいず…
面白かった 問題へのリンク 問題概要 以下の条件を満たすような 個の区間 ( 番目を とする) を構築したい。 はすべて互いに相異なる整数 これらの区間の中から「どの 2 個も交差しないように最大で何個の区間を選べるか」という問題に対して、高橋君と青木君…
難しかった 問題へのリンク 問題概要 体重が であるような 体のラクダがいる。ラクダを一列に並べる方法のうち、次の条件を満たすものについて、左端のラクダと右端のラクダの距離として考えられる最小値を求めよ。また、そのようにラクダを並べることが不可…
コーナーケースがえぐい！！ 僕は最初、(1, -1), (-1, 3) で Yes を返してしまっていた。 問題へのリンク 問題概要 個の区間 があって、 両端の座標は のいずれか 両端の座標をかき集めたとき、重複がない 区間 と区間 がもし重なっているならば、区間 の長…
