ABC190の感想

AtCoder Beginner Contest 190に参加しましたのでその感想を書いていきます。問題はこちらから。

Tasks - AtCoder Beginner Contest 190

結果はこんな感じでした。

4完（2wa）
順位：3039 / 9310
パフォーマンス：935

難しかったなーという印象でした。特にD問題です。waを出しながら命からがら何とかacに辿り着いたのですが、皆さん解いてて驚きです。ほんとうにびっくりです。

aでwaを出したのはちょっと集中力不足だなって感じですが、それ以外は特にいつも通りでしたので、これが私の実力かなと、素直に受け止めます。少しでも自分をほめるとすれば、

「d問題を60分良く粘りました。」

感想いきます。

A問題

2人で飴ちゃんを食べます。交互に食べていって、先に自分のストックがなくなったら負けです。

という問題です。考えるのが、面倒くさくなって、while文でシミュレーションをしましたところ、間違えました。横着は良くないです！

その後、a>b、a<b、a==bで場合分け、a==bなら先攻後攻で判定をちゃんと書きましたところ無事acでした。よかった。

B問題

モンスターに魔法を放ちます。強い魔法は詠唱が長いです。

モンスターに攻撃される前に、モンスターの防御力を貫通する魔法は放てるかという問題です。

これはぱっとわかりました。

xi < s && d< yi

これを1つでも満たせば、okです。

C問題

お皿とボールに関するクエリが飛んできます。

いろいろと考えましたが、結局、制約のk<=16に一番心を打たれました。

状態はaかbの２つなので、全通りを探索しても、2^16で65000ぐらいですね。ということで、思考停止でbit全探索を書きました。

ぱっと思いついたのもそうですが、何もみないですらすらとbit全探索（特にビットシフトのところ）を書けたのはとっても良かったのかなと、

D問題

これが、曲者でした。

問題文を見たときにまず、問題文短いなあって思ったところから開始です。

はじめは何にもわかりませんでしたが、nを半分にしてみました。そうすると、nが奇数の時にはなんかできるなあと気づきました。でもいまいちピントはこず、、

でもここらへんで、マイナスの部分って、正のやつと1対1で対応するから自然数範囲に絞れるとわかりました。

次に、nをなんかで割ったときに

余りが0かつその商が奇数

ならいい感じになりそうだなと。

たとえば、9/3=3なら

3-1, 3 ,3+1

でこの-1と1が打ち消しあうから、3*3で9が復元できる。ということで、約数が関係してそうだな。とここで気が付きます。

ここから、言語化がうまくできないのですが、ふんわりと書いていきます。

まず、約数の探索は√nでできるので、約数を全探索して奇数だけ足しました。提出したらwa。これは困りました。

いろいろと悩みました。nが奇数と偶数のとき、素数の時、場合分けはなんかできないかな。

1項は必ずできる。2項は、n-1、より小さい奴を組み合わせて、nをつくる。3項は2項の大きいほうを、小さいほうより小さい2つで作る。以下繰り返し。で何個作れるか？（何を言っているかよくわからないですね。）

奇数個の項で作る場合は偶数と奇数のどっちが多くなるか。

などなど、とにかくいろいろやりました。

結局、acしたのは以下のルールです。（これも良くわかりません、）

n / p = p*q ... r
pが偶数→r=0 かつ q-r>0
pが奇数→r=p/2 かつ q-(p-1)/2>0

これを適当なところまでやりました。本当に適当です。入力例3の答えが合って、tleしない程度に決め打ちしました。なんでそれでいいかもわかりません。

よくわからないけどacできたことはえらいと思います。でも、正直解けてはないので、しっかりと反省しておきます。