なんとなくな日々のコメント

2015-06-12

[][] 661.1 11:56

久し振りにしっかりした問題だった。

250

整数Nが与えられるので、N+1からKまでの整数の最小公倍数と1からKまでの整数の最小公倍数が一致する最小のKを答えよ、という問題。


1からNまでの整数のうち各素数で割り切る最大回数を求めて、それが次に出てくる位置を覚えておく。その位置の一番大きいのが答え。

450

N個のノードのあるグラフを考える。色がK色塗ってあって、各ノードは自分よりも番号が若くて色の違うノードに対して枝をはることができるし、はらなくても良い。このとき、可能なグラフは何パターンあるか答えよ、という問題。


良く分かっていないけれども、二色の場合は階乗になるし、三色の場合は奇数のみの階乗になるし、という感じで、一般化すると、色の数-1飛ばしの階乗になる模様。後はmodを取るので、ループするまで頑張る感じ。


多分数学的には有名な何かなんだろうなぁ、とは思います。

1000

一列にノードが並んだグラフが二つ与えられるので、同じ番号のノードをマージする操作を高々K回やってよいので、全二点間の距離の最大値を最小化せよ、という問題。


良く分からないけれど、頑張ればDPみたくできるのだろうか?

2015-06-04

[][] 660.1 21:55

めんどうなことをやるだけでは、次につながる気がしない。

250

二次元平面上に二点選んで、それぞれから相対位置が指定された値にある点群の重みの合計値を最大化せよ、という問題。


作業。

500

ランダムにpermutationを選んで、それぞれの値について、それよりも前に指定された値がある場合は除去するという操作を行って、最終的に残る要素数の期待値を答えよ、という問題。


多分独立に計算できるはず。自分の前にあってはまずいのが前にいる場合、何通りあって、そいつの前にそいつの前にいちゃまずいヤツがいれば自分は生き残る、みたいなのを適当に反転させながら探索していけば良さそう。状態数は多いのでメモしていく感じで。

1000

見てない。

2015-05-31

[][] GCJ 2015 Round 2 02:42

例年に比べると簡単な気がする。

A

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


取り敢えず、矢印の先に矢印があれば、その矢印は放置しても良さそう。なので、矢印の先に矢印がないなら、適当に向きを変える必要がある。後は、変えた数をカウントするだけ。矢印がなければできない。

B

特定の温度で、特定の量の水がいくらかある。これらを好きなように混ぜて、できるだけ多くの目的の温度の水にしたい。そのときの量を答えよ、という問題。


温度はキープしないといけないので、既にその温度なら好きに使える。温度が違うなら、高いのと低いのを混ぜる必要がある。取り敢えずたくさん同じ温度にしたいので、できるだけ温度が目的のに近い方から貪欲に使うのが良い。後は、混ぜるのがいなくなるまで頑張るだけ。

C

Aグループに属しているものと、Bグループに属しているものが与えられる。それとは別にAグループかBグループか分からないけれど、同じグループに属している情報が与えられる。両方のグループに属している要素の最小数を答えよ、という問題。


同じグループに属している関係を辺にしてグラフを作れば、AグループからBグループに到達できることで、両方に属していることになるので、やるだけ。グラフが結構大きくなるような気はするものの、比較的疎なグラフなので、最小費用流でも通った。

D

左右のみつながった2次元グリッドについて、各グリッドが、書かれている数字と同じ数だけ同じ数字と隣接している、という条件を満たす数字の書き方は何通りあるか答えよ、という問題。ただし、左右はつながっているので、回転して同じになるものは同じとみなす。


2を横に並べるか、3を横に二行並べるか、後は、1が2個くっついているのを回避するように2を敷き詰めるか。後者は1の関係で回転すると一致しないケースが作れたりするので、うまくそれを頑張りましょう、という問題。やること自体はとても簡単っぽいが、なかなかにやっかい。

2015-05-13

[][] 659.1 12:00

あってなきがごとしな問題はどうなんだろう?

250

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


もし一方のものを置いたら、それはK個分くらい影響が出るし、それより後ろに置いたら、もっと影響が出るので、置けるときには先に置いてしまうというような感じで、貪欲に割り当てていけばよい。

500

なんかちょっとゆがんだN*Kの空間があって、1x2のタイルか2x1のタイルか1x1のタイルを敷き詰めたい。何通り可能か答えよ、という問題。


ゆがみ方を適切に調整すると、2^K通りの状態を覚えておきつつN*K回割り当てていく感じになる。頭悪いと2^(K*2)になって詰む、というだけの問題。

1100

なんか存在してたらしい。

2015-05-06

[][] 658.1 01:49

やる気がないと成績も悪い。

300

各点間の距離の偶奇が与えられるので、そのような木が存在するならばどれか一つ答えよ、という問題。


やるだけ。とにかく、偶奇が一致する相手とは一致するし、一致しない相手とは一致しない。後は、偶と奇のそれぞれ代表を一個つかまえて、枝を作るだけ。


650

整数配列が与えられる。任意の相異なる三つの要素から、9,3,1をそれぞれ引くという操作を行って、全部を0以下にしたい。この操作は何回必要か答えよ、という問題。


適当に多少貪欲にアサインした後に、全探索とかで通りそうな気はする。TopCoder相手には絶対やらないけれども。

850

見てない。