問題 長さ n の文字列 s が与えられる。以下の条件を満たす n 頂点の木を構築することができるかどうか。 頂点 s_i の文字が 1 であれば、木から辺を 1 つ取り除いて、長さ i の連結成分を作ることができる 頂点 s_i の文字が 0 であれば、木から辺を 1 つ取…

問題 とするとき、 を求めよ。 制約 考え方 まず数を 進数の桁ごとに分けて考える。 たとえば で であるが、これは ビット目と ビット目で のそれぞれで を足せばよい。 さて、求めたいのは := n までの数で ビット目が である数の総和 として、 である。 の…

問題 正整数 K が与えられる。K の倍数の集合の中で桁和が最小になるとき、その桁和を求めよ。 考え方 任意の正整数は 1 からはじめて、 操作 ある数 t に +1 する ある数 t に × 10 する を繰り返し適応することで求められる。上記の操作をするとき +1 する…

解いた問題を振り返ります。 A.In Search of an Easy Problem 問題概要 Problem - A - Codeforces 0 または 1 である n 個の文字列が与えられる。 1 つでも 1 が存在する場合は "HARD" をそうでない場合は "EASY" を出力せよ。 考え方 問題概要の指定された…

問題 正整数 が与えられる。 となる a の数列が何通りあるか求めよ。 考え方 例として とする。 まずは を素因数分解をする。それぞれの因数ごとに独立して考えることができる。因数ごとのべき乗の数がポイントである。 を x x x x のような つのマスに配る…

問題 文字列 S, T が与えられる。S のうち、異なる 2 つの英小文字 c1, c2 を選んで swap させる。 0 回以上 swap させて文字列 S を T にすることができるかどうは判定せよ。 考え方 文字の変更先は一意に定まる。同じ文字からは同じ文字にしか変更できない…

問題 https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_c [a, b] の数から 0 個以上の要素を選んで集合 S とする。集合 S に含まれる要素はそれぞれ互いに素である。このような集合 S は何通りあるか？ 考え方 以下の 2 つ考えられ…

問題 http://codeforces.com/contest/1042/problem/D 数列 a_n が与えられる。[l, r] の区間和が t 未満になる区間の数を求めよ。 考え方 まず、数列の連続する区間和は累積和の 2 点で求められます。 今、求めるべき区間はある 2 点 i, j (i < j) について …

問題 https://yukicoder.me/problems/no/141 数学問題。以下のいずれかの操作ができるとき、 1 から m/n にするまでにかかる操作の最小回数を求めよ。 操作 1. a を a+1 にする 2. a を 1/a にする 考え方 逆から考えていく。すなわち以下の操作ができるとす…

雑多に書いていく予定です。 一般 最終的な状態を考えて逆算する とても基本的な考え方です。 自分で小さなケースのサンプルをつくって実験する 必要条件で絞り込む D - アンバランス / Unbalanced D - Forest E - Tr/ee なにかを決め打ち (して探索) する …

問題 https://beta.atcoder.jp/contests/abc109/tasks/abc109_d の 次元グリッドが与えられる。各 には のある数が書かれている。以下の操作を繰り返すことで、グリッド上にある数字で偶数のマスの数を最大化するような構築手順を求めよ。 操作 まだ選んでい…

問題 人いる( は偶数)。この中から 人組のペアを作る時、ペアの組み合わせは何通りあるか？ 考え方 (i)ペアの 人を固定 人の中からまず 人固定する。その 人に対して、ペアになる人の選び方は 通り存在する。同様に残りの 人の中から 人を固定して、その 人…

問題 https://beta.atcoder.jp/contests/agc001/tasks/agc001_b 正三角形上に光を当てて、反射するときの距離の問題 考え方 以下の図のように光のがどのように進むか法則性がわかると見通しがよい。 光の始点を A とする。この光は C で反射し点 B へ進む。…

問題 https://beta.atcoder.jp/contests/abc045/tasks/arc061_b 考え方 黒く塗る点は N 個しかないので、 N 個の点に着目する。 3 * 3 のマスに含まれる数を数えるとき、ある黒く塗る点 (i, j) は自身を含めて周囲 9 マスにしか影響を及ぼさない。 よって影…