「決めてから、整合性を確認する」というタイプの問題の典型例ですね！ 問題へのリンク 問題概要 の非負整数を成分とする行列 が与えられる。 すべての について を満たすような非負整数列 と の組が存在するか判定し、存在するなら一つ出力せよ。 制約 考え…
これ茶色はさすがにびっくりした！ 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…
なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …
間に合わなかった！！！悔しい！！！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…
いわゆる、 まで調べれば十分というタイプの問題だね。最近そのタイプの問題が流行っている気がする！ 問題へのリンク 問題概要 十進法表記で偶数桁で、かつ、その前半と後半とが文字列として等しいようなものを「良い整数」と呼ぶことにします。 以上 以下…
発想や考え方はそんなに難しくないんだけど、すごく頭がこんがらがってしまう問題だね... 問題へのリンク 問題概要 が表に書かれたカードが 枚ずつ、計 枚のカードがあります。 これらのカードをランダムにシャッフルして、高橋くんと青木くんにそれぞれ、4 …
むずかしかった！！！ でも、約数列挙でありがちな「 まで試せば良い」という考え方がちゃんと理解できているかを問う良問だった！！ 問題へのリンク 問題概要 整数 が与えられる。 1 以上 以下の整数のうち、 2 以上の整数 を用いて と表せないものはいくつ…
lower_bound の練習に！！！ あと、「3 つのものを考えるときは、真ん中を固定して考える」という考え方の典型。 問題へのリンク 問題概要 3 つの数列 (長さ ) が与えられる。各数列から要素 を選ぶ方法のうち、 を満たすものの個数を求めよ。 制約 考えたこ…
すごく面白かった！ 問題へのリンク editorial スコア: 191.85 / 500.00 問題概要 "I" と "O" のみからなる文字列 が IOI 文字列であるとは、ある正の整数 が存在して = "I" = "O" = "I" が成立することと定義する (1-indexed)。 いま、"I", "O", "?" のみか…
SRM 埋めを始めたいと思う！ ところでこの問題、こんなの気付かないよ...！！ まあ、Petr と tourist も参加したコンテストで誰も AC してない問題なので...。 問題文へのリンク 問題概要 10 進法表記で最高次数から順に広義単調増加であるような整数を Incr…
面白かった！セグ木を使ったけど、区間を複数個にする必要がないことから、しゃくとり法で線形でできるね！ 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を繰り返すことで、単調増加となるようにしたい。 区間 の要素をすべて削除する (コスト…
DIjkstra をするときに、直前の頂点ももつ系 問題へのリンク 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点 の座標は となっている。 頂点 1 から頂点 2 へと至る経路のうち、鋭角に曲がる箇所がないようなものを考える (頂点 の前の頂点…
読解が大変だけど、本質的には木 DP な問題 ジャッジへのリンク AOJ ページ 問題概要 本の棒を用いて、下図のようなモビールを作りたい。 入力としては、各棒 についての 左端から支点までの長さ 右端から支点までの長さ 左端からつながっている棒の index (…
面白かった！ 問題へのリンク 問題概要 個の石の山がある ( は偶数)。 番目の山には 個の石がある。先手と後手が交互に以下の操作を行う。操作できなくなった方が負けである 石の山のうち、まだ石が 1 個以上残っている山をちょうど 子選ぶ そのそれぞれの山…
KMP 法で殴ったけど、愚直にやっても調和級数的計算量で間に合うね。 問題へのリンク 問題概要 円周上に等間隔に 個の点が打たれている。これらの点を端点とした 個の線分がある (下図のような感じ)。 これが回転対象性をもつかどうかを判定せよ (1 周未満の…
面白かった。重み付き Union-Find を使った。 問題へのリンク 問題概要 0 と 1 と ? のみからなる長さ の文字列 が与えられる。先頭の文字が 1 であることが保証されている。 以下の条件を満たす整数の組 () の個数を求めよ。 はともに回文数である (11 や 1…
とにかく実装力を鍛えよう〜〜 問題へのリンク 問題概要 個の文字列が与えられる。そのうちのいくつかは先頭の文字が ! である (それ以外はすべて英小文字)。 red gray !orange yellow !blue cyan !green brown !gray ! の付いていない文字列と、付いている…
ペア の大きい順にソートする嘘貪欲にハマってしまった方が多そうだった 問題へのリンク 問題概要 青木君と高橋君が選挙を行う。 個の町があり、 番目の町では 青木派が 人いる 高橋派が 人いる ということがわかっている。高橋君はいくつかの町で選挙活動を…
これの応用問題って感じだった！！ drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…
な bit DP としてよく知られている問題ですね！ 問題へのリンク EDPC U - Grouping の類題と言える！ atcoder.jp 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラ…
トポロジカルソートせよ、という問題！ 問題へのリンク 問題概要 頂点数 、辺数 の DAG (閉路のない単純有向グラフ) が与えられる。 このグラフのトポロジカルソート順を一つ求めよ。また、トポロジカルソート順が唯一かどうかを判定せよ。 制約 考えたこと …
数列をヒストグラム化することで解決できるタイプの問題！特に今回みたいに、数値の値も 以下と小さい場合はすごくそれっぽい！ 問題へのリンク 問題概要 長さが の正の整数からなる数列 が与えられる。以下の条件を満たす の個数を求めよ。 なる任意の に対…
これは難しい！！！ 誘惑されそうな嘘解法がたくさんある！！ 問題へのリンク 問題概要 件の日雇いアルバイトがあります。 件目の日雇いアルバイトを請けて働くと、その 日後に報酬 が得られます。 あなたは、これらの中から 1 日に 1 件まで選んで請け、働…
「大体こういう感じ」というところまではすぐに見えるけど、細かいところを詰めるのが大変な問題かもしれない。 問題へのリンク 問題概要 マスがあって、各マスには "L" または "R" が書かれている (左端は "R" で右端は "L" であることが保証される)。また…
面白かった。 問題へのリンク 問題概要 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 人のうち、何人かについてはスパイかどうかが予めわかっている ( で与えられる)。 個の証言がある。各証言は人 が証言者によってなされ、「人 はスパ…
難易度 8 でもおかしくないと思った。 B や C より易しい気がしなくもないけど、本番の緊張感で B や C を飛ばして D を本気で考える決断はなかなかできなさそう。今回は B - パンケーキを見て冷静になれたか勝負だね... 問題へのリンク 問題概要 個の工場が…
これ本当にずっとわからなかった...言われてみればという感じ！！ 問題へのリンク 問題概要 以下の条件を満たす、頂点数 の有向グラフ (頂点番号を とする) を構築せよ (自己ループも多重辺も可)。 すべての頂点の出次数は 2 である 任意の頂点対 に対して、…
いろんな方法がありそう。Union-Find のマージ過程を表す木でやったけど、ほかにも Undo 付き Union-Find を使うなど 問題へのリンク 問題概要 頂点数 、辺数 のグラフが与えられる。初期状態では各頂点に という値がついている (すべて 1 以上で disjoint)…
こどふぉ特有の 回以下の操作で〜を達成せよ、という問題 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。以下の操作を 回以下繰り返すことで、数列の値がすべて等しくなるようにしたい。そのような操作列を一つ求めよ。不可能である場…
バチャ中に TLE が取れなかった... で実装してしまっていたけど、 にする必要があったみたい。 問題へのリンク 問題概要 長さ の 0 以上の整数からなる数列 が与えられる。 0 以上の整数 を適切に定めて XOR で定まる数列 の転倒数が最小となるようにせよ。…
