パナソニックプログラミングコンテスト2020

昨日の上記コンテストに参加しました。

外でご飯を食べていたので、25分遅れ＋スマホ＋飲酒のトリプルコンボ状態でしたが、参加したほうが経験になると思って参加したところ無事爆死しました。

Panasonic Programming Contest 2020 - AtCoder

IDは

saikatoto

です。

〇A Kth Term

配列をコピペして初期化、そのまま.at(k-1)で出力しました。

〇B Bishop

ビショップなのか角行なのか…となりました。英訳されるんですかね。Kakugyouとか英語で言われそうな気もしますけど…。

直感的にマス目のちょうど半分に行けそうだと思ったので、図を区切って2*2,3*5などをイメージしました。2で割って切り上げでいいことが分かったので、素直に書いてWAをもらいました。H,Wのいずれかが1の時は左上から移動できないので、その時は1を出力するようにしました。

×C Sqrt Inequality

鬼門でした。結局コンテスト中にACできず、元のレートが低いので影響があまりなかったことが不幸中の幸いでした。

素直にsqrtで√をつけた場合、小数点以下の桁落ち？などの影響がありそうだなあと思ったのですが、まあこれでACしたら儲けものだと思って適当に出しました。もちろんWAだったので、いくつか工夫をして出し直したのですが、特に効果はありませんでした。sqrtの引数はdouble型で処理されていることなどは今回調べてみて初めて知ったのでいい勉強になりました。

ここで方針を転換して、式変換することで整数のまま処理をすることにしました。両辺を二乗して、k=c-a-b>0の時、2√a√b<kの両辺を更に二乗します。こうすることで整数のまま処理ができる～と思ったのですが、実装の段階で全くWAが取れませんでした。方針はあっているはずなのでムキになってしまい、結局コンテスト中はず～っとWAのままでした。

今朝一から書き直したところ、一発で通せたのですが、昨日のコンテスト中に出したコードの何がいけなかったかはまだ見返す気になれませんでした。

コンテスト中に目を通したのはここまででした。

D String Equivalence

今朝解きましたが、あっさり解けただけに悔しさがすごかったです。

n=1,2,3の時を考えると、a、aa,ab、aaa,aab,aba,abb,abcとなります。アルファベット順に新しい文字が使えるようになっていき、dやgがcよりも先に使えるということはありません(同型になります)。樹形図のイメージで考えました。たまたまDFSの勉強を最近したので、素直に再帰関数を書いてみたところあっさり解けました。

使える文字に制限があるので、文字制限の情報と、今持っている文字列の二つを保持します。文字制限の次の文字まで使うことができるので(例えばそれまでにa,b,cを使っていれば次はa~dまで)、末尾に加える文字がこれまでに出てきていないものであったときは文字制限を一つ増やします。aから順に素直に使うようにfor文を書くことで、DFSで出来上がったものから出力していけば通すことができました。

Eはこれから実装してみようと思います。

C,Dがかなりもったいなく苦い薬になりました。良薬だったと言えるようにしていきたいです。