661.1
久し振りにしっかりした問題だった。
250
整数Nが与えられるので、N+1からKまでの整数の最小公倍数と1からKまでの整数の最小公倍数が一致する最小のKを答えよ、という問題。
1からNまでの整数のうち各素数で割り切る最大回数を求めて、それが次に出てくる位置を覚えておく。その位置の一番大きいのが答え。
450
N個のノードのあるグラフを考える。色がK色塗ってあって、各ノードは自分よりも番号が若くて色の違うノードに対して枝をはることができるし、はらなくても良い。このとき、可能なグラフは何パターンあるか答えよ、という問題。
良く分かっていないけれども、二色の場合は階乗になるし、三色の場合は奇数のみの階乗になるし、という感じで、一般化すると、色の数-1飛ばしの階乗になる模様。後はmodを取るので、ループするまで頑張る感じ。
多分数学的には有名な何かなんだろうなぁ、とは思います。
1000
一列にノードが並んだグラフが二つ与えられるので、同じ番号のノードをマージする操作を高々K回やってよいので、全二点間の距離の最大値を最小化せよ、という問題。
良く分からないけれど、頑張ればDPみたくできるのだろうか？
660.1
めんどうなことをやるだけでは、次につながる気がしない。
250
二次元平面上に二点選んで、それぞれから相対位置が指定された値にある点群の重みの合計値を最大化せよ、という問題。
作業。
500
ランダムにpermutationを選んで、それぞれの値について、それよりも前に指定された値がある場合は除去するという操作を行って、最終的に残る要素数の期待値を答えよ、という問題。
多分独立に計算できるはず。自分の前にあってはまずいのが前にいる場合、何通りあって、そいつの前にそいつの前にいちゃまずいヤツがいれば自分は生き残る、みたいなのを適当に反転させながら探索していけば良さそう。状態数は多いのでメモしていく感じで。
1000
見てない。
GCJ 2015 Round 2
例年に比べると簡単な気がする。
A
二次元盤面上に矢印が書いてあって、その方向に進まないといけない。どの矢印を開始点にしても、無限に移動し続けられるように、矢印の向きを変えるとき、最小いくつ変更する必要があるか答えよ、という問題。
取り敢えず、矢印の先に矢印があれば、その矢印は放置しても良さそう。なので、矢印の先に矢印がないなら、適当に向きを変える必要がある。後は、変えた数をカウントするだけ。矢印がなければできない。
B
特定の温度で、特定の量の水がいくらかある。これらを好きなように混ぜて、できるだけ多くの目的の温度の水にしたい。そのときの量を答えよ、という問題。
温度はキープしないといけないので、既にその温度なら好きに使える。温度が違うなら、高いのと低いのを混ぜる必要がある。取り敢えずたくさん同じ温度にしたいので、できるだけ温度が目的のに近い方から貪欲に使うのが良い。後は、混ぜるのがいなくなるまで頑張るだけ。
C
Aグループに属しているものと、Bグループに属しているものが与えられる。それとは別にAグループかBグループか分からないけれど、同じグループに属している情報が与えられる。両方のグループに属している要素の最小数を答えよ、という問題。
同じグループに属している関係を辺にしてグラフを作れば、AグループからBグループに到達できることで、両方に属していることになるので、やるだけ。グラフが結構大きくなるような気はするものの、比較的疎なグラフなので、最小費用流でも通った。
D
左右のみつながった2次元グリッドについて、各グリッドが、書かれている数字と同じ数だけ同じ数字と隣接している、という条件を満たす数字の書き方は何通りあるか答えよ、という問題。ただし、左右はつながっているので、回転して同じになるものは同じとみなす。
2を横に並べるか、3を横に二行並べるか、後は、1が2個くっついているのを回避するように2を敷き詰めるか。後者は1の関係で回転すると一致しないケースが作れたりするので、うまくそれを頑張りましょう、という問題。やること自体はとても簡単っぽいが、なかなかにやっかい。
659.1
あってなきがごとしな問題はどうなんだろう？
250
二種類のものを並べるときに、一方のものが直近のK個の中にK/2個以下になるようにしたい。(もう一方はどうでもいい。)一方のものの配置が一部固定されているので、最大の個数を答えよ、という問題。
もし一方のものを置いたら、それはK個分くらい影響が出るし、それより後ろに置いたら、もっと影響が出るので、置けるときには先に置いてしまうというような感じで、貪欲に割り当てていけばよい。
500
なんかちょっとゆがんだN*Kの空間があって、1x2のタイルか2x1のタイルか1x1のタイルを敷き詰めたい。何通り可能か答えよ、という問題。
ゆがみ方を適切に調整すると、2^K通りの状態を覚えておきつつN*K回割り当てていく感じになる。頭悪いと2^(K*2)になって詰む、というだけの問題。
1100
なんか存在してたらしい。
2015 Round 1A
起きたら終わっていました。
A
とあるものを減らす人と増やす人がいる。増やす人は好き勝手に増やす。減らす人も好き勝手に減らす場合、少なくともいくつ減らしたか、また、減らす人は常に同じペースで減らしたとする場合、少なくともいくつ減らしたか、をそれぞれ答えよ、という問題。
やるだけ。好き勝手減らすなら、減っているところを全部カウントするだけ。同じペースで減らすなら、一番減ったところを拾ってやる。ただし、同じペースの場合、0よりも小さくはできないので、その分だけ削っておく。
C
N個の点が与えられるので、それぞれの点について凸包の境界になるようにするには何個の点を除去すれば良いかの最小値を答えよ、という問題。
要はある点から開始して、自分が凸包作るときの次の点に選ばれるまでの順位を繰り上げる操作をすれば良さそう。実装面倒かな？
