code jam Qualification Round 2018に挑んだ

細々とにわか競技プログラミング勢として気まぐれにコンテスト参加してるけど、初めてcode jamに参加してみた。

結果は、64点で無事予選通過ですることができた。 f:id:mizunomi32:20180408122133p:plain

1. Saving The Universe Again

この問題は、「S」(Schott)と「C」(Chage)の文字列が与えられる。チャージするとそれ以降にショットするときのダメージが2倍になるので、隣り合った文字を入れ替えることができるので、最小の回数で任意のダメージ以下になるように入れ替える問題。

方針としては文字列の後ろから走査していき、「SC」の並びがあれば入れ替えてダメージ計算し、再度後ろから捜査し直すみたいなことをした。

2. Trouble Sort

この問題は、問題で示されたソートを実行して、どこで何番目の要素までソートできているのか判定する問題。

愚直にそのまま実装すれば、とりあえず点数もらえたので1番かんたんだった気がする。 高得点をもらうには入出力を高速化しないと厳しそう。

3. Go, Gopher!

Gopherに命令して任意のサイズ以上の矩形を作る問題。ただ、Gopherが言うこと聞かないときたまにある。

方針としては、とにかく3×3の正方形を塗りつぶすのをひたすら縦に繰り返していった。

4. Cubic UFO

中に浮かぶ立方体型のUFOを回転だけで影を任意の大きさにする問題。

高得点を目指さなかったら、影の面積が1.0000~1.414213なので1つの軸を回転させるだけでいい。結果的には、2分探索で回転角いじって面積を近づけていった。