AtCoder475点
Union-Find を上手に使おう！ 問題へのリンク 問題概要 初期状態では頂点数 、辺数 0 のグラフがある。頂点番号は である。次の 回のクエリに答えよ。 クエリタイプ 1：頂点 間に辺を張る クエリタイプ 2：頂点 を含む連結成分に含まれる頂点の番号にうち、 …
共通テスト数学 IA にも似た問題が出ていた！ 問題へのリンク 問題概要 頂点数が のサイクルグラフが与えられる。このグラフの各頂点を色 のいずれかの色で塗る。 どの隣接する頂点対も異なる色で塗られるようにする方法の個数を 998244353 で割った余りを求…
面白かった！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 の値を求めよ。 制約 考えたこと まず、 という制約が怪しい！！！ きっと、 として な計算量になるに違いないと思えた。 とりあえず、数列を元のまま考えるのではなく、…
ChatGPT が問題文コピペのみで解けたと話題になった！ 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。 先手と後手が交互にゲームする。交互にまだ残っているカードのうち、表の値が等しいか、裏の値が等しいような 2 枚のカー…
データ構造をいい感じに設計する地力が問われる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対する以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる を に置き換える 置き換えたあとの数列 の mex を出力せよ 制約 考えたこ…
next_combination を使った！ 普通に STL の next_permutation() でもできる。 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き無向グラフが与えられる。 このグラフの全域木をすべて考えたときの、全域木に含まれる辺の重みの総和を で割ったあま…
式がいかめしくて戸惑うけど、DP 自体は比較的単純 問題へのリンク 問題概要 個の値 が与えられる。 これらの中から順序を保っていくつか選ぶ。選び方のスコアは、 個の整数 を選んだとしたとき、 で与えられる。このスコアの最大値を求めよ。 制約 考えたこ…
chokudai さんの思想が詰まった問題 問題へのリンク 問題概要 個の開発案がある。これらの開発案によって上昇し得るパラメータが 種類ある。 開発案 () を採用すると、パラメータ () の値が だけ上昇する。その分、 のコストがかかる。 すべてのパラメータを…
有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…
Union-Find 慣れしていれば解きやすい！ 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフ が与えられる。 組の頂点対 について、どの頂点対間のもパスがないグラフを良いグラフと呼ぶことにする。 与えられるグラフ は良いグラフである。 このグラ…
DFS などの探索をしても解けるし、単に次数を見るだけでも解ける。 問題へのリンク 問題概要 個の葉をもつスターグラフを、レベル のスターと呼ぶことにする。 高橋君は、はじめ何個かのスターからなるグラフを持っている。これらのスターの頂点数の総和は …
前処理して頂点数を減らしたグラフ上で TSP！！！ ICPC ではすごくよく見るパターンですね！ 問題へのリンク 問題概要 サイズのグリッドがある。各マスは 壁マス：'#' 通路マス：'.' お菓子マス：'o' (18 個以内であることが保証される) スタートマス：'S' …
