読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

たくさんの数式 / Many Formulas [ARC 061, ABC 045 C]

問題 http://arc061.contest.atcoder.jp/tasks/arc061_a'1'~'9'から成る文字列Sがある。 この文字列に'+'を入れて正しい数式を作る。 全ての考えられる入れて作られる数式に対して和を取り、その総和を答えよ。1

しろくろチョコレート [yukicoder 421]

問題 http://yukicoder.me/problems/no/421N行M列の板チョコが与えられる この板チョコは黒チョコと白チョコが交互に市松模様状に並んでいる 以下のようにチョコを食べる1. 任意の位置からチョコを1つ選んで食べる -> 幸福度1 2. 任意の位置から黒チョコと白…

Teleporter [AGC 004 : D]

問題 http://agc004.contest.atcoder.jp/tasks/agc004_d町1~Nがある。 町1は首都。 どの町にもテレポータが1つあり、町iから町a[i]へテレポートできる。 どの町から出発してもテレポートをちょうどK回すると首都につけるようにテレポートの行き先を変える。…

AND Grid [AGC 004 : C]

問題 http://agc004.contest.atcoder.jp/tasks/agc004_c縦H横Wの透明な方眼紙が2つある。 片方は赤色で、もう片方は青色で、どちらも連結な状態で塗られている。 これら2つの重ね合わせるとどちらも塗られている所が紫色になる。 重ねあわせて紫色になってい…

Colorful Slimes [AGC 004 : B]

問題 http://agc004.contest.atcoder.jp/tasks/agc004_bN色のスライムがいる。 この時、2種類の操作を選んで行う。 飼っていない色iのスライムを選んで飼う。a[i]秒かかる 全ての飼っているスライムの色iが色i+1になる。x秒かかる 2 1

Similarity of Subtrees [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : E]

問題 http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_eS(T,d)をある木Tの深さdであるノードの個数とする。 木Tと木T'が類似しているとは、全てのdにおいてS(T,d)=S(T',d)であること。この時、ある木が与えられる。 この木の部分木のうち、類…

Parentheses [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : D]

問題 http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_d「(」と「)」から構成された文字列があり、以下の条件を満たす文字列を答えよ A回隣接する文字をスワップすると括弧の対応が取れた文字列が作れる B( 複数回答があれば、その中で文字列…

Help the Princess! [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : B]

問題 http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_b縦H,横Wの地図がある。 @ : 姫の初期位置 $ : 兵士の初期位置 % : ゴール . : 通路 # : 壁 各ステップ、姫と兵士は隣接する通路に1マスだけ進むかその場にとどまるか選択できる。 姫と…

Best Matched Pair [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : A]

問題 http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_aN個の数列がある。 これから2つ選んで積をとる。 その中で、文字列として見た時に、連続で増加している積の中で最大のものは? 連続で増加している例))2, 23, 56789 連続で増加してい…

高橋くんとホテル / Tak and Hotels [ARC 060 : E]

問題 http://arc060.contest.atcoder.jp/tasks/arc060_cN軒のホテルがある。 i軒目のホテルはx[i]の位置にある。 以下の条件を満たして移動する。 1日の移動距離はL以下 1日の終わりには必ずホテルにいる この時、Q個の以下のクエリが与えられる。 a[i]番目…

Chris and Magic Square [Codeforces 369 : Div2 B]

問題 http://codeforces.com/contest/711/problem/Bn×nの魔法陣がある。 魔法陣の数は自然数だが、1つだけ0になっており不完全である。 0に何を入れれば魔法陣として完成するか。 完成が不可能なら-1を出力せよ1

Directed Roads [Codeforces 369 : Div2 D]

問題 http://codeforces.com/contest/711/problem/Dn頂点の有向グラフがある。 全ての頂点から1本ずつ有向辺が出ている。 有向辺をひっくり返す組合せは2^n通りあるが、このうち、ループが無い組合せは何通り? 10^9+7を法として答えよ。2

Coloring Trees [Codeforces 369 : Div2 C]

問題 http://codeforces.com/contest/711/problem/Cn本の木がある。 これらの木をm種類の色で塗る。 木iは色C[i]で塗られているが、一部(C[i]=0のもの)は色が塗られていない。 塗られていない木に色を塗っていくのだが、木iに色jを塗るときはp[i][j]のインク…

Bus to Udayland [Codeforces 369 : Div2 A]

問題 http://codeforces.com/contest/711/problem/An行4列のバスの座席表がある。 'O'が空席、'X'が予約済み。 横に2つ並んで席が取れるか出力せよ。 なお、4列だが(2列)(道)(2列)であり、道をまたがっていると並んでいると言わない。 取れるなら、そこを'+'…

天下一魔力発電 [天下一プログラマーコンテスト2016 予選B : B]

問題 http://tenka1-2016-qualb.contest.atcoder.jp/tasks/tenka1_2016_qualB_b'('と')'から成る文字列Sがある。 カーソルは文字列の先頭から始まる。 以下の3つの処理が行えるとき、文字列Sを括弧の対応が取れた状態にする最小手数を答えよ。1. カーソルを…

チューリップバブル [yukicoder 417]

問題 http://yukicoder.me/problems/no/417頂点0~N-1から成る木がある 頂点iでU[i]の税収が得られる 各辺を通るときはC[i][j]時間かかる 頂点0からスタートして、辺を通って頂点を周り、頂点0に戻ってくる 全体にかかる時間がM時間以下での最大の税収を答え…

桁和 / Digit Sum [ABC 044, ARC 060 : D]

問題 http://arc060.contest.atcoder.jp/tasks/arc060_bf(b,n)がある n < b のとき f(b,n) = n n ≧ b のとき f(b,n) = f(b, floor(n / b)) + (n mod b) この関数はnをb進数表記したときの各桁の総和を返す関数とも言える f(B,N)=Sとなる2以上の最小のBを答…

高橋君とカード / Tak and Cards [ABC 044, ARC 060 : C]

問題 http://arc060.contest.atcoder.jp/tasks/arc060_aN枚の数が書かれたカードがある。 ここから1枚以上のカード選んで数の平均がAとなる組合せは何通り?1 1 1

旅行会社 [yukicoder 416]

問題 http://yukicoder.me/problems/no/416N頂点、M辺の無向グラフがある。 これからQ回のイベントを順に処理する。 1つのイベントで頂点Ciと頂点Diを結ぶ辺が壊される。この時、何回目のイベントで頂点1から頂点iまでが連結じゃなくなったかを出力せよ。 た…

BBuBBBlesort! [AGC 003 : C]

問題 http://agc003.contest.atcoder.jp/tasks/agc003_cN要素の数列がある。 これを2種の方法で要素を入れ替えて昇順ソートする 操作1 : 隣り合う2つの要素を選んで入れ替える 操作2 : 1つ飛ばしの2つの要素を選んで入れ替える 操作2の回数は何回でもいい。 …

Pythagorean Triples [Codeforces 368 : Div2 C]

問題 http://codeforces.com/contest/707/problem/C三辺が自然数の直角三角形の斜辺ではない辺の長さxがある。 この直角三角形の他の二辺を求めよ。1

Vasiliy's Multiset [Codeforces 367 : Div2 D]

問題 http://codeforces.com/contest/706/problem/D多重集合Aがあり、0が入っている。 これに対して、q個の以下のクエリを処理せよ。1. "+ x" Aにxを入れる 2. "- x" Aからxを消す 3. "? x" Aから1つ選んだ要素yについて、xとyのXORの最大値を出力1 1

Hard problem [Codeforces 367 : Div2 C]

問題 http://codeforces.com/contest/706/problem/Cn個の文字列が順に与えられる。 n個の文字列が辞書順昇順となるようにしたい。 各文字列はコストciで反転させることができる。 辞書順昇順とするための最小コストを求めよ。 辞書順昇順とできないなら"-1"…

DivisibleSetDiv1 [SRM 697 : Easy]

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14362n要素の配列bが与えられる この時、以下の条件を満たすn要素の配列aが存在するか判定せよ 全ての要素はバラバラ(distinct)である 全ての要素は1より大きい a[i]^b[i]はp[i]で割り切…

キャンディーとN人の子供 [ARC059 : E]

問題 http://arc059.contest.atcoder.jp/tasks/arc059_c(複雑なのでリンク先を見ましょう) (結構分かりにくい)1

アンバランス [ARC059 : D]

問題 http://arc059.contest.atcoder.jp/tasks/arc059_b文字列tの連続する部分文字列のうち、アンバランスな文字列があるか判定する。 あるなら、その部分文字列を(要素番号で)示せアンバランスな文字列とは以下の条件を満たす文字列 長さが2以上 文字のう…

昇順昇順ソート [yukicoder 411]

問題 http://yukicoder.me/problems/no/411正の整数 N, K がある。 1~Nが1つずつあるN個の数列はN!通りあるが、その中で以下の条件を満たす組合せを数える 数列の先頭がK 数列について Ai > Ai+1 となるiがただ1つだけある 2 1

花火大会 [yukicoder 412]

問題 http://yukicoder.me/problems/no/412自然数B, C, Dがある。 N個の数列Eiもある。 Eiの部分集合は2^N通りあるが、「その中でB 1 1 1

Clicounting [SRM 696 : Div1 Mid]

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14340n頂点の単純無向グラフがある。 この単純無向グラフの辺のうち、k個の辺が有るかどうか分からない。 この辺の有無によって、2^k通りのグラフの組合せがある。 その全ての組合せについ…

Gperm [SRM 696 : Div1 Easy]

問題 https://community.topcoder.com/stat?c=problem_statement&pm=143600~49でラベル付けされた50頂点の無向グラフがある。 このグラフ上で、任意の順番で頂点に色付けをする。 色付けをする度に両端が色付けされている辺の個数がコストとして発生する。 …

Thor [Codeforces 366 : Div2 C, Div1 A]

問題 http://codeforces.com/contest/705/problem/Cn種類のアプリがあるスマホがある。 時系列順でq個のクエリが与えられる。 各クエリの処理後、未読の通知は何個あるかそれぞれ答える。クエリは以下の3種ある。 1. アプリ x が通知を出す 2. これより前に…

Spider Man [Codeforces 366 : Div.2 B]

問題 http://codeforces.com/contest/705/problem/Bn個の数列 ai が与えられる。 n個のクエリについて答える。 各i番目のクエリで以下のゲームを行う。1. 場に a0 ~ ai があり、1さんが先手 2. 自分の番が来たら、場にある数のうち1つを2つの数に分割する 3…

Hulk [Codeforces 366 : Div2 A]

問題 http://codeforces.com/contest/705/problem/An = 1 : "I hate it" n = 2 : "I hate that I love it" n = 3 : "I hate that I love that I hate it" のようにnが増えるたびにhateとloveを繰り返して出力せよ1

五輪ピック [yukicoder 408]

問題 http://yukicoder.me/problems/no/408N頂点、M辺の単純無向グラフがある。 各頂点には1からNの番号がついている。 このグラフ上で頂点1を含む長さ5の単純閉路があれば"YES"、なければ"NO"2 0

鴨等素数間隔列の数え上げ [yukicoder 407]

問題 http://yukicoder.me/problems/no/407自然数 N, L が与えられる。 このとき、以下の条件を満たす数列の組合せを数えよ。 要素Nの数列 x0, x1, ... xN-1 0 隣り合う数の差が全て等しく、その差は素数である 3 1

Mishka and trip [Codeforces 365 : B]

問題 http://codeforces.com/contest/703/problem/Bn個の都市があり、そのうちk個が首都である 首都間は以下のルールで辺が作られる 隣り合う都市間には辺がある。都市iと都市i+1間には辺がある(都市nと都市1間にもある) 首都は全ての頂点間と辺がある 都…

Mishka and Game [Codeforces 365 : A]

問題 http://codeforces.com/contest/703/problem/An回の勝負の結果 mi,ci が与えられる。 この時、 mi > ci ならば、この勝負は"Mishka"の勝ち mi = ci ならば、引き分け mi n回やって、勝った数の多い方の名前を出力せよ。 引き分けなら、"Friendship is m…

Knot Puzzle [AGC 002 : C]

問題 N本のロープがあり、結び目で順に繋がれている。 ロープiの長さはai。 ここで、一繋がりになっているロープのうち、長さがL以上のものを選び、つなぎ目を取る。 この処理を繰り返して、全ての結び目が解けるか。 解けるなら、"Possible"とほどく順番を…

Box and Ball [AGC 002 : B]

問題 http://agc002.contest.atcoder.jp/tasks/agc002_bN個の箱がある。 1番目の箱には赤ボール1つ、他の箱には白ボール1つがそれぞれ入っている。 M回、xi番目からyi番目に適当にボールを1つ移す。 全ての操作を終えた後、赤いボールが入っている可能性があ…

Range Product [AGC 002 : A]

問題 http://agc002.contest.atcoder.jp/tasks/agc002_aa -10^9

Cellular Network [Codeforces 教育15 : C]

問題 http://codeforces.com/contest/702/problem/C直線上にn個の街とm個の基地局がある。 基地局が全ての街をカバーするための基地局の最小の半径rは?1 各座標 [-10^9, 10^9]

Powers of Two [Codeforces 教育15 : B]

問題 http://codeforces.com/contest/702/problem/Bn個の数aiがある。 ここから2つ選んだ和が2の累乗である組合せは何通りか1 1

Maximum Increase [Codeforces 教育15 : A]

問題 http://codeforces.com/contest/702/problem/An個の数列がある。 この数列の中で「連続の」増加列の最大の長さは?1

グラフィカルグラフ [天下一プログラマーコンテスト2016予選A : D]

問題 http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualD_aN頂点の木がある。 頂点0から順にA,B,...とラベルづけ。 与えられた木を以下のように視覚的に表示せよ。 8 12 ............ ...D...E.... ...|...|.... .C-A---B---F .|.....|..…

山田山本問題 [天下一プログラマーコンテスト2016予選A : C]

問題 http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualC_aN個の文字列の組AiとBiが与えられる。 辞書順で Ai のほうが Bi よりも小さいようにアルファベット順を変えたい。 全ての文字列について、辞書順が満たされるようなアルファベッ…

PackDrop [天下一プログラマーコンテスト2016予選A : B]

問題 http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualB_aN頂点の木がある。 根は頂点0。 この木に対して、辺にコストをつける。 M個の葉について、根から葉までのパスの辺のコストの総和が指定されている。 このとき、辺につけるコスト…

As Fast As Possible [Codeforces 364 : Div2 D, Div1 B]

問題 http://codeforces.com/contest/701/problem/Dn人の生徒がいて、距離lを移動する。 生徒が普通に移動すると速さv1。 バスを使って移動すると速さv2。 各生徒バスには1回しか乗らない。 バスは一度にk人しか乗せられない。 バスをうまく使ったとき、n人…

They Are Everywhere [Codeforces 364 : Div2 C, Div1 A]

問題 http://codeforces.com/contest/701/problem/Cn文字の文字列がある。 これの連続する部分文字列の中で(元の文字列について)全種類の文字が含まれている文字列の中で最小の文字列長は?1

Cells Not Under Attack [Codeforces 364 : Div2 B]

問題 http://codeforces.com/contest/701/problem/Bn×nのチェス盤がある。 ここに m 個のルークを置く。 ルークは縦横を攻撃できる。 ルークが1個目から順番に置かれていく。 ルークが1個目からi個目まで置かれたとき、盤面の中で攻撃されないマスをそれぞれ…

Cards [Codeforces 364 : Div2 A]

問題 http://codeforces.com/contest/701/problem/An枚の数が書かれたカードがある。 n/2人のプレイヤーが2枚ずつとる。 各プレイヤーがもつカードの和が等しくなるにはどのように取ればよいか。2 1