予選のこと書いて、正直疲れたからまた今度にしようかと思ったけど、絶対やらなさそうだったから、連続更新。
運良く決勝進出できたので、そん時のことを覚えてる範囲で書こうとおも。
問題A. アンテナ修復
単純におっきい三角形作ったら正解じゃね??と思って配列でアンテナの長さを表現。三角形の面積の求め方が怪しかったので、調べながら実装!余裕!!と思ってテストケースでテストしてもテストが通らない。おいこらなんでだ。まあ、こんなに簡単にできてしまうと問題にならんかとも思ってひたすらアンテナの絵を書いた。
どーやら、長いアンテナ中心に右、左、右、左と順に長いやつ並べて行ったらいけそうと気づく。うまい具合に配列を並び替える関数作ってsmallクリア
予選の時は、計算量かんがえずにそのままlarge問題解いてアウツだったので、きちんとLargeの条件も見る。最大1000個のアンテナということだったので、配列の並び替えやるだけならlarge解けそう → クリア。ラッキー
問題B. バクテリアの増殖
xのx乗に増えるということで、明らかに計算量がやばい。またハングアップするiMacとmacbookProが浮かんだ。考える。Largeの条件はxのx乗が最大1000回つづくということで、やばい。余りだけ追っていってもいいのかなと思って、いろいろアルゴリズムとか調べてみる。＼(^o^)／ないがな!
smallの条件を見ると、xのx乗が、最大2回しか続かないということで、最初のバクテリアの最大数は1000。1000の1000乗は一応計算できることを確認。pythonのpow関数は第3引数に値を入れることで剰余計算も行えることは知っていたので、1000の1000乗したやつをXとして、XのX乗の剰余計算ができるか確かめてみる。できるがな＼(^o^)／
かっこよさよりもポイント稼ぎに行く。Pythonに頼りっぱなしのださいコードになってしまった。
問題C. ワイルドカード
ここまでで、のこり30分。ワイルドカードできそう!!テストケースも通った!!いけるぞこれは!small提出!間違いおーまいがっと／(^o^)＼
後から他の人の解答を見てみると、端に*がくるパターンは考えていたものの、文字の間に*がくることを考えてなかった。解答としてはビットマスクを作成して総当り計算を行うみたい。
large問題は最大50文字ということで、ビットマスクパターンが2**50通りになってしまうため、そのままのアルゴリズムではだめ。少ない文字のパターンを順につくっていくプログラムもコンテスト終了後に作成してみたが、間違ってるみたい。Googleの公式解説動画は見逃してしまったので、答えが気になるところ。
問題D,問題Eとまだ続くんだけど、そんな余裕なかった。問題Aが意外と早く解けたのが功を奏してか、スコア23の71位。GoogleTシャツげっと!いやっほい!!
正直あんまりちゃんと解けてないから、運がよかったんだと思う。アルゴリズムとか考えてたら結構楽しかった。またやろ。
