2018年4月11日水曜日

Google Code Jam 2018 Qualification Round

リンク

問題 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}} $$ という感じで三角関数は消せる。数値誤差的にもこちらの方が望ましいか。
なおこれをやってもサンプル入力に対する出力がサンプル出力と大きくずれ、すごく不安になるが正しいはずと信じて出すと通った。つらかった。


あとはやってない。

2016年12月17日土曜日

dwacon 2017 予選

リンク

問題 https://dwacon2017-prelims.contest.atcoder.jp/
解説 なし


概要

Aはやるだけ。
Bは/([2?][5?])+/にマッチする最長部分列の長さを求める問題なのだが、オーバラップがあるためたとえばPythonの標準ライブラリreだけでは単純に記述することは出来ない(はず)。
具体的には、入力例4を見てみると2???5????に対して225252525とはてなを埋めたときに長さ8の最長列を得られることが分かるが、オーバラップが扱えないと

$ echo '2???5????' | grep -Po '([2?][5?])+'
2???
????

と欲しい部分を見つけることが出来ない。
ここで少し考えると、最長の列を得られるような埋め方というのは「先頭から奇数文字目のはてなは2、偶数文字目は5」またはその逆、のどちらかであることが分かる。
これを使って、この2種類の埋め方で得られる2つの文字列から最長の列を探すだけで全体の最長の列を見つけることが出来る。
Cは貪欲にやる(という言い方であっているのかな)。つまりある搬器にあと2人乗せられる状況で1人乗せるか2人乗せるか迷う必要はなく、常に多い方を乗せればよい。
したがって、各時点で乗せられる限り大人数の団体を優先的に乗せる、というのを繰り返すだけで解ける。
Dは時間内に思いつける気がせず撤退してしまったが、解説している人のツイートなどを見て理解した。
問題は、短くまとめるとn個の寿司を順番に食べるとき、各寿司に「少しスコアが得られる食べ方」と「たくさんスコアが得られる食べ方」があり、「たくさんスコアが得られる食べ方」は全体でm回しか使えず、m回使ったあとに出てくる寿司はどちらの食べ方でも食べられない、というルールでスコアを最大化する問題。限られたm回の使い所を選ぶ方法を考える必要がある。
i皿目まででちょうどm回の権利を使い切るとして最大のスコアはいくつか?というのを前から順番に考えていくと、i + 1皿目を食べるときに「i + 1皿目でm回目の権利を使い切る」ために今までに食べた「たくさんスコアが得られる食べ方」を1回諦める、というのを繰り返して更新していけばよいが、ではどれを諦めるのが良いか?というと2つの食べ方によるスコアの差が一番小さかったものを諦めるのがよい。
これは優先順位付きキューを使うことで効率よく実装できる。
このiの結果を使ってi + 1を求めていく感じ、DPっぽいけどそう呼ぶのかどうかはわからない。
Eはわからず。

2016年11月5日土曜日

DDCC2016 予選

リンク

問題 http://ddcc2016-qual.contest.atcoder.jp/
解説 http://ddcc2016-qual.contest.atcoder.jp/data/other/ddcc2016-qual/editorial.pdf


概要

Aはやるだけ。Bも中学校レベルの数学でやるだけ。writerがchokudaiさんだったので何事かと思ったけど、そういうことか。
Cはkとの関係によって同値類をまとめて全探索可能なサイズに帰着するというアイデアには至ったのだが、kとの公約数すべてを調べるものと思ってしまい重複をうまく扱う方法が分からなかった。
そんなことしなくても最大公約数でまとめるだけで簡単にできた……。
届きそうで届かないギリギリの問題をたくさん解いていくことが上達の近道だと思うので貴重な問題だった。
Dは未着手。

2016年8月29日月曜日

ABC044

リンク

問題・解説 http://abc044.contest.atcoder.jp/ 

概要

A, Bはやるだけ。CはDP。
おそらくだが解説よりも簡単かつ高速な方法で通したと思うので概要を述べる。

1枚目から $i$ 枚目までのカードだけを使ってどのような組み合わせを作れるかを順に求める。
問題設定から、平均がある値になるものだけが重要なので、「狙う平均からの差分の合計」だけを覚えておけば良い。使った枚数は不要。最終的にこの合計が $0$ となるような組み合わせを探す問題となる。

たとえば1つ目の入力例について考えると、狙う平均値は $8$ なので、
  • 1枚目 ($7 \equiv -1$) までを使うと $\{0, -1\}$ (何も取らないと平均が0, 1枚だけ取ると平均が-1になる)
  • 2枚目 ($9 \equiv +1$) までを使うと $\{0, -1, 1, 0\}$
  • 3枚目 ($8 \equiv \pm0$) までを使うと $\{0, -1, 1, 0, 0, -1, 1, 0\}$
  • 4枚目 ($9 \equiv +1$) までを使うと $\{0, -1, 1, 0, 0, -1, 1, 0, 1, 0, 2, 1, 1, 0, 2, 1\}$
となり、全て使った時点で平均が $0$ になっているのは6通り。
ただし、カードを1枚も取らないという手を含むため、その分を引いて答えは5通りとなる。

うまくカウンタのようなものを使うことで全体で $O\left(N\right)$ くらい……のはず。

Dは出来なかった。
$2 \le b \le \sqrt{n}$ は全探索し、 $\sqrt{n} \le b \le n$ は $b$ 進数であらわすと必ず2桁の数になることを使って高速に解ける。
最初解説を聞いてやってみても間に合わずずっと悩んでいたが、unsigned intをlong longに置き換えただけで早くなって通った。いっそPythonで書けばよかったかな。

2016年7月31日日曜日

AGC002

リンク

問題 https://agc002.contest.atcoder.jp
解説 ?


概要

A, Bはやるだけ。
Bちょっと無駄に書いてしまったけど本質的にはあっていたということで。
CはDPで解けるのかと思ったらうまくいかず、「ある簡単な解法があってそれを実装するだけ」というエレガントな問題だった。
あとは手付かず。

2016年7月24日日曜日

ABC042

リンク

問題 https://abc042.contest.atcoder.jp/
解説 http://arc058.contest.atcoder.jp/data/arc/058/editorial.pdf

今回から新形式になっている。

概要

A, Bはやるだけ。
Cは繰り上がりなどを巧妙に考えたやや長いコードで通したが、全探索でいけるらしい旨が解説されている。
Dは解説があまりに不親切だが「フェルマーの小定理より $(x!)^{−1} \equiv x^{10^9+5} (\text{mod }10^9 + 7)$ である。」とのこと。全く意味がわからないがこれを一瞬で思いつけるかどうかで解けるかどうかが決まるらしい。数え上げの方法も非自明だと思うが、とくに説明がないので誰でも簡単にわかるようだ。天才たちのゲームはむずかしい。
Beginner Contestを名乗っておきながら初心者のためになるものを作る気がない感を隠さないのはいかがか。

フェルマーの小定理とは、平たく言うと、$p$ が素数、$a$ が $p$ と互いに素な整数としたときに $a$ の $p - 1$ 乗を $p$ で割った余りは $1$ になるということを述べたもの。
$10^9 + 7$ は素数である。またこのことから $2$ 以上 $10^9 + 7$ 未満の整数 $x$ はいずれも $10^9 + 7$ と互いに素であることが分かるし、更にそのことから $x!$ も同じく $10^9 + 7$ と互いに素になることが分かる($10^9 + 7$ と互いに素な整数のみを掛けあわせた結果であることから)。
つまりフェルマーの小定理を使って $2$ 以上 $10^9 + 7$ 未満の整数 $x$ に対して $(x!)^{10^9 + 7 - 1} \equiv 1 (\text{mod }10^9 + 7)$ 、すなわち $(x!)^{-1} \equiv (x!)^{10^9 + 7 - 2}$ となることが分かる。
これで右辺がただの正数による累乗になって式変形が簡単になり、
\[\begin{eqnarray*}
(x!)^{-1} &\equiv& (x!)^{10^9 + 7 - 2} \\
&\equiv& ((x - 1)!)^{10^9 + 7 - 2} \times x^{10^9 + 7 - 2} \\
&\equiv& ((x - 1)!)^{-1} \times x^{10^9 + 7 - 2}
\end{eqnarray*}\]
てな感じで漸化式っぽく簡単に計算できそうになった。
…………あれ、解説とちがうなあ。

関係無いけどMathJaxを導入した。
やり方は http://irrep.blogspot.jp/2011/07/mathjax-in-blogger-ii.html に従っただけ。

更に関係無いけど:

このあともうちょっとアホな部分をまともに書きなおしたらPython3でも通った。
$(x!)^{-1}$ を事前計算しておくのを逆順に計算すると簡単。

と、思ったけどPythonにはpow(x, y, z)があるのでそんなことしなくてもいいのか。

2016年7月10日日曜日

ARC056

リンク

問題 http://arc056.contest.atcoder.jp/
解説 http://arc056.contest.atcoder.jp/data/arc/057/editorial.pdf

概要

Aから難しかった……解析的に解いたけど実は場合分けがそんなに複雑でなく大半のケースはシミュレーションで解ける。
B, Dは手付かず。
Cは終了後他の人のコードを見たりしていろいろ頑張ったが最終的に(x + 99) // 100とmath.ceil(x / 100)が同じことをしたいコードなのに後者は浮動小数点数の丸め誤差で動かないという悲しいずれにより撃沈。