問題 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)同じ数…