リンク
問題 https://codejam.withgoogle.com/2018/challenges/
解説 https://codejam.withgoogle.com/2018/challenges/00000000000000cb/analysis
概要
今回からジャッジシステムが新しくなっており、インタラクティブな問題も登場している。
Saving The Universe Again
SCSCCSSCCSのようなコマンド文字列を、Cを区切りと思って [ S ][ S ][ ][ S S ][ ][ ][ S ] というSがいくつか入った箱の並びと考えるとわかりやすい。
1番目の箱は重み1、2番目の箱は重み2、3番目は4、4番目は8、……という風に考えて、重み1が1つと重み2が1つと重み8が2つと重み64が1つだから合計 $ 1 \times 1 + 1 \times 2 + 2 \times 8 + 1 \times 64 $ ダメージ。
さて、可能な操作は文字列の隣接する2字を入れ替える操作だが、同じ文字を入れ替えても意味がないのでCSをSCにするかSCをCSにするかしかない。後者をあえてやることでのちのちいい結果になることがあるだろうか?ちょっと頭が混乱するが、箱のたとえを使うと、箱に入っているSを左の重みの小さい箱に移動する以外の操作は無意味ということが直感的に分かる(と思うんですけどどうですかね)。
また、こう考えると、一番右の重い箱に入っているSから順番に移すのが最も賢い、つまりgreedyに解ける、ということも直感的に分かる。
なお、どんなに操作を続けても元からSが $ x $ 個あれば最小ダメージは明らかに $ x $ であるので、最初にそのチェックを行ってもよい。上の操作をループで書くときに終了判定を実装する手間が省ける(impossibleでないことがわかっているときは絶対に操作がどこかで終了するので無限ループするだけでよい)。
Trouble Sort
実際にシミュレーションすると $ O(n^2) $ 。しかし、よく考えてみると、この操作を繰り返すと列の奇数番目の要素が偶数番目になることはないということが分かる。つまり、この操作の結果は奇数番目だけを取り出した列をソートしたものと偶数番目だけを取り出した列をソートしたものを交互に並べた列と一致する。これは $ O(n\log n) $ で得られる。エラー位置の判定は $ O(n) $ 。
Cubic UFO
Test Set 1だけ解いた。この制約下では、一つの座標軸に沿って高々45°回転させるだけでほしい結果が得られる。この回転角を $ \theta $ 、影の面積を $ A $ とおくと $$ A = \sin(\theta) + \cos(\theta) = \sqrt 2 \sin(\theta + \frac{\pi}{4}) $$ である。これを $ \theta $ について解いて、回転行列を使って各点を回転させた座標を求めと答えが出る。
ちなみにまじめに計算すると $$ \cos(\theta) = \frac{A}{2} + \sqrt{\frac{1}{2} - \frac{A^2}{4}}, $$ $$ \sin(\theta) = \frac{A}{2} - \sqrt{\frac{1}{2} - \frac{A^2}{4}} $$ という感じで三角関数は消せる。数値誤差的にもこちらの方が望ましいか。
なおこれをやってもサンプル入力に対する出力がサンプル出力と大きくずれ、すごく不安になるが正しいはずと信じて出すと通った。つらかった。
あとはやってない。
