ABC-B埋め(001~040)
ABC040までのAとBを埋めていたら、1日で59ACしていました!
ということで、B問題の印象に残った問題についての感想をいくつか書いていこうかなと思います。
- ABC001 B - 視程の通報
- ABC008 B - 投票
- ABC024 B - 自動ドア
- ABC026 B - N重丸
- ABC027 B - 島と橋
- ABC030 B - 時計盤
- ABC035 B - ドローン
- ABC040 B - □□□□□
ABC001 B - 視程の通報
問題
提出コード
1回目からこれか…って感じでした。素直に条件分岐をしてばいいのですが、Bにしては少し処理がめんどくさいなぁと感じました。
前日にABC001のCとD問題を解いていて、似たような分岐を書いたのでそれよりはすんなりいきました。
ABC008 B - 投票
問題
提出コード
この問題に限らず、最近mapを使う機会が多い気がします。
名前をキーとして票数を対応させ、入力後にマップを全探索していきました。
入力のたびに最大値と名前の更新をしてもよかったのかなぁと今は思います。
ABC024 B - 自動ドア
問題
提出コード
次の人が来たときに、まだ自動ドアが開いているかどうかで場合分けをすればいいのですが、それぞれのパターンでの処理に少し悩みました。
次にドアが閉まる時間と、開始時から次にドアが閉まるまでのドアの空いている時間をそれぞれ更新していきました。
ABC026 B - N重丸
問題
提出コード
外側から数えて奇数番目か偶数番目かを調べ、それによってそれまでの合計値(初期値は0です)に半径の二乗を足す、もしくは引いていき、最終的な数にπをかければいいです。解く際は内側からループしましたが、外側からループしたほうが考察的には楽かもしれません。
ABC027 B - 島と橋
問題
提出コード
今日解いた中では一番難しかったと思います。
まずは島にいる人の合計を計算し、それがnで割り切れるかどうかで、答えが-1となるかどうかを判定します。
それが終わったら、最初の島から順番に橋を架けるかを判定していきます。
初期値を0とし、最初の島から順番に、島にいる人を足していきます。そして、足していった人数が、平均×足していった島の数になったときに、それを1つのグループとし、そのグループにだけ橋を架けます。終わったらまた次の島から人数を足していき、同じことをします。これを最後の島まで繰り返します。
実装で結構悩みました(グループを分ける条件文を間違えていたのにずっと気づきませんでした)。
ABC030 B - 時計盤
問題
提出コード
時計に関する問題は苦手です。どこかしらでミスをする印象が強いですね。
一周を720分割します(12時間が720分だからです)。短針も1分ごとに針が進むことに注意してください。
短針は1分で720分割のうちの1、長針は12進みます。一周が360度なので、長針と短針の差を2で割ったもののうち、小さい方が答えになります。
小さい方、という部分を読み飛ばさないようにしましょう(自分はこれが1WAした原因です)。
ABC035 B - ドローン
問題
提出コード
T=1のときは、左右、上下それぞれの差の絶対値を足したものに?の個数をたしたものが答えになります。
T=2のときは、少し場合分けが必要です。
上下、左右の差の絶対値をとって足したものが?の個数より多ければ引き算するだけでいいのですが、そうでない場合は、?の個数から先ほどの和を引いたものが2の倍数なら0、そうでない場合は1となります。
これもBにしては難しい気がします(そのための部分点だといえばその通りなのですが)。
ABC040 B - □□□□□
問題
提出コード
工夫すれば全探索が間に合います。
先にi枚のタイルを余らせる、とします。そのときに、のこったN-i枚のタイルで長方形を作るのですが、長方形にするにはN-i=j×kのようなjとkが存在してなければなりません。
そしてjを適当に決めたとき、kは(N-i)をjで割ったものであり、一意に決まります。つまり、(N-i)はjで割り切れないとき、一辺がjの長方形はつくれないのでスキップしても大丈夫です。
そして、jはk以下であると決めれば(もともとは、jとkは入れ替えても同じ答えになります)、jはsqrt(N-i)以下の場合だけを全探索すればいいことになります。
そして最後にiを0からN-1まで調べ、答えを求めれば良いです。
A問題並みに簡単な問題もたまにありましたが、実装ミスもかなり(計算上2回に1回ぐらいあることになりました…)あったので、集中力と実装力を鍛えなければなぁと思います。
2018/10/19追記
42以降も埋めました。記事はこちらになります。