set をちゃんと使えるかを試す問題！ 問題へのリンク 問題概要 高橋くんは最初、体力は であり、二次元平面上の座標 にいる。 高橋くんは今から 回の移動を行う。高橋くんの移動方法は長さ の文字列 で表される。1 回の移動は、上下左右のいずれかであり、そ…

「並び替え方」の全探索は、C++ なら next_permutation()、Python3 なら itertools.permutations() が使える！ 問題へのリンク 問題概要 個の長さ の文字列 が与えられる。 これらを並び替えて得られる文字列 であって、 「 と が 1 文字違いである」() とい…

結構整理するの大変！ 茶色あっても良さそうだと思ったけど、灰色上位問題だった。 問題へのリンク 問題概要 2 つの長さ の文字列 が与えられる。これらは英小文字または文字 '@' のみからなる。 の各文字 '@' は、"atcoder" に含まれるいずれかの文字に変え…

データの持ち方をうまく工夫することで、計算量を改善する系の問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 個のクエリが与えられるので、それらを順に処理せよ。クエリは次の 3 種類ある。 x：数列 をすべて に書き換える i x： に を足す i…

文字通り、与えられた数列を座標圧縮する問題ですね。 問題へのリンク 問題概要 長さ の数列 が与えられます。 これらの数列から重複を除外して小さい順に並び直して得られる数列を とします。 各 に対して、 となるような を出力してください。 制約 座標圧…

競技プログラミングで時々問われる「座標圧縮」について簡単に解説します。 1. 座標圧縮とは 数列 が与えられたときに、それぞれの要素が「全体の中で何番目に小さいか」を求めていく作業を、競プロ界では座標圧縮 (座圧) とよびます。 たとえば A = (8, 100…

Grundy 数がフラクタルっぽい構造を示していた！ 問題へのリンク 問題概要 個の石の山がある。各山には 個の石がある。先手と後手が交互に以下の操作を繰り返す。 山を一つ選ぶ。その山には石が 個あるとする。 その山の石の個数が 個または 個となるように…

日付に関する問題は Python が楽！！ 問題へのリンク 問題概要 与えられた日付から、2014/05/17 までの経過日数 (負もありうる) を求めよ。 制約 "1988/07/03" から "2014/12/31" まで 考えたこと 全部 Python の datetime に任せる！ コード import datetim…

現在の AtCoder ではあまり出なさそうな問題。こういうのは Python 楽だね。 問題へのリンク 問題概要 (西暦) ÷ (月) ÷ (日) が整数となるような日付を「割り切れる日付」と呼ぶ。 日付が "2020/11/14" のようなフォーマットで与えられる。その日付以降の最…

グリッドの縦方向の情報と横方向の情報を前処理するのは典型ですね！！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 のグリッドの各マス目に数値が書かれている。 各マス に対して、「そのマスと行または列が等しいマスの数値の総…

木の直径を求めよ、という問題。直径を考えると解ける問題は高難易度でもお馴染みですね。 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 頂点数 の木が与えられます。 この木に新たに辺を 1 本追加すると、閉路が 1 つできます。 …

整合したカッコ列を bit 全探索する問題！！！ 問題へのリンク editorial へのリンク 類題とか drken1215.hatenablog.com 問題概要 長さ の「整合したカッコ列」を辞書順にすべて列挙せよ。 整合したカッコ列の意味については、問題ページにて。 制約 考えた…

「最小値の最大化」には二分探索が有効という典型ですね。 問題へのリンク 解説へのリンク 前提知識 二分探索にまったく経験がない場合は、まずは次の記事を読んでみてください。 qiita.com 問題概要 長さ のようかんがあって、そのうち左端から の位置に切…