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

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

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

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

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

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

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

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

問題 N頂点からなる、辺の重みが1の連結な木が与えられる。 M個のA,Bが与えられ、「頂点AとBから同じ距離に位置する頂点の個数」をそれぞれ返す。N M 考え方 任意の木では、個数の数え上げが難しいので、頂点1をルートとする根付き木にしておく。 考察すると…

問題 a〜zの26個のアルファベットの重みが与えられる。 ある文字列が与えられたとき、長さ1以上の部分文字列で「両端のアルファベットが同じ」かつ「両端を除いたアルファベットの重みの和が0」であるようなものがいくつあるか？ 10^5 文字列の長さ 考え方 …

問題 今、N人のプロとM人の初心者がいる。 3人でチームを作る際、(プロ、プロ、初心者)か(プロ、初心者、初心者)であるように作らなければならない。 何チーム作れるか？0 考え方 それぞれ(プロ、プロ、初心者)がAチーム、(プロ、初心者、初心者)がBチームで…

問題 n個の数字が与えられ、それからどこれか1つの数字を除いたn-1個の数字、さらに、それからどれか1つの数字を除いたn-2個の数字が与えられる。 それぞれ、なんの数字が抜かれたか？を返す。 考え方 n個の数字の合計値を求めておけば、n-1個の数字の合計値…

問題 いくつかのコマが配置されたチェス盤が与えられる。 各コマには重みが与えられており、各プレイヤーごとの重みの合計値が高いほうのプレイヤー名(White/Black)を返す。同点の場合はDrawを返す。 考え方 数えるだけ。 が、入力をよく見ると、knightの場…

http://d.hatena.ne.jp/phyllo_algo/20150215/1423985061Codeforces 514のD問題をかなり微妙な解法で通ってしまっていたけど、テストケースが35個ぐらいでそんなに悪意のあるケースがないためたまたま通ってしまっているようにも思われる。 http://kmjp.hate…

問題 無限に頂点がある根付きn分木が与えられる。 ある親頂点について、子頂点はn個あるが、それぞれ左からd[i]の重みになっている。 今、「根から頂点jまでの距離=根から頂点までの最短ルートの重みの和」とする。 距離xが与えられるので、距離がx以下であ…

問題 N台のロボットが1列に並べてあり、各ロボットはM種類の精密機械で構成されている。 各精密機械は何個か積まれており、ロボットiのj番目の精密機械はk個(a[i][j]=k)という情報が与えられる。 今、特殊な兵器によって、1回につき、すべてのロボットについ…

問題 a,b,cの3文字からなる、n個の文字列が与えられる。 次に、a,b,cの3文字からなる、m個の文字列が一つずつ与えられたとき、n個の文字列で以下の条件を満たす文字列がある場合YES、なければNOを返す。 ・同じ長さの文字列である ・ちょうど1つの文字が異な…

問題 leading zeroを許さないn桁の整数x(>0)を考える。 以下の条件を満たすxは何個存在するか？ 「y mod k = 0となるy(>0)が、整数xのsuffixになっている」 答えをmod mで答える。n k m 考え方 条件を満たすxを考えるため、suffix候補のb桁のyを考えてみる。…

問題 n個の非負の整数a1,a2,...,anが与えられる。 これを2^a1,2^a2,...と書き直して総和を求める。 これに2^b(b>=0)形式のものをいくつか加えて、その総和が2^{v}-1(vは任意)になるようにしたい。 いくつ加えればよいか。 1 0 考え方 各ビットで考えられる。…

問題 n個まで連分数展開されたa0+1/(a1+1/...)の配列aと、分数p/qが与えられる。 この連分数展開されたものと分数p/qが等しいかどうかを返す。1 1 考え方 多倍長があれば、それを使って連分数をpp/qq形式に直して、pp*q == qq*pかどうかを判定。 または、p/q…

問題 非負で100以下の異なる整数がいくつか与えられる。 このとき、「任意のペアが、それらの各桁について少なくとも0を含む」ようにサブセットを作る。 2つの整数を同時に、1の位、10の位、100の位で見て、どちらかが0になるようにする。サブセットは満たす…

最後に参加したのがMayとかなってた。。。半年以上やってなかった。

予選落ち。507位、、、orz

いい勉強になった。0点。 基本的に英語の読解スピードが遅く、正確性が低くて悲しい。

問題 文字列strが与えられる。さらに、いくつか文字列boring[i]が与えられる。 文字列strの部分文字列の中で、boring[i]が含まれない最長の文字列の長さとその最初の文字の場所を答える。 考え方 しゃくとりっぽくやる。部分文字列の最初の位置begと最後+1の…

久しぶりすぎる参加。Div.1のレートが上がってしまったので、またDiv.2に。。

問題 ノミがn個の円状になっている草むらを時計回りで飛んでいる。このノミは時刻kのときには、現在位置からk-1個先の草むらへ飛ぶ。このとき、ノミはn個すべての草むらにまわることができるか。 考え方 nが少ないので、適当にシミュレーションするだけ。 な…

A. Flea travel 解けた。 modの世界。10^6回ぐらい回してみればいいかな。提出。 いやいやいやいや、不安すぎる。10^8回ぐらい回した結果と違う結果になるものを探してみる。おわらない。YESになるやつだけ出力してみる。1,2,4,8,16,...なるほど。再提出。 B…

頭痛がひどかったけど参加。

久しぶりの参加。