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

hamayanhamayan's blog

競技プログラミング

Tree Separator [JAG Practice Contest for ACM-ICPC Asia Regional 2017 E]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_eN頂点の木がある。 ここから1つのパスを指定して、パスに含まれる頂点と辺を全て取り除く。 できる連結成分の中で良い成分(頂点数がK以上)の個数を最大化せよ。

RPG Maker [JAG Practice Contest for ACM-ICPC Asia Regional 2017 F]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_f縦H,横Wの盤面がある H = 4n-1, W = 4m-1である '@'は始点 '*'は町 '#'は道路 '.'は何もない 始点と町はx,y座標がどちらも偶数番目にある。 現在の盤面は道路が無いので、以下のルールをみた…

Separate String [JAG Practice Contest for ACM-ICPC Asia Regional 2017 H]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_hN個の文字列集合Sがある。 文字列Tもある。 Tを分解して、全て集合Sの要素となるようにする。 何通りの分割方法があるか(mod10^9+7)

Coin Slider [JAG Practice Contest for ACM-ICPC Asia Regional 2017 G]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_gN個の円があり、それぞれ始点(sx[i],sy[i])、終点(tx[i],ty[i])、半径r[i]である。 最初、全て始点にある。 この円を適切な順番で終点に動かす。 動かす過程で他の円と交わってはいけない。 …

Prime-Factor Prime [JAG Practice Contest for ACM-ICPC Asia Regional 2017 C]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_c[L,R]の数で素因数分解したときの素因数の個数(同じ素因数でも重複して数える)が素数の数は何個?

Tournament Chart [JAG Practice Contest for ACM-ICPC Asia Regional 2017 B]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_bトーナメントが文字列で与えられる。 「[左-右]」で与えられる。 次にトーナメントに出てきたN人について、勝利回数が分かっている。 勝利回数が正しいかどうか判定せよ。

Window [JAG Practice Contest for ACM-ICPC Asia Regional 2017 A]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_a縦H横Wの窓がN枚ある。 奇数番目はX[i]だけ右にずらし、偶数番目はX[i]だけ左にずらす。 空いている部分の面積は? Nは偶数である。

Matrix Land [HackerRank Week of Code 35 D]

https://www.hackerrank.com/contests/w35/challenges/matrix-land縦H、横Wの行列Aがある。 この行列上で以下のゲームを行う。 最初は1行目の任意のセルからスタート 1回の操作で左右か下に移動する セルを訪れたら書いてある数をゲットし、ゲットしたら数は…

3D Surface Area [HackerRank Week of Code 35 C]

https://www.hackerrank.com/contests/w35/challenges/3d-surface-area縦H,横Wのエリアがあり、(i,j)には高さA[i][j]の箱が置いてある。 敷き詰めるように置いた時にできる図形の表面積を答えよ。

Triple Recursion [HackerRank Week of Code 35 B]

https://www.hackerrank.com/contests/w35/challenges/triple-recursionN行N列の行列aがあり、以下のルールでこの行列を埋めていく。 i=0かつj=0なら a[i][j] = M i=jなら a[i][j] = a[i -1][j - 1] + K i>jなら a[i][j] = a[i - 1][j] - 1 i<jなら a[i][j…

Lucky Purchase [HackerRank Week of Code 35 A]

https://www.hackerrank.com/contests/w35/challenges/lucky-purchaseN個の名前と値段が付いた商品がある。 この中で以下の条件を満たす商品名を答えよ。 値段を文字列として見た時に、4と7の個数が同じ 値段を文字列として見た時に、4と7だけで構成されてい…

Skiing [CodeChef November Cook-Off 2017 C]

https://www.codechef.com/COOK88/problems/SKIINGH(=N)行W(=M)列の行列Aがある。 「A[y][x] := 座標(x,y)の高さ」である。 現在(x,y)にいる時、移動できるのは高さが同じか低い隣り合った座標である。 ここで、座標集合Sを定義する。 全ての座標に座標集合…

Online Chess [CodeChef November Cook-Off 2017 B]

https://www.codechef.com/COOK88/problems/ONCHESSN人のプレイヤーが順番に待ち行列に入る。 i番目のプレイヤーは レートがR[i] 対戦相手のレートはMin[i]~Max[i]を希望 対戦時間はT[i]を希望 レート変化はisRated[i]を希望 色はColor[i]を希望 というパラ…

Random Pair [CodeChef November Cook-Off 2017 A]

https://www.codechef.com/COOK88/problems/RNDPAIRN個の配列Aがある。 この配列に対しi<jである(i,j)の全ての組合せのA[i]+A[j]の最大を取る。 ここからランダムにi<Jである(i,j)を取って、最大となる確率を求めよ。

BuffaloBuffaloBuffalo [SRM723 Div1 Med]

文字列Sがあり、一部'?'となっている。 ある文字列がgoodであるとは、その文字列から部分文字列として"buffalo"を抜き出していくと、全ての文字が抜き出せる文字列である。 '?'を任意の文字列に変えてgoodな文字列を作りたい。何通りあるか(mod10^9+7)

TopXorer [SRM723 Div1 Easy]

N個の配列Aがある。 ここから、0≦B[i]≦A[i]を満たすようにN個の配列Bを作る。 B[0] xor B[1] xor ... xor B[N-1]の最大値は?

Wall [AtCoder Beginner Contest 079 D]

https://abc079.contest.atcoder.jp/tasks/abc079_d

Train Ticket [AtCoder Beginner Contest 079 C]

https://abc079.contest.atcoder.jp/tasks/abc079_c

Pride [Codeforces Round #446 Div1 A]

http://codeforces.com/contest/891/problem/AN個の配列Aがある。 「並んだ2つの要素(x,y)のどちらかをgcd(A[x],A[y])にする」という操作をする。 全ての要素を1にするための操作の最小回数は?

Restoration of string [Codeforces Round #445 Div1 B]

http://codeforces.com/contest/889/problem/BN個の文字列がある。 この文字列に対して、以下の条件を満たす文字列を構築せよ。 全ての部分列について、出現回数を考える その中で出現回数が最大の部分文字列を全て集めると与えられた文字列を全て含む集合と…

Chef and Subarray Queries [CodeChef November Challenge 2017 F]

https://www.codechef.com/NOV17/problems/CSUBQN個の配列Aがあり、以下のクエリに答える。 「1 x y」 x番目の要素をyにする 「2 l r」 部分列[l,r]の中の任意の部分列の最大値が[L,R]である組み合わせ数を答える

Chef Hates Palindromes [CodeChef November Challenge 2017 D]

https://www.codechef.com/NOV17/problems/CHEFHPAL以下を満たす、N文字の文字列を構築する。 A種類の文字からなる(小さい方から順に使う) 回分である任意の部分文字列の長さが最小 回分である任意の部分文字列の長さの最小値と共に答えよ

Periodic Palindrome Construction [CodeChef November Challenge 2017 C]

https://www.codechef.com/NOV17/problems/PERPALIN以下の条件を満たす長さNの文字列を構築せよ。 無理なら"impossible" 'a'と'b'の両方の文字から成る(どちらかはダメ) 全体として回文である i番目と(i-P)番目の文字が等しい

Chef goes Left Right Left [CodeChef November Challenge 2017 B]

https://www.codechef.com/NOV17/problems/CLRLN人いる。i番目の人のレートはA[i]である。 最後の人は自分で、レートはRである。 N人で順番に二分探索のようなことをする。 i番目より大きいならば、左に。 小さいならば、右に移る。 矛盾するならNO,矛盾しな…

Villages and Tribes [CodeChef November Challenge 2017 A]

https://www.codechef.com/NOV17/problems/VILTRIBE N文字の'A','B','.'からナなる文字列がある。 AはAの領地、BはBの領地である。 それ以外は、Aに挟まれていればAの領地、Bに挟まれていればBの領地となる。 Aの総領地、Bの総領地数を答えよ。A..A..B...B -…

Petya and Catacombs [Codeforces Round #445 Div1 A]

http://codeforces.com/contest/889/problem/AN+1個の配列Tがある。 T[0] = 0で他は与えられている。 この時、以下の条件を満たす配列Aを構築する。 N + 1個の要素から成る 全てのiについて i あるiについてA[i] = A[j]を満たす最大のjがあるなら、T[i] = j…

登山 [yukicoder No.595]

https://yukicoder.me/problems/no/595

ABS [AtCoder Regular Contest 085 D]

https://beta.atcoder.jp/contests/arc085/tasks/arc085_b

HSI [AtCoder Regular Contest 085 C]

https://beta.atcoder.jp/contests/arc085/tasks/arc085_a

壊れた宝物発見機 [yukicoder No.594]

https://yukicoder.me/problems/no/594