構築
誤読したーーーーー 問題へのリンク 問題概要 頂点数 、辺数 の連結な無向グラフが与えられる (多重辺はありうるが、自己ループはない)。各辺には色がついていて、色は 以上 以下の整数値で与えられる。 各頂点に 以上 以下の色を割り振りたい。このとき、「…
グリッドグラフは二部グラフ！！！ 問題へのリンク 問題概要 のマス目に整数値 (マス には ) が書かれている。 各マスについて、「元の整数値のままにする」または「元の整数値に 1 を足したもの」をすることによって、どの隣接する 2 マスの値も互いに相異…
これは天才パズル！！！ 問題へのリンク 問題概要 のグリッドに 0, 1 の数値を書き込む方法であって、 どの行をみても、それに含まれる 0 の個数と 1 の個数のうちの小さい方の個数が どの列をみても、それに含まれる 0 の個数と 1 の個数のうちの小さい方の…
ちょっと面白い感じの構築問題！ 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす 3 つの格子点 の組を一つ求めよ。 座標値はすべて 以上 以下の整数値 3 つの格子点からなる三角形の面積を 2 倍すると に一致 制約 考えたこと 仮に 1 …
構築楽しかった 問題へのリンク editorial 問題概要 のグリッド上に のドミノを互いに重ならないように配置していく。 どの行・列を見ても、その行・列上にある のドミノの個数が互いに等しいような配置を求めよ。存在しない場合は "-1" を出力せよ。 制約 …
面白かった！ 問題へのリンク 問題概要 頂点数が の木であって、各頂点 から最も遠い頂点への距離がそれぞれ であるような木が存在するかどうかを判定せよ。 制約 考えたこと 面白そう！！！！！！似た見た目の問題としては、次の問題もあった。 drken1215.h…
山登り法で見つかった！スコアが下がっていくのを眺めるの快感！ 問題へのリンク 問題概要 のグリッドに以下の条件を満たすように英小文字を入れよ。 横方向、縦方向に連結しているマス目を抜き出してできる文字列は 個ある そのすべてが互いに相異なる これ…
面白かった 問題へのリンク 問題概要 という 個の整数がある。これらを 2 個以上のグループに分ける。各グループの整数の総和が互いに等しくなるようにグループ分けすることが可能かどうかを判定し、可能ならば具体例を構築せよ。 制約 考えたこと こういう…
テスターしてました！難しかった。 問題へのリンク 問題概要 ラスク君は木を持っていましたが、なくしてしまいました。 この木は、頂点に 1 以上頂点数以下の相異なる整数の番号がついていて、各辺には 以上 以下の整数の重みが定まっていました。 頂点数は …
面白かった 問題へのリンク 問題概要 以下の条件を満たすような 個の区間 ( 番目を とする) を構築したい。 はすべて互いに相異なる整数 これらの区間の中から「どの 2 個も交差しないように最大で何個の区間を選べるか」という問題に対して、高橋君と青木君…
ならば になるネタ、結構見る！ 問題へのリンク 問題概要 数列 があって、初期状態では となっている。ここで 2 つの正の整数の組 に対して正の整数 を返す関数 を考える。 次の条件を満たす操作列を構築せよ。1 つの操作は整数 で与えられ、 , をともに で…
BFS 木とか、BFS による経路復元とか、その辺りの理解を問いかける教育的問題だった！！！ 問題へのリンク 問題概要 頂点、 辺の無向グラフが与えられる。頂点 1 以外のすべての頂点に対し「みちしるべとなる頂点」を、以下の条件を満たすように設定すること…
軽めの構築問題！！ 今回は「最大次数」というのが割と明らかだけど、しっかり構築法踏まえて証明する練習をすると、高難易度問題にも繋がりそう！ 問題へのリンク 問題概要 頂点の木が与えられる。 本の辺に色を塗っていきたい。ただし、どの頂点についても…
こういうの大好き！ 問題へのリンク 問題概要 の盤面 A が与えられる。各マスは白か黒かのいずれかである。次の条件を満たす、同じ大きさの白黒の二つの盤面の組 (S, T) を構築せよ S の黒マスはすべて縦横に連結である T の黒マスはすべて縦横に連結である …
12 が 4 の倍数で、112 が 8 の倍数だから、1112 が 16 の倍数なんじゃないの...と迷走したりしていた。 問題へのリンク 問題概要 以下の条件を満たす整数 を 1 つ求めよ (というクエリに 回答えよ) 桁の整数である どの位の値も 0 ではない 各桁の話を とし…
面白かったけど、実際に実装するのは辛かった。 問題へのリンク 問題概要 のグリッドが与えられる。各マスを 2 または 5 で埋めたい。ただし以下の条件を満たすようにしたい。 2 が書かれたマスだけに着目し、上下左右斜め に隣接するマス同士に辺を張ったグ…
面白かった！！！ 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺に対して、以下の条件を満たすように 1 以上 1000000 以下の整数値を割り振りたい。 条件は 個ある 番目の条件は、2 頂点 と整数値 が指定されて、 を結ぶパス上の辺の値の最小値が…
実装に精彩を欠いてしまった...コンテスト中に WA を取りきれず... WA の原因は「すでに色を決めたはずの頂点について再度色を上書きしていることがある (現在見ている D 値について、それより小さい値の頂点とはつながっておらず、等しい D 値同士で結ばれ…
結構ギャグ要素強めな問題だった 問題へのリンク 問題概要 3 つの整数 が与えられる。 長さ の整数列 であって、以下の条件を満たすものを構築せよ: を満たすような の組がちょうど 個ある 制約 考えたこと とりあえず一つ思うこととして、 は全部 1 以上な…
900 点なので備忘録程度に... 久しぶりに競プロでめちゃくちゃ楽しかった！！！ 2 時間 10 分かかったので本番だったら通せていないけど、どうすればもっと早く解けたのかの反省もこめて。 問題へのリンク 問題概要 以下の条件を満たす 頂点の木を復元せよ。…
今日の会社のバチャでやった。面白かった。 問題へのリンク 問題概要 のグリッドに 'A', 'B', 'C' の各文字を書き込む。以下の条件を満たすものを一つ求めよ。 以下のような に対して である: 隣接する 2 マスの組であって一方が 'A' で他方が 'B' であるも…
初見時は証明なしに再帰的にやった... 問題へのリンク 問題概要 頂点の完全グラフがあたえられる。 このグラフの辺に、非負整数値を付けていく方法のうち 整数値が等しい辺のみからなる部分グラフが奇数長のサイクルを含まない という条件を満たす範囲内で、…
ちょっとややこしかった 問題へのリンク 問題概要 '0' 〜 '9' からなる 文字の文字列があたえられる。各文字を白黒に塗る。 どの黒く塗られた数も、あらゆる白く塗られた数以上である 白く塗られた数を元の文字列の順序で抜き取ったとき、数値は単調非減少で…
順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの 問題へのリンク 問題概要 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど 組であ…
冷静になれば自然な構成ではあるね...企業コンのラス問だと身構えてしまうのがよくない 問題へのリンク 問題概要 頂点からなる重みつき無向単純完全グラフであって、 通り考えられるハミルトンパスに対して始点と終点が同じものを同一視して得られる 通りの…
ちょっとした構築系問題という感じかな... 問題へのリンク 問題概要 二次元平面上の二点 が与えられる。 はすべて整数である。 今、 から出発して「上下左右に 1 秒に 1 だけ動く」という動作を繰り返しながら に行き、またそこから出発して に戻り、さらに…
600 点問題ともなると、さすがに正解者数も少ない。 色んな人が色んな構築してそうだけど、僕なりの方法をば。 問題へのリンク 問題概要 を 以上の整数とする。 以上 以下の整数が 2 個ずつあって、これを並べ替えてできる長さ の数列 であって、 となるよう…
とても教育的なツリーの探索問題。 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。このグラフの各頂点を白黒に塗る方法であって 同色に塗られた 2 頂点はどれを選んでも、その間のパスの長さは偶数である という条件を満たすものを求めよ…
楽しかった。 回文系の問題。「〜な条件だと結局全部一緒になる」という問題の雰囲気がどことなく数オリっぽい。 必要条件を頑張って列挙したら実は十分な感じもまた、数オリっぽさと AGC っぽさの両方がある感じ。 問題へのリンク 問題概要 総和が 、長さが…
これの Easy バージョン。すごく楽しくて好き！！！！！ Easy：操作の結果が所望になる入力を求める逆問題 Hard：操作に入力を与えた結果を求める問題 という風になっていて、普通「操作の結果を求めるだけ」の問題の方が絶対簡単なことが多いのに、Easy と …
