Google Code Jam Qualification Round 2019に参加した記録

いつから:2019/4/6 AM 8:00(JST)

いつまで:2019/4/7 PM 12:00(JST)

問題数:4問

超簡単なルール説明:

　各問題には当然だがテストケースが設定されている。

　ただし、通常のプログラミングコンテストとは少し違い、visibleとinvisibleの2つのタイプが各問題毎に存在する。visibleが弱い制約、invisibleが強い制約下で構成されている。

　visibleの正誤はコンテスト中に閲覧可能だが、invisibleはコンテスト終了後に正誤が判明する。

　その為、通過点ギリギリの点数を取って「〇〇点取れてる!!通った!!やった!!」とか思って浮かれてると後でinvisibleケースで落ちていて予選敗退ということも十分考えられる(コンテスト中には自分の獲得した点数が表示されるがそれはあくまで"invisibleケースが全て通っていた"場合の仮定の点数である)。

結果:提出した問題は全てACで41点を獲得。Round 1でも頑張ります。

解いた問題の適当な解法:

　勿論、invisibleケースで落ちているかもしれないので満点解法ではない可能性もある。全部通ってました。やったね。

問題概要:

　整数Nが与えられる。Nはどこかに4を含んでいるがキーボードの4の数字の部分が壊れているので足すとNとなるどこにも4を含まない2つの整数を打ちたい。その2つの例を挙げてね。

codingcompetitions.withgoogle.com

解法:

　当然ながら、invisibleが1≦N≦10^100なので文字列として入力する。

　次に、2つの配列を用意しておく。

　文字列をforで前から舐めていくといずれ'4'という文字列が出てくるので2つの配列それぞれの末尾に'1'と'3'を入れる。

　それ以外の数字の場合はどちらか片方の配列にその文字を加える。もし、それ以前に'0'以外の文字が出てきている場合はもう片方の配列には'0'を加えることにより、例えば10を表現したい時に0010となったり、位がずれてしまって1となることを防ぐことができる。これの実装が1番面倒だった。

　これらを実装して、AC。1つのクエリにつきO(|N|)。