AtCoder Beginner Contest 249に参加した話
AtCoder Beginner Contest 249に参加しました。今回は4完に成功し、目標の水perfを達成することができました。
ネットに詳しい解説があふれているため緑色の私が解説する必要はなく、解説はしませんが、コンテスト中にどういう思考プロセスを取っていたのか(どういう独り言を言っていたのか)、まとめてみます。
A.
あー、また面倒そうなAが来たよー...
うーん、とりあえず歩くのと休むのをセットで周期として考えれば、いいんじゃないかな？
カッコつけるの面倒だから掛け算の順番変えちゃうか→WA
やっぱだめか...→AC
B.
すでに出てきたやつを記録しておけば、重複してるかわかるな
mapで記録して、1文字づつすでに出てきてるか確認すればいいね→AC
C.
ん？どういうこと？
とりあえずN<=15だし、bit全探索かな？
文字列から選ぶものをbit全探索して、そこに含まれる英小文字の数を数えればいいか...→とりあえず実装
あ、同じ文字列に同じ英小文字が2字以上含まれていると、カウントがおかしくなるな、工夫が必要だな→AC
D.
制約的にO(N^2)解法をどうにかしろって問題だな...
A_i/A_j=A_kってつまり、A_i=A_j*A_kだよな
A_jとA_kがA_iの約数ってことか、そういえば約数列挙ってO(√N)とかでできたよな
数列Aに出てきた数字の個数をmapとかでカウント→A_iの約数列挙→その約数とA_i/約数の出てきた数を掛け算したら何通りあるか求められそう
O(N√N)とかで間に合わないかな？とりあえずやってみるか→TLE
あれー...、いらないsortとか消してみるか...→AC(1600ms...?????)
補足: D問題は実際O(N√N)で通ります。ただ、mapがかなり重いため、制限ギリギリになってしまってTLEを出したようでした。後で、vectorやunordered_mapを使用したところ十分高速に動作しました。(200ms~600ms)
