ABC161

参加しました。

恒例の全然ダメだなあという出来栄えでした。

そもそも一週間前のことですからね。ちなみに昨日のABC162も全然ダメでした。ABC162に比べたらABC161はまだマシでしたね…。

All Submissions - AtCoder Beginner Contest 161

私の回答です。復習で解説放送の概要欄を見たら、検索結果もリンクが有効なことに気が付きました。常識じゃないか…という気もしますが…。

A-ABC Swap

x,y,zの順に受け取ってz,x,yの順に出力しました。

B-Popular Vote

二回WAを出したんですよね。焦りがあったんだろうなあ…。

総票数を数えた後、1/4m倍して必要票数を求めて、一つ一つチェックしました。

総票数の1/4mを出すところで二回間違えました。余りの処理が下手くそですね。例えば偶奇分けのときは、(a+b+1)/2としてやると少数派切り捨てられるので場合分けをせずに一つの式で処理できます。総票数をxとすると、(x+4*m-1)/(4*m)としないといけないのですが、-1を忘れていました。不注意はなくしていきたいです。

C-Replacing Integer

差を取っていくので、結局余りを求めているのと同じことになります。絶対値と置き換えるので、最終的には余りと、kから余りを引いたものを比較して小さいほうを出力しました。

D-Lunlun Number

コンテスト中に時間がかかりそうだと思ったので飛ばしました。string型で受け取って桁を比較していくのかな～くらいまで考えましたが、Fが解けそうだったので後に回したところ結局戻ってくることはありませんでした。

コンテスト後に解説を見てACしました。コンテスト中にこだわらなくてよかったです。多分自力では解けなかったと思います。queueを使って、一桁の整数を列挙し、その後一つずつ追加していくやり方を選びました。

E-Yutori

これは、Dとは違って解き方は分かりました。前からと後ろからそれぞれ貪欲に働く日を決めていき、被る日があればその日は働く、というやり方です。前から求めるときは、働ける日を貪欲に選んでいき、1からスタートしてkまでの数字を順に振り当てます。後ろから求めるときは、働ける日を貪欲に選んでいって、kからスタートして1までの数字を順に振り当てていきます。これで、もし前からと後ろから振り当てられた数字が同じだった日は必ず働かないといけないとわかります。この方法は、i日目を一番早くなるようにしたときと、一番遅くなるようにしたとき、とも言い換えられます。

ここまでは考えたのですが、これを実装する能力は自分にはなさそうでした。これ以上簡単な方法も思いつかなかったので、飛ばすことにしました。もし仮にFが解けていた場合は、正確な解法を思いついてもいないDに戻ろうとすら思っていましした。

コンテスト後に解説放送を見て、そこで書かれていたコードを改変してACしました。

F-Division or Subtraction

戦犯です。解けたと思ったのですが結局バグが取れませんでした。

nが割り切れるときと割り切れないときで分けて考えます。割り切れるときは、割り切れなくなるまで割ることで、そのあとの処理が割り切れないときの処理と同じようになります。割り切れないときの処理はC問題とほとんど同じです。nとの差を取るということは結局割った余りを取るということです。余りが1になればいいということは、n-1が割り切れたらいいということなので、これは簡単に求めることができます。次に割り切れるときですが、これもまたn-1が割り切れる数を探したときと同様にして、割り切れなくなるまで割った後に、もう一度割り算をして余りが1になるかどうかを確認すればいいです。

完璧に解けたと思ったのですが、TLEを吐いてしまいました。その後いろいろと試してみたのですがどうにもならず、コンテスト後に解説を見て少し書き方を変えたところ、またTLEを吐きました。そこで、解説のコードと逐一見比べたところfor文を初期化した型がint型かlong long型かの違いがあったので、intからlong longに書き換えたところ、もともとのコードでもTLEが取れました。キャストの計算量が意外とバカにならないんでしょうか。少し調べたのですがよくわかりませんでした。

以上が今回の復習になります。

悔しい結果が続いてるので何とかしたいですね。(次回は何ともならなかったという…)