ひっこします

http://phyllo-algo.hatenablog.com/読みやすさを意識します。

GCJ2016 Round1B C.Technobabble

問題 N個の単語ペアが与えられる。ペアは前側と後ろ側の単語と区別する。 これは、N人が順番に、前側、後ろ側どちらかがそれまでその側で使われていない新しい単語を使って作られるようにしたはずのものである。 しかし、fakerと呼ばれる人はそれまで出てた…

SRM669 div1 250

解答に必要なことを一つも考えつけてなかったorz 最適分割の部分の理解が怪しいが、理解したと思う範囲でまとめておく。 問題 体積Sのスライムがある。 1回の操作で、今あるスライムの塊を一つ選んで、2つに分解することができる。 このとき、体積Aのスライ…

Codeforces 582A. GCD Table

問題 ある長さNの配列a_iがあったとき、この配列自体は与えられず、代わりにgcd(a_i,a_j)の結果N*N個が与えられる。 元の配列に含まれる数値を答える。 1 a_i 考え方 与えられたgcd(a_i,a_j)の中で、一番大きい数をMとする。 gcd(M,M)=Mであるので、少なくと…

CODE FESTIVAL 予選A D.壊れた電車

問題 N車両の電車をM人で点検する。最初、i番目の人はXi車両目にいる。 点検には時間がかからないが、隣の車両への移動には1分かかる。 すべての車両を少なくとも1人が点検した状態にするのにかかる時間は最低何分か? 1 1 考え方 Nが大きいので、車両の状態…

ABC029 D. 1

問題 1からNまでの数字をすべて書き出したとき、「1」は何回書いたか? 1 考え方 愚直に数えると、O(N*桁数)かかってしまって間に合わない。 以下、1からではなく、0から考えても問題ない。 桁DP 最大桁から考える。 ここで、Nが3桁「xyz」であると仮定する…

Codeforces 580D. Kefa and Diches

問題 N種の料理からM種を順番に選んで食べる。 このとき、各料理自体の満足度の他に、料理iの直後に料理jを食べた場合の追加満足度もある。 満足度の最大値を求める。 1 0 0 考え方 N種からM種選んで、その順番を列挙する方法だと、O(2^18 * 18!)で間に合わ…

Codeforces 578B. "Or" Game

問題 n個の整数a_iが与えられる。 高々k回、整数xを整数a_iから一つ選んでかける、という操作を行える。 各整数のORをとったものa_1 | a_2 | ・・・| a_nの最大値はいくつになるか? 1 1 2 0 考え方 直感的に、xが2以上なので、x^kをかけた方が最大bitを更新…

Codeforces 578A. A Problem about Polyline

問題 (0,0)->(x,x)->(2x,0)->(3x,x)->・・・のようなぎざぎざした線を考える。 今、整数点(a,b)をこの直線が通る事がわかっている。 可能なxの中で最小のものを返す。なければ-1を返す。1 考え方 まず、y軸の方は0からxまでしか変化し得ないので、b以上でな…

Codeforces 577B. Modulo Sum

div2Bのレベルなの・・・? 問題 n個の要素からなる数列aと整数mが与えられる。 空でない部分列の和がmで割り切れるような部分列があるかチェックし、あるならYES、ないならNOを返す。1 2 0 考え方 各a_iはmod mを取っておいても問題ない。なので、問題は「0…

SRM462 div1 250

問題 バス停からn台のバスが確率的に選ばれて1台だけ出発し、そのバスが戻ってくるまで他のバスは出発できない。 バスiは、戻ってくるまでtime[i]時間だけかかる。また、バスiはprob[i]/100の確率で選ばれる。 バス停に時刻sで訪れた時にバスの出発までに待…

SRM500 div1 250

英語の読解力が低い・・・ 問題 N人でマフィアというゲームを行う。 各ターン、N人全員が「弱いと思われる候補者」に投票し、投票数が最大の人が1人ならばその人が負ける。 投票数が最大の人が複数人いる場合、その人たちを「弱いと思われる候補者」の対象と…

yukicoder No.23 技の選択

問題 体力がHのモンスターを倒したい。 毎ターン、通常攻撃と必殺技攻撃ができ、 ・通常攻撃の場合は、必ずAのダメージ ・必殺技攻撃の場合は、1/3で失敗し0ダメージ、2/3でDのダメージ を与えられる。 モンスターを倒すのに、攻撃の回数の期待値が最小とな…

Codeforces 550A. Two Substrings

A問題で簡単だと思って油断すると、怪しいケースを見逃したりするので注意。 問題 長さがnの文字列sが与えられる。 「AB」と「BA」の2つの文字列が部分文字列としてオーバーラップしないように含まれるか?を確認し、含まれるならYES、そうでないならNOを返…

SRM660 div1 250

むずい 問題 n*mのセルに0〜9の数字が書かれている。 あるセル(i,j)を選んだ時、p個の(i+x[k],j+y[k])に書かれている数字をすべて抽出し、その合計を得られる。(範囲外は0を抽出) 今、ある2つの異なるセルを選び、同じセルから1回のみ抽出できる場合、合計値…

SRM660 div2 500

問題 N人の友達をパーティーに招待する。 しかし、友だちiは友だちA[i]が嫌いなので、もし先にパーティーに招待されていたら来ない。 (嫌いな人がいない場合はA[i]=iとなっている) 呼べる友達が最大になるような順番で友達を招待したら、何人の友達を呼ぶこ…

SRM660 div2 1000

問題 整数n,k,mが与えられる。 Σ_{i=1}^n {i^(2^k-1)}を求めよ。 1 1 2 考え方 i^(2^k-1)を考える。 k=400まであるので、愚直な方法では桁あふれしてしまう。 2^k-1というのは、ビットレベルで考えると2^kはk+1ビット目だけ立っていて、2^k-1は1ビット目〜k…

TCO2015 Round2A 300. MODMODMOD

半分以上が赤で、日本人も激強の3人がいる圧倒的威圧感の部屋で、がんばって解いたのにunratedでツラい。ratedになった。 問題 要素がN個の配列mが与えられる。 ここで、f(x)=(((x mod m[0]) mod m[1]) ... mod m[N-1])とするとき、f(1)+...+f(R)の値を求め…

POJ 1949. Chores

問題 仕事がN個ある。しかし、K番目の仕事は、1〜K-1番目の仕事に0個以上依存しており、前の仕事がすべて終わっていないと手を付けられない。 各仕事にかかる時間とK番目の仕事が依存している仕事番号のリストが与えられるので、すべての仕事が終わるまでに…

Codeforces 547A. Mike and Frog

大虐殺と聞いて。解法は教えてもらった。ムズすぎでは・・・ 問題 高さh1のカエルと高さh2の花があり、1秒後にはカエルは高さが(x1*h1+y1) mod M、花は(x2*h2+y2) mod Mになる。 カエルの高さがa1、花の高さがa2に同時になるような最短時間を求めよ。そのよ…

素因数関係の列挙

今日、「素因数の総数の列挙がエラトステネスの篩の計算量程度に抑えられている」という話題がでて、混乱したので、メモ。 問題 1〜Nまでのすべての整数に対して素因数に関するなんらかの数の列挙を行うこと。 素数の列挙 整数xの相異なる素因数の個数の列挙…

ABC024 D. 動的計画法

問題 10^8*10^8マスにmod (10^9+7)を取ったパスカルの三角形が書かれている。 今、(r,c)と(r,c+1)と(r+1,c)に書かれている数字A,B,Cがそれぞれ与えられる。 rとcのうち、10^8-1未満となるrとcで、rが最小となるもの、かつ、同じrで複数ある場合はcが最小とな…

Codeforces 538D. Weird Chess

問題 N*Nのチェス盤にコマをいくつか置く。 コマは(x,y)に居る時、(x+dx[i],y+dy[i])の地点に攻撃する。 今、コマの位置と攻撃された地点の情報が与えられるので、矛盾のないdx[i],dy[i]を返す。 作れない場合はNOを返す。複数答えがある場合はどれか一つ返…

ARC038 C. 茶碗と豆

問題 N個の茶碗が並んでおり、茶碗iには豆がA[i]個と、整数C[i]が書かれている。 ただし、C[0]は書かれておらず、A[0]=0。2人のプレイヤーが豆を一つ選んで、その豆が入っている茶碗iから、茶碗(i-1)〜(i-C[i])のどれかに移す、ということを繰り返す。茶碗0…

ARC039 D. 旅行会社高橋君

問題 N頂点、M辺からなる無向グラフが与えられる。(多重辺や自己ループはなし) Q個の「同じ辺を通らず、頂点aから頂点bを通って頂点cに行くことができるか?」のクエリがくるので、それに答える。 N M Q 各クエリのa,b,cは互いに異なる 考え方 行くことがで…

ARC039 C.幼稚園児高橋君

問題 二次元格子の原点からスタートし、上下左右に移動するときは、各方向に移動して最初の未訪問格子点まで動く、という動作を繰り返す。 K回分の上下左右どちらに動いたか?の情報が与えられるので、最終的な格子点の座標を答える。 K 解いた方法 愚直にシ…

GCJ2015 Round1C B.Typewriter Monkey

問題 猿がK個のキー(同じ文字が存在するかもしれない)をS回押す。同じキーを何回も押すかもしれない。 押した順番に文字を並べた長さSの文字列ができあがるが、この中に、長さLの文字列Tが含まれる個数だけバナナを上げることにしている。 バナナは必要最低…

google code jam 2015 Round1C

今年は突破ならず・・・ oo o- x- 44pt 1335位 A. Brattle ship 問題 R*Cのマスがあり、1*Wの戦艦のマスをすべて言い当てるゲームをしている。 自分は戦艦の場所を見ることができず、言ったマスに戦艦があるかどうかを知ることができる。 ところが、見られな…

SRM657 div2 1000

問題 整数a,b,cが与えられたとき、(a*x^2+b*x+c) mod 10^9 = 0となる整数xを返す。 ただし、0 0 考え方 法Mが合成数の場合、「f(x)=n mod M」は、Mを素因数分解した場合「f(x)=n mod p^a」「f(x)=n mod q^b」(M=(p^a)*(q^b)*..., p,qは素数)が成り立つ(中国…

GCJ2015 Round1C C.Less Money, More Problems

問題 D種類の異なる金額を表すコインがある。 各種、C枚までしか使うことができない。 1〜Vまでの金額をすべて払えるようにしたい。 あと最低何種類追加すればすべて払えるようにできるか? T Small C=1, 1 Large 1 考え方 全探索(small) 与えられたD種コイ…