考察：操作・条件・目的関数を言い換える
種類数に関する面白い問題！ 問題へのリンク 問題概要 2 つの文字列 は、 である を左右反転してできる文字列 について、 である といういずれかの条件を満たすとき、似ているとみなす。 与えられた 個の文字列 について、似ている文字列は同一視することに…
初歩的な Greedy の問題と言える。 問題へのリンク 問題概要 以上 以下の整数からなる数列 であって、 は で割り切れる という条件を満たすものを考える。そのような数列の長さの最大値を求めよ。 制約 考えたこと 基本的には、なるべく小さい値でスタートし…
面白かった！！ 問題へのリンク 問題概要 人がいて、それぞれ正直者であるか、嘘つきであるかのいずれかである。また、各人は混乱していないか、混乱しているかのいずれかである。 混乱していない正直者は、常に正しいことをいう 混乱している正直者は、常に…
極端な場合を考えて考察した！ 問題へのリンク 問題概要 非負整数 (片方は正) が与えられるので、以下の条件を満たすような二次元グリッドを構築せよ（存在しない場合は、そのことを報告せよ）。 グリッドのマス数は 以上 以下 グリッドの各マスは白色または…
これは典型らしいので、このセグメント木の使い方は今後押さえる！ 問題へのリンク 問題概要 正の整数からなる数列 が与えられる。 一般に、数列 に対して、 とする。まず の値を求めて、その後、次の 回のクエリに答えよ。 【クエリ】 整数 が与えられるの…
完全に言われた通りに実装してしまうと、 の計算量となって TLE してしまうので、工夫しよう！ 問題へのリンク 問題概要 空の配列に対して、以下の操作を 回行う。 回目の操作では 配列の末尾に値 を挿入する 配列全体を reverse する を行う。 回操作後の配…
すごく悩んだけど、なんとか解けた！ 問題へのリンク（仮） 問題概要 次の図のように、木を、文字 (、)、1 からなる文字列で表す（異なる木が同じ文字列になることもある）。文字列の生成規則は次のように表される。 E ::= ‘1’ | ‘(’ E E ‘)’ 詳細は問題文を…
面白かった！ 一見 MST の問題に見えるけど、主客転倒すると Dijkstra だった。 問題へのリンク（仮） 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。頂点 には重み がついていて、辺 には重み がついている。このグラフの全域木のコストを次…
面白かった！ カタラン数的なものが登場する。 問題へのリンク 問題概要 制約 考えたこと まずすぐにわかったことは、 の中に、1 が 2 個以上あってはダメ の中に、1 が末尾以外の場所にあってはダメ ということだった。そうすると、 は次のいずれかの形にな…
問題文がややこしい書き方をしているけど、「要するにこういうこと！」という言い換えができるといい。 問題へのリンク 問題概要 文字 ., @ からなる長さ の文字列 が与えられる。@ を左から順に 個だけ . に書き換える。 書き換えたあとの文字列に含まれる…
ちょっと工夫が必要な感じ 問題へのリンク 問題概要 長さ 正整数列 と、正の整数 が与えられる。 数列の区間であって、総和を で割った余りと、区間内に含まれる要素の個数とが等しいものの個数を求めよ。 制約 考えたこと 結構ややこしい。落ち着いて条件を…
上手に式変形しよう！ 問題へのリンク 問題概要 正の整数からなるサイズ の数列 が与えられる。次の条件を満たす組 の個数を求めよ。 制約 考えたこと 条件が不思議だ。普通は よりも の方が大きいことが多いのに、 となる条件を問うとは。 さて、この手の数…
条件を上手に言い換えよう！ 問題へのリンク 問題概要 個の整数 が与えられる。 が平方数 という条件を満たすような組 の個数を求めよ。 制約 考えたこと これは「条件の言い換え」を頑張る問題。「 が平方数」という条件を扱いやすいように言い換えよう。こ…
すごく面白い問題！ 問題へのリンク 問題概要 個の文字列 が与えられる。 これらの文字列から異なる 2 つの文字列を選ぶ方法であって、それらの文字列が互いにアナグラムとなっているものの個数を求めよ。 制約 考えたこと まずは、問題の条件をわかりやすく…
これはややこしい！ 問題へのリンク 問題概要 マス が一列に並んでいる。最初、 個のマスに石が入っており、マス には 個の石が入っている。あなたは以下の操作を好きな回数行うことができる。 「マス に石があるとき、マス からマス へと石を 1 つ移動させ…
座標ごとに情報を整理するのは頻出！ 問題へのリンク 問題概要 x-y 座標平面上に 人がいる。それぞれ座標 の位置にいて、左右いずれかを向いている（各人が左右どちらを向いているかは文字列 で与えられる）。 各人が、その位置から、向いている方向に向かっ…
ちょっとした考察が必要になる問題。 問題へのリンク 問題概要 整数からなる数列 が与えられる。数列の各要素に対して「何もしない」「1 を足す」「1 を引く」をしていく。 操作後に、整数値 を選ぶ。 となる の個数の最大値を求めよ。 制約 考えたこと 問題…
evima さんの別解で解いた。 問題へのリンク 問題概要 頂点数 の単純な木が与えられる。この木に辺を 1 本追加して得られるグラフのうち、次の条件を満たすものの個数を求めよ。 単純グラフである サイクルをちょうど 1 つ含み、そのサイクルに含まれる頂点…
サンプルを見れば上限が分かる系の問題！ 問題へのリンク 問題概要 各桁の値が 1 である数をレプユニット数という。 レプユニット数 3 個の和として考えられる数のうち、 番目に小さい数を求めよ。 制約 考えたこと まず、問題文の条件を満たす数をトリレプ…
探索アプローチでも解けるし、整数論的考察で解くこともできる。 問題へのリンク 問題概要 の倍数であって正の整数であるものをいくつか用意する。 その総和を で割った余りが となることはありうるか？ 制約 考えたこと まず、「いくつかの正の の倍数を足…
綺麗な言葉で条件を言い換えよう！ 問題へのリンク 問題概要 一列に白色碁石と黒色碁石が合計 個並んでいる。 左右のいずれかに白色碁石と黒色碁石を置いていく。このとき、オセロのルールに基づいて石の色がひっくり返る。 すべての色を同色にするのに必要…
実はとても単純な解法に落とし込めるのだけど、発想がちょっと難しい 問題へのリンク 問題概要 AtCoder 王国の 1 週間は 日あり、最初の 日が休日、後半の 日が平日である。 高橋君は 日分の予定があり、それぞれ 日目に予定がある。 これらの予定日がすべて…
問題の条件をいかにうまく言い換えるか！ 問題へのリンク 問題概要 2 つの整数 が与えられる（）。 を小数点第四位を四捨五入して、小数点第三位まで表した結果を求めよ。 考えたこと を整数型ではなく、浮動小数点型として受け取って、B / A を計算して小数…
問題文の操作を上手に言い換えて、for 文で処理できる形にしよう！ 問題へのリンク 問題概要 長さ の数列 に対して、以下の操作を 回実施してできる数列を出力せよ。 数列の先頭の数値を削除し、末尾に 0 を挿入する 制約 考えたこと C++ では、数列は vector<int></int>…
意外と実装に手こずった人も多いかもしれない。上手に for 文で実装できる操作に言い換えていこう！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 今、 かつ をみたす 4 つの整数 が与えられる。 数列 の 番目から 番目の項までと、 番目から 番目の…
言われた通りにシミュレーションする問題！ 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。この数列に対して 降順にソートする から 1 を引く という操作を「数列に含まれる正の数が 1 個以下」になるまで繰り返す。操作は何回行うこ…
意外と頭がこんがらがる 問題へのリンク 問題概要 人の人 がいて、人 の名字は 、名前は である。 各人にニックネームをつけたい。人 のニックネーム は または である かつ である任意の に対して、 かつ である という条件を満たす必要がある。このような…
これは上手にやろう！ 問題へのリンク 問題概要 2 つの正の整数 を足すとき、繰り上がりが発生するかどうかを判定せよ。 制約 考えたこと 一見いかめしい問題を解くときには、少しでも思考をシンプルにしていこう！ 繰り上がりがないというのは、次のことと…
条件を巧みに言い換えて整理しよう！ 問題へのリンク 問題概要 3 個の整数 が与えられる。 がメディアンであるかどうかを判定せよ。 解法 がメディアンとは、すなわち、 を小さい順に並べたときに、 が 2 番目に小さいということである。そのような場合は が…
これは面白い！ 問題へのリンク 問題概要 文字 J, O, I からなる、長さ の文字列 が与えられる。 の文字を並び替えて、次の条件を満たすものを求めよ。 すべての文字 J は、すべての文字 O よりも前にある すべての文字 O は、すべての文字 I よりも前にある…
