AOJ
面白かった！ 問題へのリンク editorials 問題概要 3 つの文字 B, Y, K からなる長さ の文字列 が与えられる。 この文字列をいくつかの区間に分割する。各区間について、 ランレングス圧縮すると、B -> Y -> K の順になるもの：区間の長さだけスコアを獲得 …
たまたま作れた！！！ 個人的傑作の自作構築問題。 問題へのリンク editorials 問題概要 正の整数 が与えられる。 のマス目に 1 以上 以下の整数を入れる方法であって、次の条件を満たすものを構築せよ。 【条件】 について、 行目または 列目のマスは 個あ…
にょぐた君と一緒に考察した。面白かった。公式解説は多面体で考えているけど、ここでは LP 双対で解いてみる。 問題へのリンク commentary 問題概要 種類の水溶液がある。水溶液 は、 として、 水溶液全体の重さが g 1 g あたりの溶質の重さが g 以上 g 以…
小谷の蟻の問題！ 問題へのリンク 問題概要 の直方体の表面上で、1 つの頂点から最も遠い点への距離を求めよ。 下の図は 1 x 1 x 2 の例であり、とくに「小谷の蟻の問題」と呼ばれている。 制約 考えたこと 1 x 1 x 2 のときに、直方体の反対側の頂点が答え…
ICPC 本番に正解チームの現れなかった難問！ 問題へのリンク 問題概要 サイズのグリッドグラフから、いくつかの頂点と辺を削除してできる連結なグラフが与えられる。 このグラフの全域木であって、どの 2 つの葉も、その間の距離が偶数であるものを 1 つ求め…
Block-Cut 木を試すのにすごくいい問題！ 問題へのリンク 問題概要 頂点数 、辺数 の連結な無向グラフが与えられる（単純とは限らない）。頂点 には、重み がついている。各頂点について、以下の問に答えよ。 【問】 その頂点を除外したグラフを考える。この…
これは比較的易しめだった。探索するだけ！ 問題へのリンク 問題概要 下図のように「計算過程」を表す二次元グリッドが与えられる。文字 . 以外の文字は木をなしていて、葉には数値がかかれている。演算子 +、-、*、/ はそれぞれ「大きい方から小さい方に演…
すごく悩んだけど、なんとか解けた！ 問題へのリンク（仮） 問題概要 次の図のように、木を、文字 (、)、1 からなる文字列で表す（異なる木が同じ文字列になることもある）。文字列の生成規則は次のように表される。 E ::= ‘1’ | ‘(’ E E ‘)’ 詳細は問題文を…
面白かった！ 一見 MST の問題に見えるけど、主客転倒すると Dijkstra だった。 問題へのリンク（仮） 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。頂点 には重み がついていて、辺 には重み がついている。このグラフの全域木のコストを次…
これ面白かった！ ABC-E で出題されて水色 Diff などがあり得そうな雰囲気。 問題へのリンク（仮） 問題概要 正の整数 が与えられる。 以上 以下の整数のうち、popcount が最小のものを求めよ。複数ある場合は、そのうちの最小の整数を求めよ。 制約 考えた…
制約的に でも通るが、スタックを用いて でも解ける！ 問題へのリンク（仮） 問題概要 マスからなるマス目があり、最初各マスには 0 が書かれている。このマス目に対して、以下の操作を行う。 正の整数値 と、連続するいくつかのマスを選ぶ（ただし、どのマ…
グラフの基本問題！ 問題へのリンク 問題概要 の人 がいる。 組の友達関係があって、 組目の友達は人 と である。 人 1 の友達と、人 1 の友達の友達に相当する人 (人 1 を除く) が何人いるかを答えよ。 制約 解法 この問題はグラフの練習問題といえる。グラ…
すごろくを題材にした問題。すごろくの各マスには「oo マス進む」などの指示がある。これを上手に管理しよう。 問題へのリンク 問題概要 マス からなる双六が与えられる。マス 1 がスタート、マス 以上がゴールである。 回サイコロを振って、 回目には目 だ…
ちょっと重たい全探索問題 問題へのリンク 問題概要 の形に配列された二次元文字列 が与えられる。 に対して、次の操作を繰り返すことで に一致させたい。 反時計回りに 90 度回転する (コスト 1) 時計回りに 90 度回転する (コスト 1) 1 マス選んで文字を変…
for 文の練習！ 問題へのリンク 問題概要 個の整数 のうち、最大値と最小値を除外した 個の整数の総和を求めよ。 制約 個の整数はすべて互いに相異なる 解法 まず 個の整数を「配列」として受け取りましょう (C++ では vector<int> 型など)。 その後、配列に対し</int>…
スタックを用いたシミュレーション問題！ 問題へのリンク 問題概要 最初、本は積まれていない。次の 回のクエリに答えよ 【クエリ】 各クエリでは文字列 が与えられる。 が "READ" ではないとき、タイトルが である本が新たに上に積まれる が "READ" である…
多重 for 文の練習！ 問題へのリンク 問題概要 2 つの数列 、 が与えられる。数列 からそれぞれ 1 個ずつ選んでできる 個のペアについて 「その和」と「その最大値」の積 を求めて、それらの総和を求めよ。 制約 考えたこと 2 つの数列からそれぞれ要素をと…
for 文と if 文の練習！ 問題へのリンク 問題概要 文字 J, O, I からなる長さ の文字列 が与えられる。 この文字列において、J を O に、O を I に、I を J に置換した文字列を答えよ。 解法 for 文を用いることで、 の各文字にアクセスすることができる。左…
ちょっとした算数的な考え方が必要になる問題 問題へのリンク 問題概要 JOI 君は以下の行動を行動 A → 行動 B → 行動 A → ⋯ のように交互に繰り返す。 行動 A：3m 前に進む 行動 B：2m 後ろに戻る 行動を合わせて 回行うとき、何m進むか？ 解法 このような問…
とても易しい算数の問題！ 問題へのリンク 問題概要 円もっている。 1 個 5 円の鉛筆を何本買えるか？ 解法 答えは「 を 5 で割った商」となります。これは C++ では A / 5 と書けます。 コード #include <bits/stdc++.h> using namespace std; int main() { int A; cin >> </bits/stdc++.h>…
一見すると計算量が厳しい問題にも見える。ちょっとした発想の転換が必要になる。 問題へのリンク 問題概要 正の整数 が与えられる。次の条件を満たす 個の整数 の組が何個あるかを 100000 で割った値を求めよ。 制約 [tex 1 \le N \le 7] 考えたこと 安直に…
ちょっと実装が重たい。 問題へのリンク 問題概要 グリッドが与えられる。最初、どのマスにもなんらかの色（整数値）がついている。 マス から辺で接しているマスへの移動を繰り返し、マス と色が異なるマスに入ることなく移動できるマスの集まりを、マス の…
「最大値と最小値の差」を最小化せよと言われたら、最大値または最小値を固定すると上手くいくことが多い！ 問題へのリンク 問題概要 サイズが であるような 4 つの数列 が与えられる。 これらの数列から 1 個ずつ要素を選んで とする。 の値の最小値を求め…
ちゃんと証明しようとすると、結構大変！ 問題へのリンク 問題概要 人の生徒がいて、生徒 の身長は である。 これらの生徒を 2 人ずつ 組に分けて、どの組も身長差が 以下となるようにしたい。 そのようなことが可能かどうかを判定せよ。 制約 考えたこと こ…
シミュレーションと呼ばれるジャンルの中では、最も重たい部類の問題 問題へのリンク 問題概要 1 から までの整数の書かれたカードがこの順に並んでいる。このカード列に以下の 回の操作を行う。 回目の操作は、整数 （）によって表される。操作前のカードの…
再帰関数を使った全探索の練習！ こういうのは本当に練習になる。 問題へのリンク 問題概要 各マスが 0 または 1 であるような の二次元グリッド が与えられる。 グリッド上の各マスを渡り歩いていく移動経路のうち、次の条件を満たすものを考える。 1 回の…
ソートの練習問題 問題へのリンク 問題概要 20 個の整数が与えられる。 前半 10 個の整数のうち、大きい順に 3 個の整数の総和 後半 10 個の整数のうち、大きい順に 3 個の整数の総和 をそれぞれ求めよ。 解法 前半ができれば後半も同様なので、前半を考えま…
文字列を左から見ていき、隣接する 2 文字が異なる箇所を見つけるやいなや、マルバツスタンプを使う、という Greedy でよい！ 問題へのリンク 問題概要 マルスタンプ、バツスタンプ、マルバツスタンプの 3 種類がある。 マルスタンプを使うと、文字 'O' を印…
シミュレーションを冷静に実装しよう！ 問題へのリンク 問題概要 マス があって、マス 1 はスタート、マス 2019 はゴールである。 個のコマがあり、それぞれ 番目にマスに置かれている。 次の 回の操作を実行する。 回目の操作ではコマ を動かそうとする も…
結構頭がこんがらがる問題だと思う。 問題へのリンク 問題概要 あるソーシャルゲームでは、1 日につき 1 回までログインすることができ、ログインするたびに 枚のコインが得られる。 さらに、月曜日から日曜日まで 7 日連続でログインすると、そのたびに、追…
