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個のケージに分けて入れるとき、各ひよこは自分とおなじケージにいるひよこの大きさの和と…

SoundHound Inc. Programming Contest 2018 (春): C - 広告

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

AtCoder Grand Contest 029: C - Lexicographic constraints

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

yukicoder No.765 ukuku 2

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

yukicoder No.776 A Simple RMQ Problem

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,…

yukicoder No.719 Coprime

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

Kyoto University Programming Contest 2018: F - カード集め

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

AtCoder Regular Contest 083: F - Collecting Balls

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上に…

AtCoder Regular Contest 071: F - Infinite Sequence

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

CODE FESTIVAL 2018 qual A: D - 通勤

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

CODE FESTIVAL 2018 qual A: C - 半分

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

仕事やめ彦・せん蔵

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

天下一プログラマーコンテスト2013 決勝: A - 天下一有無

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