POJ 1949. Chores

その他

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

2015-05-27

Codeforces 547A. Mike and Frog

こどふぉす

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

2015-05-25

素因数関係の列挙

勉強

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

2015-05-23

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が最小とな…

2015-05-23

Codeforces 538D. Weird Chess

こどふぉす

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

2015-05-23

ARC038 C. 茶碗と豆

その他過去問

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

2015-05-17

ARC039 D. 旅行会社高橋君

その他

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

2015-05-17

ARC039 C.幼稚園児高橋君

その他

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

2015-05-11

GCJ2015 Round1C B.Typewriter Monkey

その他過去問

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

2015-05-10

google code jam 2015 Round1C

その他その他

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

2015-05-10

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は素数)が成り立つ(中国…