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として与えられる。すべての文字列は自分の左にある文字列より辞書順で真に小さい、という制約のもとで、そのような文字列の列が存在する…

https://yukicoder.me/problems/no/765 問題概要 文字列Sが与えられる。Sから任意の1文字を削除するとき、削除後の文字列において回文となる最長連続部分文字列の長さを求めよ。 |S| <= 2 * 105 解法 回文の中心となる場所を総当たりしていく。最終的な回文…

https://yukicoder.me/problems/no/776 問題概要 N要素の数列Aに対して以下の2種類のクエリがQ個飛んでくるので順次処理せよ。 set(i, x): Ai の値を x に変更する。 max(l1, l2, r1, r2): l1 <= l <= l2, r1 <= r <= r2, l <= r を満たすすべての整数の組l,…

https://yukicoder.me/problems/no/719 問題概要 2〜Nの数の集合から、「どの相異なる2つの要素を取り出してもそれらは互いに素である」という条件を満たすように部分集合を作る。このような部分集合のうち、要素の合計が最大になるときの値を求めよ。 2 <= …

https://beta.atcoder.jp/contests/kupc2018/tasks/kupc2018_f 問題概要 N枚のカードを使って2人ゲームをする。先手と後手はそれぞれのターンに残っているカードから任意の1枚を選んで手持ちに加える。このときカードに書いてある数値を得点として得る。また…

https://beta.atcoder.jp/contests/arc083/tasks/arc083_d 問題概要 2次元平面上に2N個のロボットと2N個のボールがある。ロボットはx軸上のx座標1〜Nの箇所にN個、y軸上のy座標1〜Nの箇所にN個それぞれ設置されている。x軸上のロボットは起動されるとx=a上に…

https://beta.atcoder.jp/contests/arc071/tasks/arc071_d 問題概要 整数Nが与えられたとき、以下の性質をすべて満たす数列が何通りあるか求めよ。 数列は無限長で、各要素は1〜Nのいずれかの整数である 数列の第N項以降はすべて同じ値である 数列のある要素…

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_d 問題概要 自分の家が座標0, オフィスが座標Dにあり、N個のガソリンスタンドの座標が数列Xで与えられる。車の燃料タンクの容量がFで距離1の移動に燃料を1消費す…

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_c 問題概要 N要素の数列Aが与えられる。数列の要素をひとつ選び2で割る、という操作をちょうどK回行ったあと、残った数列としてありえるものが何通りあるか求め…

今まで新卒で入った会社でプログラミングとは全然関係なく事務職をやってたんですが、そこを辞めて競プロア〜が多いと噂の会社でプログラマーをすることになりました。転職活動ではかなり競プロの経験を生かせたと思う（というか生かせそうなところに応募し…

https://beta.atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_a 問題概要 N×Mのグリッドの各マスに対して「着色されたマスが縦・横・斜めで隣り合わない」かつ「最低1マスは着色されている」という条件のもと色を塗るとき、何通りの塗り方…

https://beta.atcoder.jp/contests/tenka1-2016-qualb/tasks/tenka1_2016_qualB_d 問題概要 N要素の数列a1, a2, .., aNに対してA個の加算クエリとB個の調査クエリが与えられるので順次処理せよ。 加算クエリ: 数列の区間[L, R]にXを加算する 調査クエリ: S回…

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_e 問題概要 長さNの文字列がM個与えられる。それらに対するQ個のクエリを順次処理せよ。 swapクエリ: x番目の文字列とy番目の文字列の、l番目からr番…

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_d 問題概要 N頂点0辺の無向グラフに対してQ個のクエリが飛んでくるので順次処理せよ。 addクエリ: 頂点u, v間に辺を張る completeクエリ: 「頂点u」…

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_c 問題概要 N頂点の無向グラフで、頂点に1からNまでの番号がついており、自己辺・多重辺を持たず、すべての辺の長さを1としたとき頂点1-2間の最短距…

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_b 問題概要 N要素の数列Aが与えられる。Aの中から連続するK個の要素を選んでその値を全て0にするという操作を何度でも行えるとき、最終的なAの全要素…

http://codeforces.com/contest/1010/problem/D 問題概要 N頂点の根付き木が与えられる。すべての葉にはあらかじめ1か0の入力が与えられており、葉以外の頂点はすべて「子から来たビットを入力として論理演算をし、その出力を親に送る」機能を持っている。演…

https://beta.atcoder.jp/contests/arc097/tasks/arc097_d 問題概要 N頂点の木が与えられる。木の各頂点には白か黒どちらかの色がついている。任意の頂点からスタートし、以下の2種類の動作を任意の順序で繰り返すとき、すべての頂点の色を黒にするために必…

https://beta.atcoder.jp/contests/arc079/tasks/arc079_d 問題概要 N頂点N辺の弱連結有向グラフが与えられる。すべての頂点にそれぞれひとつの非負整数aiを割り当てることを考える。「ある頂点uから伸びる有向辺(u, v)でuと繋がっているすべての頂点vに割り…

https://beta.atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_e 問題概要 N頂点M辺の単純連結無向グラフが与えられる。辺iには整数siが設定されている。すべての頂点にある整数を割り当てるとき、すべての辺において「辺…

https://beta.atcoder.jp/contests/agc012/tasks/agc012_d 問題概要 N個のボールが一列に並んでおり、各ボールには色と重さが設定されている。色が同じで合計の重さがX以下のボール2つの位置を入れ替える操作と、色が異なって合計の重さがY以下のボール2つの…

https://yukicoder.me/problems/no/95 問題概要 N頂点M辺の無向グラフが与えられる。グラフの頂点には0～(N-1)の番号が付いている。はじめプレイヤーは頂点0にいて、一度の移動で一辺で繋がれた2頂点間を移動できる。また頂点nをはじめて訪れたとき(2n - 1)…

https://beta.atcoder.jp/contests/arc093/tasks/arc093_c 問題概要 N頂点M辺のグラフが与えられる。各辺にはコストがある。すべての辺をそれぞれ白か黒かで塗り分けるとき、以下の条件が満たされるような塗り方は何通りあるか。条件：「白の辺も黒の辺も少…

問題概要 N軒の焼肉屋が横一直線に並んでおり、それぞれの間の距離は数列Aで表される。またM枚のチケットを1枚ずつ持っており、チケットjを焼肉屋iがある地点で使うことでB(i, j)の幸福度を得ることができる。好きな地点からスタートして自由に移動してチケ…