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

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

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

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

https://atcoder.jp/contests/dwacon2017-honsen/tasks/dwango2017final_b 問題概要 N要素の正整数の数列Xが与えられる。Q個の区間[L, R]が与えられるので、それぞれについて「その区間に含まれるすべてのXの要素の積をとったとき、その数の約数は何個か」と…

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

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

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

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

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

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