2022-12-01から1ヶ月間の記事一覧
コンテスト中、Sparse Table だと思わずに解いていた。コンテスト後に TL で Sparse Table だと見て、「確かに！」と思った。 問題へのリンク 問題概要 インタラクティブ問題である。次のフェーズ I とフェーズ II に分かれる。 フェーズ I ジャッジから整数…
これをグラフの問題だと思えるかどうか！ 問題へのリンク 問題概要 箱の中に 個のボールが入っており、各ボールには 以上 以下の整数が書かれている。 番目のボールに書かれた整数は である。 箱の中に 2 個以上のボールが残っている限り、下記の行動を繰…
上手に整理すれば、とてもシンプルな問題！ 問題へのリンク 問題概要 正の整数 が与えられる。 を で割った商 を で割ったあまりを求めよ。 制約 考えたこと で割るような操作を 2 回しているので、 を で割った余りを考えるとよいのだろうなというあたりを…
floor sum のいい感じの練習問題！ 問題へのリンク 問題概要 正整数 が与えられる。 非負整数 を用いて という形で表せる正の整数のうち、 番目に小さいものを求めよ。 ( 個の入力ケースが与えられる) 制約 考えたこと いかにも二分探索という問題。次の判定…
floor sum の練習！ 問題へのリンク 問題概要 以上 以下の の倍数をすべて十進表記で 1 回ずつ書き出した時、数字 が書かれる回数を求めよ。 (テストケースが 個与えられる) 制約 考えたこと 各桁ごとに考える。整数 の右から 桁めが である条件は を で割っ…
floor sum と聞いて！！ 問題へのリンク 問題概要 以上 以下の整数のうち、 で割って 余るものを考える。そのような整数の popcount 値の総和を求めよ。 ( ケース与えられる) 制約 考えたこと TL を見て、floor sum と知った上での考察。 「popcount の総和…
一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある！ その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる！！ 問題へのリンク 問題概要 頂点数 、辺数 の単…
フラグの考え方で解くのが一番分かりやすいと思った 問題へのリンク 問題概要 英小文字と、文字 , と " からなる長さ の文字列 が与えられます。 に含まれる文字 " の個数は偶数であることが保証されています。 に含まれる " の個数を 個とすると、各 につい…
レピュニット数を題材とした問題。 問題へのリンク 問題概要 を 個並べた数と、 を 個並べた数の最小公倍数を で割ったあまりを求めよ。 制約 考えたこと を並べた数をレピュニット数とよぶ。数学的に面白い性質が色々ある。 レピュニット数の最大公約数は、…
文字列の連続した部分文字列を数え上げるのは Suffix Array の典型問題。それを少し応用した面白い問題！ 問題へのリンク 問題概要 英小文字からなる 2 つの文字列 が与えられる。次の条件を満たす文字列の個数を求めよ。 中に連続した部分文字列として含ま…
Suffix Array の典型問題 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列として登場しうる文字列をすべて考える。重複は除外する。これらの文字列の長さの総和を求めよ。 制約 考えたこと 次の問題とほと…
めっちゃ面白い問題だった！ Suffix Array の練習問題。 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 の suffix は空文字列を除いて 個ある。これらの suffix を適切な順序で連結させて 1 つの文字列を作るとき、それが辞書順最…
すごくシンプルな面白い問題。 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを並び替えて連結して 1 つの文字列を作る。作れる文字列のうち、辞書順最小のものを求めよ。 制約 解法 単純に を辞書順にソートして、小さい順に連結するのでは反…
Suffix Array の練習問題 問題へのリンク editorials へのリンク 問題概要 英小文字からなる文字列 と、 個のクエリが与えられる。 各クエリでは 2 つの文字列 が与えられる。 文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の…
久しぶりに bit ベクター高速化を使った。デバッグがしんどかった。 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。今、次の操作をちょうど 回実行する と を選ぶ と とを swap する 操作実行後の の値の最大値を求めよ。 制約 考えた…
シミュレーションの仕方を工夫する問題。数値ごとに index をまとめあげるデータを持つとうまくいく。 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。 の順列 であって、 を満たすものを考える。そのような順列の (ただし である場合の の場合は…
とても面白かった。文字列に操作を 回施して、操作後の文字列の辞書順最小のものを求める問題。Suffix Array のよい練習問題でもある。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。この文字列に対して、以下のいずれかの作業…
Suffix Array と LCP の理解を問う問題。超シンプルで面白い問題！ 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 解法 文字列 の Suffix とは「後ろの何文字かをとってできる文字列」のことである…
Floor Sum が AtCoder 標準ライブラリに入ったのはびっくりした。結構マニアックな印象だった。 問題へのリンク 問題概要 この問題は ケース与えられる。整数 が与えられるので、 を求めよ。 制約 考えたこと 等差数列を で割った商の総和を求めたくなること…
BIT の使い方の練習問題。同時に、自分で BIT を書いたときにそれを verify できる問題でもある！ 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対する 個のクエリに答えよ。 ：数列中の値 に を加算する (a[p] += x) ：数列 の区間 の総和…
Union-Find の最も典型的な練習問題 問題へのリンク 問題概要 頂点 辺の無向グラフに 個のクエリが飛んでくる ：辺 を追加する ： 頂点間 が連結ならば 1、そうでないなら 0 を出力する 制約 解法 Union-Find はグループ分けを管理するデータ構造です。以下…
よくあるデータ構造問題！！ めっちゃ色んな解法がある！ 問題へのリンク 問題概要 長さ の整数列 と整数 が与えられる (0-indexed で表している)。 各 に対して、次の問題に答えてください。 個の整数 を小さい順に並び替えたときの先頭 個の総和を求めよ。…
残り 1 分でなんとか通せた。 問題へのリンク 問題概要 頂点数 の連結な単純無向グラフ (頂点番号は であって、次の条件を満たすものの個数を で割ったあまりを求めよ。 なお、ここで、頂点 から各頂点 までの最短距離を としている。 制約 考えたこと グラ…
数列に対して、2 進法で表して、再帰的に上位桁から 0 と 1 で分類した木を作る！！！ こどふぉではよく見るやつですね。 問題へのリンク 問題概要 個の非負整数 が与えられる。ある非負整数 を上手に選んだときの、 の値の最小値を求めよ。 制約 考えたこと…
部分和問題の応用問題！ 問題へのリンク 問題概要 個の非負整数 が与えられれる。 これらの整数から 個選んで、総和が の倍数となるようにする。その値として考えられる最大値を答えよ。 の倍数にするのが不可能な場合は -1 を答えよ。 制約 前提知識 この問…
「割り算を使う」「ある値が 0 以下になるまで繰り返す」といった典型処理要素を詰め込んだ問題ですね！ 問題へのリンク 問題概要 曲からなるプレイリストがあり、曲には の番号が付けられています。各曲の長さは です。 プレイリストを再生すると、曲 の順…
ハニカムにそんな性質があるなんて！！！ 45 度回転する技術のアナロジーが炸裂する。 あと、x 座標が最小となる点で場合分けする際に、同一の x 座標を持つものに対してダブルカウントを除去する工夫が大変だった。 問題へのリンク 問題概要 2 次元平面上に…
単純な全探索で解ける！ 累積和で高速化したり DP したりしても OK 問題へのリンク 問題概要 のマス目があり、上から 行目、左から 列目のマスをマス と表すことにする。マス には 個のアメが置かれている。 あなたははじめ、左上のマス にいる。 右方向ま…
これも重み付き Union-Find で解ける問題！ 問題へのリンク editorial 問題概要 具体例として一つの入力ケースを示す。 7 1 kilometre = 10^3 metre 1 megametre = 10^3 kilometre 1 metre = 10^-6 megametre 1 terametre = 10^3 gigametre 1 petametre = 10…
重み付き Union-Find が有効活用できる問題！ 問題へのリンク 問題概要 個の変数 の値を決定したい。 これらの値を決定するための 本の制約条件がある。このうち 個めの情報は 3 つの値 によって与えられ、 であるという制約条件を表す。 これら 本の制約条…
