ABC165

ABC165に参加しました。

とりあえずは二日連続で更新できそうです。

A,B,Dの三完でした。Cの実装がいまいちぴんと来なかったのでDを見たところ、これはすぐに解けそうだなと思ったのでDから解きました。Dをかなり早めにACできたところまではよかったのですが、Eのバグ取りが出来ずに三完で終わりました。パフォ自体は悪くなかったですが勿体なかったです。

Tasks - AtCoder Beginner Contest 165

All Submissions - AtCoder Beginner Contest 165

A-We Love Golf

A以上の最小のKの倍数がB以下であればOKなので、((A-1)/k)*kでA以上の最小のKの倍数を計算してBと比較しました。

B-1%

整数型の変数に100を入れておき、それを何回1.01倍したらX以上になるか数えました。整数型は計算するごとに小数点以下が切り捨てられるので細かいことを考えずに済むので今回は扱いやすいと思います。

C-Many Requirements

おそらく数列Aを全て調べれば良いということは分かりましたが、数列Aをすべて生成する上手なコードが全く思いつかなかったので、コンテスト中に解くことは諦めました(根性見せて10重ループを書くか、E問題に取り組むかを天秤にかけました)。全探索でいいということが分かったのは、このAような数列組み合わせの数は、19C10=92378になるからです。受験数学の数列の範囲だったと思います。

ここまでは考えていたので、コンテスト後に解説を見ました。方針自体は概ねあっていたので、sunukeさんの解説コードをまねしてコードを書きました。再帰関数については勉強したつもりでいるのですが、こういう時にスッと書けないのでまだまだ練習しないといけないようです。再帰関数を使うという発想にすらならなかったので…。

少し話は変わるのですが、snukeさんのものを参考に一番最初に書いてみたコードのバグを取ったものがこれです。

Submission #12860818 - AtCoder Beginner Contest 165

バグが取れなかったので、一度sunukeさんのコードと対応させて添え字の置き方を変えたもので先にACしたのですが、その後バグを取ったこれでもACが出ています。ただ、このコードだと数列Aの一文字目は必ず1になっているので、問題を僕が読み間違えていなければWAにならないといけないような気がします。どうなんでしょうか…。

D-Fllor Function

これはかなりラッキーな設問でした。実数t以下の最大の整数というのは、言い換えるとtを小数点以下切り捨てしたもの、ということです。直観的にxがBより1小さければfloor(x/B)が0になるので最大化できそうです。一応いくつか数字を当てはめて検証してみたところ周期的に変化しており、やはりxがBの倍数より1小さい時に最大となるようだったので、x=B-1としてコードにしました。

E-Rotation Matching

対戦相手をズラせばよさそうだなと思って深く考察することなくコードを書き始めたら泥沼にはまってしましました。偶奇で場合分けをしないといけないということに気づいた後も偶数の時の扱い方が曖昧だったので時間内に修正できませんでした。対戦相手をズラして、というだけでなく、D問題でしたように具体的な数字を入れてどこから切り替えて数字をズラすのか、ということを考えないといけなかったです。

C問題あたりまではざっくりと方針を決めて書きながら考えても解けるようになってきたのですが、D,E問題はしっかり最後まで考えてからコードにしないと、まだまだ不用意に時間を浪費してしまいます。

今回は以上です。