問題 https://yukicoder.me/problems/no/741 10進数表示をしたときに桁が昇順に並んでいる数字を AscNumber とする。 10N 未満の AscNumber がいくつあるか求めよ。 考え方 [0, 9] の数字から重複を許して N 個選んだ時の数を昇順に並べると1つの AscNumber …

問題 題材は以下の問題です。 https://codeforces.com/contest/1047/problem/C 概要 ある数 を素因数分解をするとき、通常は までの素数で順に割ればよい。これは計算量 で求めることができる。 今回の場合は、配列 に含まれる のすべての数について素因数分…

問題 長さ 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 マスにしか影響を及ぼさない。 よって影…

問題 https://beta.atcoder.jp/contests/abc107/tasks/arc101_a 数直線上に N つの点が与えられる。今地点 0 にいる。数直線上の点から K 個選ぶとき、移動距離の最小値を求めよ。 考え方 (i)正負に分けて全探索 最短距離を動くときの点の選び方は正の方向か…

問題 https://beta.atcoder.jp/contests/abc003/tasks/abc003_4 制約 1 <= R, C <= 30 1 <= X <= R, 1 <= Y <= C 0 <= D, L, 1 <= D, L <= X * Y 考え方 包除原理である。まず、R * C から X * Y の長方形のとり方を求める。次に X * Y の長方形に D + L 個…

JavaのMapを使うときにValueの降順で取り出したい時。 Map<Integer, Integer> map = new HashMap<>(); List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet()); Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() { @Override public int compare(Entry</map.entry<integer,></map.entry<integer,></map.entry<integer,></integer,>

問題 https://beta.atcoder.jp/contests/abc106/tasks/abc106_d M つの区間 [l_i, r_i] が与えられる。またクエリが Q つ与えられる。以下のクエリの数を求めよ。 クエリ 2つの数 [p_i, q_i] に完全に含まれる (p_i <= l_j かつ r_j <= q_i) 区間の個数を求…

問題 https://beta.atcoder.jp/contests/abc024/tasks/abc024_d タテ、ヨコ マスある方眼紙上で頂点 から頂点 への経路が 通りで与えられる。この時 の組み合わせを求めよ。 考え方 グリッドグラフ上で頂点 から への経路数は で与えられる。 同様に から へ…

問題 https://beta.atcoder.jp/contests/dwacon2017-prelims/tasks/dwango2017qual_b 0から9と?で構成される文字列 s が与えられる。?を好きな数字に変えることで25の繰り返しのみで構成される s の部分文字列 s' の最大の長さを求めよ。 考え方 貪欲法では…

問題 https://beta.atcoder.jp/contests/soundhound2018/tasks/soundhound2018_c 縦 r 、横 c の r × c のグリッドがあたえられる。グリッドのマスは * か . で構成される。.のマスに広告を打つが上下左右に隣り合うように広告は打てない。広告を打つ最大数…

問題 https://beta.atcoder.jp/contests/abc044/tasks/arc060_b 整数 に対して 進数の桁和 が与えられる。 を満たすような最小の を求めよ。 制約 考え方 が大きいので単純に全探索はできない。そこで で場合分けする。 (i) の場合 この場合は で全探索が可…

問題 https://beta.atcoder.jp/contests/abc105/tasks/abc105_d 数列 が与えられる。閉区間 の和が の倍数になる区間の個数を求めよ。 考え方 の累積和を とする。これが の倍数になる時 と が の倍数でなければなりません。よって の累積和をとり、 であま…

問題 https://beta.atcoder.jp/contests/abc105/tasks/abc105_c 整数 が与えられる。 の 進数表現を求めよ。 考え方 考え方は通常の 進数を求める方法と同じだが、操作をちゃんと理解していないと実装でバグります。通常の 進数(今回は 進数とします) の求め…

問題 https://beta.atcoder.jp/contests/abc104/tasks/abc104_d 長さ の文字列 が与えられる。 のうち つ文字を選んだときに左から となっている組み合わせの数を求めよ。 制約 考え方 場合の数である。文字を つ選ぶときに真ん中の を固定して数え上げるこ…

問題 https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_d rev(x) := x を 10 進表記してできる文字列を反転したものを 10 進表記に持つ整数を表す。 正の整数 N, M について 1 <= x <= N, 1 <= y <= M なる (x, y) について、以下の操作…

問題 https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_c N 行 M 列のマス目がある。(i, j) は '.' or '#' である。あるマスに上下左右のいずれかの方向を向いたロボットをおく。ロボットは直進し、あるマスで右折した後直進することが…

問題 https://beta.atcoder.jp/contests/abc066/tasks/arc077_b 考え方 同じ数で場合分けする。同じ数を左から a_l, a_r とする。 k 個選ぶときの選び方について考える。 (i)同じ数を0個選ぶ場合 n-1 個の数から k 個選ぶ場合の場合の数 n-1 C k (ii)同じ数…