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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

https://atcoder.jp/contests/soundhound2018/tasks/soundhound2018_c 問題概要 各マスが '*' もしくは '.' で構成されたr行c列のグリッドが与えられる。'.'のマスに広告を打てるが、広告を打ったマスの上下左右4マスには広告を打つことができなくなる。最大…

https://atcoder.jp/contests/agc029/tasks/agc029_c 問題概要 N個の文字列が順番に並んでおり、それぞれの長さが数列Aとして与えられる。すべての文字列は自分の左にある文字列より辞書順で真に小さい、という制約のもとで、そのような文字列の列が存在する…