661.1

久し振りにしっかりした問題だった。 250 整数Nが与えられるので、N+1からKまでの整数の最小公倍数と1からKまでの整数の最小公倍数が一致する最小のKを答えよ、という問題。 1からNまでの整数のうち各素数で割り切る最大回数を求めて、それが次に出てくる位…

660.1

めんどうなことをやるだけでは、次につながる気がしない。 250 二次元平面上に二点選んで、それぞれから相対位置が指定された値にある点群の重みの合計値を最大化せよ、という問題。 作業。 500 ランダムにpermutationを選んで、それぞれの値について、それ…

GCJ 2015 Round 2

例年に比べると簡単な気がする。 A 二次元盤面上に矢印が書いてあって、その方向に進まないといけない。どの矢印を開始点にしても、無限に移動し続けられるように、矢印の向きを変えるとき、最小いくつ変更する必要があるか答えよ、という問題。 取り敢えず…

659.1

あってなきがごとしな問題はどうなんだろう? 250 二種類のものを並べるときに、一方のものが直近のK個の中にK/2個以下になるようにしたい。(もう一方はどうでもいい。)一方のものの配置が一部固定されているので、最大の個数を答えよ、という問題。 もし一…

658.1

やる気がないと成績も悪い。 300 各点間の距離の偶奇が与えられるので、そのような木が存在するならばどれか一つ答えよ、という問題。 やるだけ。とにかく、偶奇が一致する相手とは一致するし、一致しない相手とは一致しない。後は、偶と奇のそれぞれ代表を…

657.1

出題者性格悪いなぁ。 250 三人組を作りたいが、役割がそれぞれあって、どれができる人がどれだけ、みたいな感じで指定されるので、最大何グループ作れるか答えよ、という問題。 愚直に条件を満たす割り当てが可能かバイナリサーチするだけ。条件が間違うと…

2015 Round 1A

起きたら終わっていました。 A とあるものを減らす人と増やす人がいる。増やす人は好き勝手に増やす。減らす人も好き勝手に減らす場合、少なくともいくつ減らしたか、また、減らす人は常に同じペースで減らしたとする場合、少なくともいくつ減らしたか、をそ…

656.1

世間の人と価値観が違いすぎるのかも知れない。 250 N個のものからランダムに1個選ぶ操作を繰り返していく。前のよりもindexが後ろのを選んだら失敗で終了。このとき、選んだもののスコアの合計値の期待値を答えよ、という問題。 普通にメモ付き探索するだけ…

655.1

適度にやる気なくしていたら、比較的いい問題がきた。 250 N*Nの盤面をK*Kの区画を塗る操作を延々と繰り返して、目的の塗り方にできるか答えよ、という問題。 とにかくK*Kの同じ色の区画があれば、そこをそう塗る前はどんな状態でもいいので、そんな感じで一…

654.1

本当に飽きてしまった...。 250 文字列の一部が伏せられていて、特定の文字である確率が与えられる。部分文字列が全部同じ文字からなるものの個数の期待値を答えよ、という問題。 実装やるだけ。やっただけ。 450 整数配列が与えられるので、二つの連続領域…

653.1

ちゃんとした問題が出ても解けない。 250 同じ数字がその数字の数だけ並んでいるのを結合して作られた整数配列がある。一部が伏せられているので、元の数列を復元できるか答えよ、という問題。 適当に探索して複数通りにならないのを確認すれば良さそう。探…

652.1

もうダメかも知らんね...。 250 1からNまでの整数の最小公倍数を求めよ、という問題。 サンプルが間違っていました。 500 スタートからゴールまでの移動コストの最小値を答えよ、という問題。ただし途中K回ほど邪魔が入る可能性があって、邪魔されると一番ひ…

651.1

眠いので途中だけれど、メモして去ります。 250 縦横移動に相当する操作列を与えたときに、それぞれが無視される可能性がある状況で、盤面の外に出ないような最長操作列の長さを答えよ、という問題。 要は現在位置から盤面の外に出ない四方向のそれぞれの距…

650.1

純粋につまらないから人が減っている?悪循環ですかね? 250 AとBのどちらかからなる文字列の指定された位置がAかBか与えられるので、できるだけ同じ文字が連続しないようにするとき、何通りできるか答えよ、という問題。 取り敢えず、交互に並べるのが良い…

649.1

思考に椅子が必要なのかな?とは思っています。 250 指定された文字列から、任意のK文字を除去したときの結果がユニークになるか答えよ、という問題。 連続するK+1文字の中に同じ文字が2個以上あればダメ、という風に置き換わる。後はやるだけ。 550 整数配…

648.1

実装大変でしたね。 250 AとBからなる文字列のうち、文字数がNで、Aの後にBがくるというインデックスの組がK個の文字列を答えよ、という問題。 愚直に探索するのがいいと思うけれど、まずはAとBが半分ずつある文字列を作って、適当に隣接するA,Bをスワップし…

647.1

本当に最近つまらないのでやめたい。でもやめると二度とやらない気がするので、義務として続けている感じ。 250 初期値が0で各ステップで高々1だけ値を変更して良い。指定されたステップでの値が指定された値以下になるように注意しつつ、Nステップ操作を繰…

646.1

配点詐欺。問題は簡単なのにそれが解けない原因は明らかに自分が劣化しているからだとは思う。 250 整数配列が与えられるので、適当に増減させて連続なK個の整数を作るとき、何回増減させる必要があるか答えよ、という問題。 取り敢えずどこか一個固定して、…

645.1

前回はなかった。 250 区間が与えられて、隣接グラフができるので、それの最小点被覆問題のような気がする。 要は開始と終了があるので、接しているどれか一つを選ぶと接しているのも選ばれたことになるから、全体を選ぶように最小に選ぼうという問題。 区間…

643.1

貪欲に貪欲を出し続ける出題者...。 250 でかい素数が与えられて、部分的に素因数分解の結果が与えられるので、残りを復元せよ、という問題。 部分的に分かっているので割ってから、素因数分解するだけでいいらしい。やたらと大きい数が出てくる場合に、どこ…

642.1

問題が枯渇しているからつまらないのかも知れないけれど、今日のは出題者の悪意しか感じない。 250 N個のものを確率に従って抽選するという操作を延々と繰り返す。抽選結果に応じて、次の抽選までの時間が決まる。抽選を開始した時刻から経過した時刻が与え…

641.1

最近の問題はつまらない。多分情熱が冷めたんでしょうね。 250 点が適当に与えられるので、原点を中に含む三角形になるような点の選び方は何通りか答えよ、という問題。 適当に角度でソートして、180度よりも大きくならない範囲で選択してやればいいらしい。…

640.1

変なセット? 250 グラフが与えられるので、ツリーになっている部分グラフの、枝の重みの合計値の最小値を答えよ、という問題。 枝の重みでソートして、適当にMST作るだけのような気がする。 550 二部グラフの右側の点の数と左側の点の数と、最大マッチング…

640.1

変なセット? 250 グラフが与えられるので、ツリーになっている部分グラフの、枝の重みの合計値の最小値を答えよ、という問題。 枝の重みでソートして、適当にMST作るだけのような気がする。 550 二部グラフの右側の点の数と左側の点の数と、最大マッチング…

639.1

TopCoderってこんなにつまらなかったっけ?(出題センス的な意味で) 250 1,3,5,7,9,...を二人に分けたときの、合計値として正しいか答えよ、という問題。正しいときには、一人目はいくつの数字を割り当てられているか、その可能な最小値を答えよ、という問題…

638.1

Adminは問題の難易度をもう少しまじめに把握した方が良いと思う。 300 N*N*Nの領域に1*1*1のキューブが適当に連結に詰んである。各方面から見たときに、見える見えないの情報が与えられるので、そんな積み方は可能か答えよ、という問題。 取り敢えず明らかに…

637.1

実装大変な問題。 250 1から2Nまでの整数をN個ずつ二人に分ける。自分の持っている整数が分かっていて、相手がどういう風に並べているかも部分的に分かる。自分の持ってる整数を並び替えて、相手の並べている整数と順番に比較して、大きくなる回数をできるだ…

636.1

500が解けるか解けないか。 250 2次元テーブルに整数値が入っているので、矩形領域の和を高速に求める下準備をしなさい、という問題。 やるだけ。コピペの人が多いんだろうな。 500 二次元平面上に、ランダムにK個の点を配置して、一番近い点同士に辺をはっ…

635.1

めんどくさい... 250 折れ線が与えられるので、一部オーバーラップしてもいいので、二つの部分折れ線を見比べたとき、相似形になっているもので、一番長いものを答えよ、という問題。 愚直にやるだけ。一部だけ傾き見ていると、全体として相似形じゃなくなる…

634.1

なんかめんどくさいだけに見えた。 250 商品の買われた個数が与えられる。それぞれの人が高々一個しか各商品について購入していない。N人の人がいるとき、K個以上の商品を購入した人の数の最小値を答えよ、という問題。 K個以上買った人は全部一個ずつ買った…