AtCoder500点
一瞬、「更新がある」「種類数」ということで、Wavelet Matrix が必要かとびびった 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個のクエリに答えよ タイプ 1： の 文字目を に変更する タイプ 2： の区間 に含まれる文字の種類数を答える …
DP しなくても間に合うけど、桁 DP 的な考え方が役に立つ！ 問題へのリンク 問題概要 100 桁以下の整数 が与えられる。 以上 以下の整数であって、十進法表記で 0 以外の数値がちょうど 個であるようなものが何個あるのかを求めよ。 制約 の桁数 考えたこと …
面白かったけど、実際に実装するのは辛かった。 問題へのリンク 問題概要 のグリッドが与えられる。各マスを 2 または 5 で埋めたい。ただし以下の条件を満たすようにしたい。 2 が書かれたマスだけに着目し、上下左右斜め に隣接するマス同士に辺を張ったグ…
個数制限なしナップサック！！！！！！！ 問題へのリンク 問題概要 種類の魔法を駆使して、HP が のモンスターを倒したい。 番目の魔法は、魔力を だけ消費して、モンスターの HP を だけ減らすことができる モンスターの HP を 0 以下にするのに消費する魔…
すごく面白かった！ 問題へのリンク 問題概要 ある数値が与えられる。ただしその数値は非常に桁数が大きいことがあるので、数値を 10 進法で表したときの文字列をランレングス圧縮した状態で与えられる。具体的には 組の値 が与えられて、 の順に、数値 が …
「〜の最小値を求めてください」「ただし 1000000007 で割ったあまりで」 ...この設定の歪さを見ると、不思議な気持ちになる 問題へのリンク 問題概要 個の正の整数 が与えられる。 以下の条件を満たす正の整数列 をすべて考えたときの、 の最小値を求めよ (…
こういう系の「個別要素に分解して考える」という問題が三連発だ！！！！！ これもあれも！ drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 が与えられる。これらから 個を選ぶ 通りの方法についての 「選んだ 個の整…
面白かった 問題へのリンク 問題概要 長さ の整数列 が与えられる。 長さ の 0 と 1 からなる文字列 に対して定まる関数 は次のようになっている。 は、次のようにして文字列 を文字列 に一致させるのに必要な最小コストとする。 回目の操作で、 の文字 を選…
じゅぴろ君が「これは中受典型」と言いそうな雰囲気がありますね。 問題へのリンク 問題概要 以上の整数 が与えられる。 を計算した値において、末尾に何個の 0 がつくのかを求めよ。 制約 考えたこと これとよく似た形で、たとえば の末尾に 0 が何個つくか…
この Floyd--Warshall は天才すぎる！ 問題へのリンク 問題概要 頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。 各頂点では燃料を補給できて、補給すると満タン (容量 の…
個人的には bitDP は「順列を全探索するもの」というイメージがあるけど、今回はそれとはまた違う bitDP という感じ！ 問題へのリンク 問題概要 個の宝箱がある。宝箱を開けるための鍵が 個あって、それぞれの鍵はいくつかの宝箱に対応している。鍵 を用いる…
区間反転操作問題シリーズ！！！ それにしてもいろんな見方ができる問題な気がする。 問題へのリンク 問題概要 長さ の 'B', 'W' からなる文字列 があたえられる。今この文字列に 回の操作を行う。 まだ選んでいない 2 マス を選んで区間 [ ] の 'B' と 'W' …
文字列検索に関するライブラリが充実していれば怖いものがない。でも文字列のことを知らなくても実は DP でも解ける！！！ Suffix Array Z-algorithm (editorial 解) ロリハ + 二分探索 「ロリハ + 二分探索」の高速化 (editorial のラスト 3 行で言及された…
木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…
グラフの頂点を倍加するタイプの問題ですね。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えらえます。頂点 から頂点 へと、けんけんぱで移動したいものとします。 1 回のけんけんぱでは、「自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接…
順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの 問題へのリンク 問題概要 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど 組であ…
共通部分列に関する問題！！！！！ 最長共通部分列問題は有名だけど、今回は共通部分列を数え上げる問題。 問題へのリンク 問題概要 2 つの数列 が与えられる。 と の共通部分列が何通りあるかを求めよ。 ただし、 や から抜き取ってできる文字列が同じもの…
復元つらい 問題へのリンク 問題概要 黒板に 個の整数 が書かれている。 書かれている数字から 2 個選んで として、これらを消して を新たに書き加える という操作を 回行って最後に残る整数の最大値を求めよ。またそれを達成する操作列を復元せよ ( を毎タ…
これと似てる！！！ これの解法 3 みたいなやり方をイベントソートって呼ぶのね。 drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) くらいのサイズの配列があって最初は INF に初期化されている。 回の以下の操作を行う 整数 が与えられて、区間 […
何をしたらよいかがすぐに見えてくる典型だけど、かなり手こずった 問題へのリンク 問題概要 整数 があたえられる。 のグリッドから 個を選んでコマを置く 通りの方法それぞれに対して 通りのコマにペアそれぞれについてのマンハッタン距離の総和 を求め、そ…
まさにこの考え方で解ける問題 drken1215.hatenablog.com 今回の問題も桁 DP でもよいのだが、実は桁 DP しなくても解ける。 問題へのリンク 問題概要 正整数 が二進数表記で与えられます。 以下の条件を満たす非負整数 の組がいくつ存在するか求めてくださ…
「探索候補は実はそう多くない」という教育的問題！！！ 問題へのリンク 問題概要 組の整数ペア がある。各ペアから整数をどちらかを選ぶ。こうして選ばれた 個の整数の最大公約数の最大値を求めよ。 制約 考えたこと 約数と言われて思い浮かべるべきことの…
これまた Union-Find を用いる教育的問題！！！！！ 問題へのリンク 問題概要 枚のカードがあって、それぞれ 1 か 2 の数値が書かれている。 枚のカードの数値 をすべて当てたい。 現在、以下の形式をした条件が 個与えらている: 整数 に対して、 は偶数であ…
気づけばすぐな感じかな 問題へのリンク 問題概要 本のロープがあってそれぞれの長さは で与えられる。最初、ロープ の右端とロープ の左端が結ばれている。今、 長さが 以上のひとつながりのロープを選び、その中に結び目があればどれか 1 つ選んでほどく …
楽しかった 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす正の整数 の個数を求めよ: を で割ったときの商と余りが一致する 制約 考えたこと とりあえず について手元で計算しているうちに、商と余りとが一致した値 として考えられる…
何も考えずにゲーム DP 毎ターン「実質的に取れる選択肢が二通りしかない」というパターン という包畜を含む教育的問題。 問題へのリンク 問題概要 先手と後手は初期状態で と と書かれたカードを持っている。 枚の山札があってそれぞれ の数値が書かれてい…
昨日の ABC で、「左右両端からの累積和」を使うと良い問題が出たので、その発展的類題の紹介に。 drken1215.hatenablog.com 問題へのリンク 問題概要 を正の整数とする。 個の要素からなる数列 にとおいて、 個の要素を取り除き、残った 個の要素のうち (前…
状況がゴチャゴチャとして来て、整理するのが大変だった 問題へのリンク 問題概要 個のマスがあって最初は全マスに が書かれている。これに以下の操作を好きな回数だけ好きな順序で行って数列 にできるかどうか判定せよ。 を巡回させてできるものを足す 制約…
頭の整理が大変！！！ 問題へのリンク 問題概要 左から右に向かって 1 から N の番号がついた N 個のマスがあります。 各マスには文字が書かれており、マス i には文字 si が書かれています。また、各マスにははじめ 1 体のゴーレムがいます。 すぬけ君は Q …
各地点に早くたどり着いておくに越したこと無い系問題！！ atcoder.jp 問題概要 のグリッドがあってスタートからゴールへと行きたい。壁のあるマスは通れない。 ただし毎秒ごとに移動できる方向に制限がある。 で割ったあまりがそれぞれの場合についてどの方…
