KUPC2014

参加記。
過去のKUPC記録を見てみると、
KUPC2011 4完(42位)
KUPC2012 5完1半(67位)
KUPC2013 3完(94位)
KUPC2014 6完(52位)
と解ける問題が増えててうれしい。

点数的に順番に解いていけばよさそうなので、前から解いていく方針。

A.マッサージチェア

問題読み飛ばして例題から問題を推測してしまっていろいろおかしかった(小数で計算、出力・・・
そのまま丁寧にやるだけ。

B.数当てゲーム

また、問題読まずに雰囲気から2分探索のコードを途中まで書いて、問題見たら「割り切れるか」になってるのに後から気づくというひどさ・・・
nで割れるか？でYならそのnの倍数はすべてOK、Nならそのnの倍数はすべてNGとなるので、2,3,5,7,11...と素数を確認しつつ、OKかNGかどうか調べれば200回以内にすべて確認できる。

C.占い

さすがにちゃんと問題を読む。
最大でもa1とb1が2回目にならぶ時の1つ前までしかなさそうということがわかる。
「1回目〜n-1回目はすべて同じで、n回目で初めて異なる」というのを確かめればよさそう。
あとは矛盾しないかどうかのチェックで、2SAT？強連結成分分解？と思ったけど、インデクスでグラフを作って、同じなら連結、違うなら非連結・・・ってUnionFind。
nをデクリメントして毎回UnionFindする無駄なコード書いてTLEしてしまったけど、インクリメントしていけばいいので、書き換えて提出

D.ハミング

どうもDPくさい。
でも、dp[di][dj][i][j]:=S1がiまででdi個異なる、S2がjまででdj個異なる組み合わせの数？みたいな？
やばそうなので、後回し。

E.何しちゃおっかな？

単純な形だと反転させてくっつけてできる2*4の長方形で敷き詰められるかの問題か。(ただし、2*4長方形は2回以上じゃないとピースを2種類使えない
とりあえず、自明な条件として、N*Mは4で割り切れないとピース的におかしい。
条件分岐で通せそう。

N=2の時は、(2回使わないといけないので)M>=8かつM%4==0でよい。
N>=4かつN%2==0の時は、M>=4かつM%2==0でよい。

が、ダメ。
N=3や5のような奇数の時は作れなさそうか？
3*4は無理そうだけど、3*8や3*12で敷き詰められるとその倍数も可能になる。
試してみると、3*8で作れる。
3*8はいいけど、3*12は作れないので、M=8*iであればよさそう。
また、3*8ができることからN=8ならM>=2のすべてが可能。
N%2==0、N%4==0、N%8==0の時はMの条件が緩くなるので、それらを確認。
N%2==1だと、Mは8の倍数じゃないといけない(?)。M>=?なら4の倍数でよいみたいなケースがあるかもしれないと思ったけどなさそうなので、提出。。。

J.カード

DPくさい。
でも、状態が、
・i日目
・n枚保持
・m円保持
ぐらいなので、
dp[i][j]:=i日目でj枚保持のとき、残っているお金の最大値
でよさそう、提出。

D.ハミング(再び)

各i番目について考えてみると、組み合わせは(0,0)(0,1)(1,0)(1,1)しかない。
①(0,0)と(1,1)の時は、逆の値にすればどちらも異なる数を+1できる。
②(1,0)と(0,1)の時は、どちらかだけを異なる数にできる。

①の方でn個異なる数にすると、②の方ではd1-n個、d2-n個にならないといけない。さらに(d1-n)+(d2-n)=(1,0)または(0,1)の個数、となっていないといけない。
それぞれ組み合わせ計算すればいいので、modComb使って計算。

K.弱点

最後時間無くて、問題読んだけど、部分点でやるだけ感があったKにチャレンジ。
書いた後で、部分点の制約でモンスターの数は10^5なのに気づいて絶望して終了。

反省

問題文をめんどくさがらずにちゃんと読む。
典型っぽいものは見たらすぐ気づけるようにしたい。