黄色diff
お 見た目とても面白そう 問題へのリンク 問題概要 要素からなる数列 があたえられる。各要素を「赤」「緑」「青」の三色のいずれかに塗る方法のうち、各色の合計値を として三辺の長さが となるような三角形が存在するようなものを数え上げよ。998244353 で…
こういうのを得意になるぞー！！！ でも AtCoder でこういうデータ構造をしっかり準備する必要がある系は珍しい気がする。 問題へのリンク 問題概要 個のマス () があって、マス上に 個の区間がある。 各 に対して、 と移動したときに何個の区間を踏むかを答…
コンテスト中に真剣に考えて解けなかった 700 点問題！！！ 問題へのリンク 問題概要 個の整数 があたえられる。 個の整数の部分和は空集合に対応するものを除くと 個ある。 このうちの中央値を求めよ。 制約 考えたこと とりあえず部分和問題みたいなことを…
駅メモ！駅メモ！駅メモ！！！！！ 問題へのリンク 問題概要 座標平面上に 個の頂点がある。各頂点の座標は で与えられる。 原点を中心とする半径 の円内の点をランダムに選び、与えられた 個の点の中から最も近い距離にある点へと移動する。 各点について、…
楽しい問題だった！！！ 問題へのリンク 問題概要 すぬけ君は黒板と 個の整数からなる集合 を持っています。すぬけ君は黒板に整数 を書いたのち、以下の操作を 回行います。 から要素を 1 つ選んで取り除く。 その後、現在黒板に書かれた数を 、 から取り除…
見るからにコーナーケースが怖い... atcoder.jp 問題概要 頂点 本の辺からなる単純かつ連結な無向グラフが与えられます。 全ての辺をちょうど一回ずつ使って つのサーキットを作ることが可能かどうかを判定してください。 制約 考えたこと 輪っかを 3 つ作る…
証明はできるし、その証明に基づいた構成を数学的に与えることまではできるけど、それを実装に落とすのがすごく大変な問題。。。 問題へのリンク 問題概要 整数 が与えられます。 の順列 であって、 次の条件をすべて満たすものが存在するかどうか判定してく…
21:01 発の磐越西線 (会津若松 -> 郡山) に乗りながらのコンテスト参戦だった。 元々コンテスト出ないで問題だけ読んで考察だけ楽しむつもりが、この F がスラッと解けたので思わず提出してしまった。この段階ではまだ電波状態が大丈夫だった...のと、やはり…
ダブルカウントに気をつければ難しくない。現代なら 700 点かもしれない... 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数からなる無限数列 のうち 任意の について であるとき、 から連続する 個は同じ値である を満たすものの個数を 1…
これは。。。C より先に確実にこれをとったのはよかった 問題へのリンク 問題概要 (意訳) H × W の二次元グリッドがあって、各マスは通路か壁である。壁は N 個ある。最初は (1, 1) に駒がある。 毎ターン (x, y) にある駒は (x + 1, y) に進める、ここで (x…
弱かった。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 文字列の列 であって の文字数が である 辞書式順序で < < < を満たすもののうち、登場文字数の最小値を求めよ。 制約 考えたこと が狭義単調増加だったら、"a" の個数だけで行けるので…
実装は手こずったものの、それなりに自信のある Greedy を提出できて一発 AC できてよかった 問題へのリンク 問題概要 1 〜 の値を 個ずつもつ長さ の数列であって、 各 について、 番目の値が 個目の である という条件を満たすものを 1 つ構築せよ。条件を…
これがインフレ！？ABC 110 D - Factorization に瓜二つ 問題へのリンク 問題概要 整数 を 個の整数の積として表す方法が何通りあるかを、1000000007 で割ったあまりを求めよ。 制約 考えたこと ほとんど、ABC 110 D - Factorization と一緒。 だが、マイナ…
こういう系の問題、なかなか提出が怖くなるやつ。こういうのは背水の陣状態じゃないと躊躇してしまいそう... 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。 どの頂点から出る辺数も 1 どの頂点から出発しても必ずノード 1 (root) にた…
部分列 DP の考え方を試せる問題 問題へのリンク 問題概要 文字列 A が与えられる。 A の部分文字列とはならないような文字列 (英小文字のみ) のうち、最短の長さのものを求めよ。 複数考えられる場合にはそのうち辞書順最小のものを求めよ。 制約 1 <= |A| …
桁ごとに考えるしかなさそうなのはそれはそう... 問題へのリンク 問題概要 (ARC 092 D / ABC 091 D) 要素の数列 と が与えられる。 個の整数 の XOR 和を求めよ。 制約 < 解法 XOR 和と言われた時点で、各桁ごとにカウントしたい気持ちにはなる。 個の整数の…
「 番目の値を求めよ」「メディアンを求めよ」といった問題では、二分探索法が有効なことが多々ありますね。 問題へのリンク 問題概要 長さ の数列 が与えられます。 この数列の連続する区間として考えられるものは 個あります。そのそれぞれの区間について…
高速ゼータ変換の練習第二弾！ 問題へのリンク 問題概要 長さ の整数列 があります。 を満たすすべての整数 について、以下の問題を解け: を < , を満たす整数とするとき、 の最大値を求めよ。 制約 考えたこと 個の要素を一斉に変換する何かをさせている感…
いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たい。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷似) POJ 3692 Kindergarten (補グラフとって二部グ…
完全に冷静さを欠いたし、ハマった。。。 ARC 099 D - Snuke Numbers 問題概要 (ARC 099 D / ABC 101 D) 正の整数 N に対してその 10 進法での桁の和を f(N) で表す。今、正の整数 N がすぬけ数であるとは、任意の N より大きい正の整数 M に対して f(N) / N …
slack 勉強会で 600 点の DP として話題になってやってみたん。 DP 自体は素朴だけど、計算量解析含めると 700 点でもいい気はする。 Grouping 問題へのリンク 問題概要 (ARC 067 E) 人をグループ分けしたい。 人は互いに区別される。 どのグループの人数も …
600 にしちゃムズイ。 ARC 097 E Sorted and Sorted 問題概要 (白, 1), (白, 2), ..., (白, N), (黒, 1), (黒, 2), ..., (黒, N) の 2N 個の要素の順列が与えられる。「隣同士を swap する」を最小回数行うことで、「白」についても「黒」についてもソートさ…
コンテスト本番における 僕のコード: https://beta.atcoder.jp/contests/agc025/submissions/2612210 tourist のコード: https://beta.atcoder.jp/contests/agc025/submissions/2609185 解けたとはいえ、反省点も多い感じですね。。。 問題へのリンク 問題概…
はじめに 昨年末 DEGwer さんの数え上げテクニック集 がとても勉強になる資料として話題になりました。その中の P. 9 の「4. 条件の言い換え」のところに、「必要条件を列挙したらそれが十分条件だった」がありました。 こないだの APC 001 E - Antennas…
