問題記録

AtCoder Regular Contest 090: F - Number of Digits

https://atcoder.jp/contests/arc090/tasks/arc090_d 問題概要 正整数nに対してf(n)をnの10進表記での桁数と定義する。与えられる整数Sに対してf(l)+f(l+1)+...+f(r)=Sを満たすような(l, r)の組が何通り存在するか求めよ。 S <= 108 解法 まず桁数が少しでも…

Codeforces Round #562 (Div. 1) : B. Good Triple

https://codeforces.com/contest/1168/problem/B 問題概要 各文字が0または1のどちらかからなる長さNの文字列Sが与えられる。1 <= l <= r <= N を満たす整数の組(l, r)のうち、Sの区間[l, r]の中に同じ文字が3文字以上等間隔で並んでいるものの数を求めよ。 …

Educational Codeforces Round 64: D. 0-1-Tree

https://codeforces.com/problemset/problem/1156/D 問題概要 N頂点の木が与えられる。木の各辺は0または1のコストを持つ。単純パスで、かつ辺が「0個以上の0コスト辺」→「0個以上の1コスト辺」の順序で並んでいるパスをvalidと呼ぶ。頂点x->yへの単純パスが…

AtCoder Regular Contest 040: D - カクカク塗り

https://atcoder.jp/contests/arc040/tasks/arc040_d 問題概要 N行N列のグリッドが与えられる。グリッドの各マスは床もしくは障害物である。指定されたマスからスタートして「現在の向きに直進し、90度どちらかに向きを変える」という操作を繰り返してすべて…

京都大学プログラミングコンテスト2012 practice: D - A mul B Problem

https://atcoder.jp/contests/kupc2012pr/tasks/kupc2012pr_4 問題概要 N行N列の行列A, B, Cが与えられる。AB = Cであるか判定せよ。 N <= 1000 解法 普通に掛け算するとO(N3)だが、検算だけなら各要素が0か1をランダムでとるN要素のベクトルrを使って ABr =…

早稲田大学プログラミングコンテスト2019: F - RPG

https://atcoder.jp/contests/wupc2019/tasks/wupc2019_f 問題概要 N頂点M辺の有向無閉路グラフが与えられる。グラフの各頂点は必ず「戦闘」もしくは「空き地」のいずれかに分類される。また空き地の頂点iには整数のコストCiを支払うことで回復所を設置する…

CPSCO2019 Session3: F - Flexible Permutation

https://atcoder.jp/contests/cpsco2019-s3/tasks/cpsco2019_s3_f 問題概要 1~Nの順列Pのうち Pi > i であるような i がA個 Pi < i であるような i がB個 Pi = i であるような i がN - A - B個 という条件をすべて満たすものが何通りあるか求めよ。 N <= 3…

CPSCO2019 Session1: F - Fruits in Season

https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_f 問題概要 N個の果物があり、これを1日目からN日目まで毎日ひとつずつ食べていく。i番目の果物はj日目に食べるとAi-abs(j-ti)×Biの満足度が得られる。またある順番で果物を食べたとき、全体の…

いろはちゃんコンテスト Day2: F - 総入れ替え

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_f 問題概要 箱が3つあり、それぞれの箱には100円玉がA1枚、B1枚、C1枚、50円玉がA2枚、B2枚、C2枚入っている。コインが1枚以上入っている箱をひとつ指定して、そこからランダムにコインを1…

AtCoder Regular Contest 027: D - ぴょんぴょんトレーニング

https://atcoder.jp/contests/arc027/tasks/arc027_4 問題概要 N個の石が一直線に並んでおり、石x からは 1 ~ Hx 個先のどれかの石にジャンプすることができる。以下の形式のクエリがD個飛んでくるのでそれぞれに解答せよ。 整数s, t (s < t) が与えられる…

AtCoder Regular Contest 045: D - みんな仲良し高橋君

https://atcoder.jp/contests/arc045/tasks/arc045_d 問題概要 整数Nと、XY平面上の(2N+1)個の点が与えられる。各点はX座標またはY座標が同じ他の1点とペアになることができる。ただしすでにペアをつくっている点が他の点とペアになることはできない。すべて…

Aizu Online Judge 2710: Marked Ancestor

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2170 問題概要 N頂点の木とQ個のクエリが与えられる。木は常に頂点1が根である。また初めは頂点1だけにマークがされている。クエリにはMとQの2種類があり、Mクエリでは指定された頂点にマークを付…

AtCoder Regular Contest 084: F - XorShift

https://atcoder.jp/contests/arc084/tasks/arc084_d 問題概要 N個の非負整数Aiが黒板に書かれている。黒板に書いてある数に対して「数をひとつ選びそれを2倍したものを黒板に書き足す」「数をふたつ選びそれらのbitwise xorをとったものを黒板に書き足す」…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選: D - チップ・ストーリー ~黄金編~

https://atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_d 問題概要 1以上1012以下の秘密の整数Nがある。Nをi進数で表したときの各桁の数字の和Ai (i = 2〜30) がそれぞれ与えられるので、条件を満たすNが存在するか判定せよ。存在する場合にはその…

AtCoder Grand Contest 025: D - Choosing Points

https://atcoder.jp/contests/agc025/tasks/agc025_d 問題概要 正整数N, D1, D2が与えられる。xy平面上で 0 <= x < 2N, 0 <= y < 2N に存在する整数座標の点の集合であって、要素数がN2個でありかつ集合の中のどの2点を取ってもその2点の距離がsqrt(D1)でもs…

全国統一プログラミング王決定戦予選 / NIKKEI Programming Contest 2019: E - Weights on Vertices and Edges

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_e 問題概要 N頂点M辺の連結な無向グラフが与えられる。グラフの各頂点と各辺には重みが設定されている。辺をひとつ選んでグラフから削除するという操作を何回でも行えるとき、削除されて…

AtCoder Grand Contest 016: D - XOR Replace

https://atcoder.jp/contests/agc016/tasks/agc016_d 問題概要 長さNの数列A, Bが与えられる。Aの要素をひとつ選びその値をAのすべての要素のXORで置き換えるという操作を好きなだけ行えるとき、AをBに一致させることができるか判定せよ。また可能な場合には…

AtCoder Regular Contest 041: D - 辺彩色

https://atcoder.jp/contests/arc041/tasks/arc041_d 問題概要 N頂点M辺の無向グラフが与えられる。このグラフの各辺を以下のルールに従って赤か青のどちらかで塗っていくとき、各辺を初めに指定されている色で塗ることができるか判定せよ。 ルール: 自由に…

AtCoder Regular Contest 020: D - お菓子の国の旅行

https://atcoder.jp/contests/arc020/tasks/arc020_4 問題概要 N個の町があり、隣り合う町同士は道で結ばれている。町iと町(i+1)を結ぶ距離はDiとして与えられる。いまN個の町からK個の町を選び順に移動していくことを考える。このとき訪れる町に重複があっ…

AtCoder Regular Contest 004: D - 表現の自由 ( Freedom of expression )

https://atcoder.jp/contests/arc004/tasks/arc004_4 問題概要 整数N, Mが与えられる。NをM個の整数の積として表す方法が何通りあるか求めよ。構成要素が同じでも並び順が異なればそれぞれ1通りとして数えるものとする。 |N| <= 109 M <= 105 解法 掛け算の…

AtCoder Regular Contest 039: D - 旅行会社高橋君

https://atcoder.jp/contests/arc039/tasks/arc039_d 問題概要 N頂点M辺の無向グラフとQ個の旅行計画が与えられる。各旅行計画は始点、中継点、終点をあらわす頂点の組(A, B, C)からなる。各旅行計画について、一度も同じ辺を通ることなく始点→中継点→終点と…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦: D - DISCO!

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d 問題概要 どの文字もDISCOの5文字のうちいずれか1文字であるような文字列Sが与えられる。この文字列に対する以下のQ個の問に答えよ。 問: Sの区間[l, r]の範囲内で長さ5の部分文字列(連…

DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦: C - グラフいじり

https://atcoder.jp/contests/ddcc2017-final/tasks/ddcc2017_final_c 問題概要 N頂点M辺の強連結な重み付き有向グラフが与えられる。ひとつの辺の重みを自由に変更できるとき、グラフのすべての単純サイクルについて、サイクル内に含まれる辺の重みの和が0…

Educational DP Contest / DP まとめコンテスト: W - Intervals

https://atcoder.jp/contests/dp/tasks/dp_w 問題概要 '0'と'1'のみからなる長さNの文字列を考える。M個のスコア条件(l, r, a)が与えられたとき、文字列の区間[l, r]のうち少なくとも1文字が'1'であればa点を得る。文字列を自由に構成できるとき、スコアの最…

Educational DP Contest / DP まとめコンテスト: T - Permutation

https://atcoder.jp/contests/dp/tasks/dp_t 問題概要 整数Nと長さN-1の文字列Sが与えられる。Sは'>'と'<'のみからなり、長さNの数列における隣り合う値の大小関係を表す。(1, 2, ..., N)のすべての順列のうちSの表す大小関係に従うものは何通りあるか。 N <…

CODE FESTIVAL 2016 Final: F - Road of the King

https://atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_f 問題概要 N個の町があり、これらの間にはひとつも道が存在しない。はじめ王様は町1におり、今いる町からN個の町のどれかへ移動することをM回繰り返す(移動元と移動先は同じで…

AtCoder Grand Contest 028: C - Min Cost Cycle

https://atcoder.jp/contests/agc028/tasks/agc028_c 問題概要 N頂点の有向グラフがあり、各頂点iは2つの値Ai, Biを持っている。このグラフはすべての点対x, yに対して辺x->yが存在し、その重みはmin(Ax, By)である。グラフのすべての頂点をちょうど1回ずつ…

Codeforces Hello 2019: D. Makoto and a Blackboard

https://codeforces.com/contest/1097/problem/D 問題概要 整数N, Kが与えられる。Nの約数のうちひとつを等確率で選び、それでNを割る、という操作をK回繰り返すとき、最終的なNの値の期待値を求めよ。 N <= 1015 K <= 104 解法 Nの約数の数は最大ケースで30…

NJPC2017: G - 交換法則

https://atcoder.jp/contests/njpc2017/tasks/njpc2017_g 問題概要 2つの文字列に対する演算子@が次のとおり定義される。 s@t = min(s,t) + max(s,t) ここで+は結合を表し、max/minは辞書順比較での大小を表す。文字列Sが与えられたとき、その文字列を1文字…

CODE FESTIVAL 2018 Final: G - Chicks and Cages

https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_g 問題概要 N羽のひよこがいて、ひよこiの大きさはAiである。ひよこをM個のケージに分けて入れるとき、各ひよこは自分とおなじケージにいるひよこの大きさの和と…