abのみで12点 2205位で敗退しました...来年こそは！
A Spirailing Into Control
とりあえず部分点を考えます
K回以内に操作できるか？みたいなのは、DPテーブルに操作回数を持たせるのが多い気がします
今回も
dp[i][j][k] = (i,j)にいて操作回数がkのときに、どこからきたか？
と定義することで解くことができます
遷移は(i,j)の値が小さい順に愚直にやりましょう
Largeを考えてみますが、すぐにピンとくるわけではないので他の部分点を狙いにいきます
B Pixelated Circle
いかにもめんどくさそうで、roundとsqrtの誤差を適切に処理しないと愚直も落ちそうで嫌だなとなります
いったんLargeを考えますが思いつかないので、しかたなく愚直を書きます
さすがに小数をそのまま使うと落とされることは目に見えているので、式変形をして整数だけで判定できるようにします
round(x) = Aなら A-0.5 ≦ x < A+0.5であることを 利用すれば不等式で評価できます
とりあえずsmallは通したのでCにいきます
C Saving The Jelly
これもsmallを考えますが、N≦10の割にピンときません
N!を考えますが、さすがにO(N * N!)くらいは必要そうなので厳しそうです
となると、bitDPが定番なので考えてみると、子どもとお菓子をまとめてbitとして管理すればよいことに気づきます
あとはこのbitDPを実装するだけです、定数倍の高速化のためにあらかじめ2点間の距離は前計算しておきます
...が、WA
コードを読んでちょくちょく怪しいところを直しますが4WA
あまりに正しいコードになってしまいお手上げになりました
ここで粘ってて結局解けずに時間切れでした
終わった後にupsolveしたんですが、INFが小さすぎたのが原因でした
(ルートを外した)距離の最大値が
(10^9 - (-10^9)) ^ 2 + (10^9 - (-10^9)) ^ 2 = 8*10^18
となるので、ここまで広げなければいけません
考慮したつもりだったんですが、計算を間違ってました
ちゃんと丁寧に確認するべきでしたね
D I, O bot
部分点を取ろうと思ってちょっと見たんですが、すぐに思いつきはしなかったので解きませんでした
部分点だけで通るならabcdが必要だったので、これ倒せるくらいの実力はつけたいですね
総括
立ち回り難しい...
Aのlargeもちゃんと難しいと思ってたので、abcで通るかなと思ってたんですがそんなことなかったですね
今までのGCJの経験的に重実装部分点とるのは得意よりなので、ひとまず部分点を全部取ってLargeとしっかり勝負できればいいな
