茶色diff
これ難しいと思った！ あと、どうやら (1, 1, 1, 6) を 3 回にする嘘解法が AC になったらしい 問題へのリンク 問題概要 以下の動きのできる駒がある。駒をマス からマス へ移動させるのに必要な手数の最小値を求めよ。 制約 考えたこと まず、スタートとゴ…
いかに上手に実装するか！ 問題へのリンク 問題概要 長さ の ">" と "<" のみかななる文字列 が与えられる。 長さ の非負整数列 は， すべての について次の条件をみたすとき、良い非負整数列と呼ぶ。 = "<" のとき： = ">" のとき： 良い非負整数列の要素の…
区間分割して考える系、AGC-A にめちゃくちゃ多いね 問題へのリンク 問題概要 文字列 が与えられる。 を 回繰り返してできる文字列を とする。 の文字をひとつ選んで他の文字に書き換える操作を繰り返すことで T のどの隣り合う 2 文字も相異なるようにする…
面白かった。でも茶色ってことは流石になさそう......(コンテスト中は、全部の XOR 和が 0 かどうかを判定する、という嘘解法が AC になっていたらしい) 問題へのリンク 問題概要 個の非負整数 が与えられる。これらを円環状に上手に並べることで、 「どの整…
場合分けやコーナーケース回避がエグい問題！ 問題へのリンク 問題概要 .#..#.. のような長さ のマス目が与えられる。"#" は岩を表す。初期状態では、すぬけ君は マス目に、ふぬけ君は マス目にいる ()。 今、「2 人のうちのいずれかを選んで 1 マス右か 2 …
ある程度探索でゴリ押した。 問題へのリンク 問題概要 英小文字のみからなり、どの 2 文字も互いに相異なる文字列を「多彩」であると呼ぶこととする。多彩な文字列 が与えられる。以下の条件を満たす文字列の中で最も辞書順が小さいものを求めよ。 よりも辞…
整数 を 8 で割ったあまりは、 の下三桁を 8 で割ったあまりに等しい！ 問題へのリンク 問題概要 整数 が長さ の文字列として与えられる ( は '1'〜'9' のみで構成される)。 の各文字を並び替えてできる整数の中に、8 の倍数となるものが存在するかどうかを…
半分全列挙した！ 問題へのリンク 問題概要 正の整数 と整数 が与えられる。以下の条件を満たす正の整数 の組の個数を求めよ。 制約 考えたこと 愚直な方法としては、次のように 4 重ループをする解法が考えられるかもしれない。しかしこれでは の計算量を要…
本当にただ全探索するだけ！！！ でも意外とこういうのが思いつかれにくいかもしれない。 問題へのリンク 問題概要 (意訳) 長さ の整数列 が与えられる。今、整数 を 1 つ選ぶ。そして整数列をすべて に書き換える。それに要するコストは で与えられる。適切…
問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。各頂点 には値 が書かれている。以下の操作を好きな順序で好きな回数だけ行うことで、各頂点 の数値が であるような状態にすることが可能かどうかを判定せよ。 辺 を選んで、以下のいずれ…
2 種類の操作がある系の問題！こういうのは操作の手順を単純化して考えられる場合が多い 問題へのリンク 問題概要 正の整数 が与えられる。これに対して以下の 2 種類の操作のいずれかを繰り返し行なっていく を 倍する に を足す が 以上となってはならない…
Union-Find の典型的な問題！！ でも、DFS や BFS でも解くことができる。 問題へのリンク 問題概要 人 から 人 までの 人の人がいます。 「人 と人 は友達である」という情報が 個与えられます。同じ情報が複数回与えられることもあります。 と が友達、か…
包除原理！！！C 問題としては難しめですね。 問題へのリンク 問題概要 0 以上 9 以下の整数値からなる長さ の数列 であって、 数列中に 0 が含まれる 数列中に 9 が含まれる という条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 制約 考え…
Zero-Sum Ranges だった！！！ 問題へのリンク # 問題概要 'A', 'G', 'C', 'T' からなる文字列 が相補的であるとは、 を並び替えてできる文字列 が存在して、 T[ i ] = 'A' ならば T'[ i ] = 'T' T[ i ] = 'T' ならば T'[ i ] = 'A' T[ i ] = 'G' ならば T'[…
Union-Find の練習問題という雰囲気ながら、DFS や BFS でも解ける 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。これに最小本数の辺を追加することで全体が連結となるようにしたい。その最小本数を求めよ。 制約 考えたこと 全体…
ちょっと場合分けが怖い問題だけど、最後の動きは「ちょうどゴールにならないと、上がれないすごろく」を思い出すと納得できそう！ 問題へのリンク 問題概要 現在、座標 にいる。以下のいずれかの操作をちょうど 回行う。 座標 にいるとき、 に移動する 座標…
XOR について完全理解することが求められる...！ 問題へのリンク 問題概要 を偶数とする。 個の 0 以上の整数 であって、以下の条件を満たすものを求めよ。 個の整数のうち 番目を除外した 個の整数の XOR 和が となる 制約 考えたこと が偶数というのが不気…
これは、、、桁和を求めるタイプの問題の応用ではある 問題へのリンク 問題概要 数値を文字列に置き換える。ただしそのルールは 1,2,⋯,26 は、その順に a, b, ..., z 27,28,29,⋯,701,702 は、その順に aa, ab, ac, ..., zy, zz 703,704,705,⋯,18277,18278 は…
差分更新を上手にやっていくという、とても教育的な問題！！！ そして、よく似た類題として、以下の問題がある！！ atcoder.jp 今回の問題へのリンク 問題概要 個の整数 が与えられる。以下の 回のクエリに答えよ。 各クエリでは 2 つの整数 が与えられる 数…
一瞬ヤバそうに見えるけど、落ち着いて考えると、 くらいまで調べればいいという 問題へのリンク 問題概要 正の整数 が与えられるので、 を満たす整数 を一つ求めよ。 制約 考えたこと こういうの、基本的には全探索。でも という制約を見ると、 あたりまで…
回操作した後の結果を求めよ (ただし がめちゃくちゃ大きい) という問題は、 同じ処理の繰り返しとなっているところを見抜く ダブリングする というパターンが多いと思われる。 問題へのリンク 問題概要 個の町 がある。町 からは、町 へテレポートできる。…
久しぶりに素因数分解する問題が来た！！！！！！！！！！！ 問題へのリンク 問題概要 正の整数 に対して、以下の操作を何回行うことができるか、その最大回数を求めよ。なお、素数 と正の整数 を用いて の形で表すことのできる整数を「素数べき」と呼ぶこと…
誤差は怖い！！！！！！！ 問題へのリンク 問題概要 整数 と、"x.yz" のフォーマットで与えられる実数 が与えられる。 の小数点以下を切り捨て、結果を整数として出力せよ。 制約 考えたこと 数値誤差が怖いというテーマの問題は、パナソニックコンでもあっ…
気づけば一発系。ただし、数式の見た目がエグく見えてしまうかもしれない... 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数 に対する - の値の最大値を求めよ。 制約 考えたこと 全探索すれば だけど、それでは間に合わない。さて、式の…
これかーーー数学ゲーじゃないかと物議を醸した問題。でも普通にいい問題だと思う！！ 問題へのリンク 問題概要 底面が一辺 cm の正方形であり、高さが cm であるような直方体型の水筒に、体積 cm3 の水を入れる。 底面の正方形の一辺を軸として、この水筒を…
ちょっと問題を理解するのが大変かもしれない 問題へのリンク 問題概要 ロボットと 回ジャンケンをする。ロボットの出す手はあらかじめすべてわかっている。 グーを出して勝つと 点 チョキを出して勝つと 点 パーを出して勝つと 点 が得られる。ただし 回目…
落ち着いて頭を整理。。。 問題へのリンク 問題概要 'R', 'G', 'B' のみからなる長さ の文字列 が与えられる。 の index の組 であって、 と と はすべて互いに異なる である という条件を満たすものの個数を求めよ。 制約 考えたこと 頭がごっちゃになりそ…
丁寧に簡潔に 問題へのリンク 問題概要 合計で グラム買いたい。 0.25 グラフで 円のセット 0.5 グラムで 円のセット 1 グラムで 円のセット 2 グラムで 円のセット がある。これらのセットを組み合わせて グラム買うための最小金額を求めよ。 考えたこと 0.…
差分更新系の教育的問題かな 問題へのリンク 問題概要 長さ の数列が与えらえる。各 index k に対して、 数列から k 番目の要素を除いたものについて その中から異なる 2 つの要素を選ぶ方法であって (順番は問わず) その 2 つの要素の選び方が等しい という…
先頭と末尾の両方から push できるデータ構造といえば、deque！！！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個の操作を行ってできる文字列を出力せよ type 1： 文字列 を左右反転する type 2： 値 F と文字 c が与えられ、F = 1 のと…
