AtCoder Beginner Contest 203(Sponsored by Panasonic)の感想
AtCoder Beginner Contest 203(Sponsored by Panasonic)に参加してきました!結果はABCの3完(perf:937)でレートが44上がりました。以下簡単にコメントしていきます。
A - Chinchirorin
3つのサイコロを投げて、出目が全て揃ったらその値、出目が2つ被ったら残りの一つの出目、出目が揃わなかったら0を出力せよという問題。
前回に引き続きサイコロ問題。if文を使って出目が2つ被ったら残りの一つの出目を出力し、それ以外は0を出力するようにしました。こうすれば3つの出目が同じ場合もカバーできるのでコード長が短くて済んで衛生的です。
ここまでで1分38秒。なかなかいいペースで解けたと思います。
B - AtCoder Condominium
N階建てのマンションの各階にK部屋ある。i階のj部屋目の部屋番号をi0jとするとき、すべての部屋番号の総和を求めよという問題。
つまるところiとjは別々に考えてよいので、3桁目と1桁目で別々に計算して最後に和を取ることを考えました。注意すべきは1-indexにすることと、iの成分は3桁目なので100倍してから加えることぐらいですかね。
ここで5分18秒。悪くないペースだと思います。
C - Friends and Travel costs
所持金K円で村番号0の村からスタートして、なるべく番号が大きい村へ移動することを考えます。i村からi+1村へは1円のコストで移動することができ、訪れた村に友達がいる場合はB円もらうことができます。最終的にたどり着ける村を出力せよという問題。
問題文を見た瞬間この問題を思い出しました。
ABC185 B - Smartphone Addiction
今回の位置AでB円もらえるという条件は、この問題は時刻Tでバッテリーが(B-A)回復するのと同じように見ることができます。この問題ではすべての時刻でバッテリーをチェックするのではなく、バッテリーの充電タイミングでバッテリーが切れるかどうかのチェックをしていました。
そこで今回もお金を貰えるタイミングにその村にたどり着けるかのチェックを行い、
- すべての友人からお金をもらう
- 途中で所持金が0になる
タイミングで最終的な到達点を計算して出力しました。
ここまでで19分55秒。少し早いだけでパフォがかなり伸びたようなのでちょっと悔しいです。ただ類題にすぐに気づけたのは精進の成果がでたということなのでよかったと思います。
D - Pond
各マスに高さが与えられたN×Nマスのグリッド内に自由にK×Kの区画を取るとき、この区画内の最小の中央値を出力せよという問題。
中央値の扱い方が難しいなぁと思い初手でGoogle検索。「AtCoder 中央値」でggrと決め打ち二部探索法が出てきました。
決め打ち二部探索法は、競プロ典型90問やZONeコンに出題されていたのでかなり記憶に新しいですね。
【1 日目】
— E869120@公開アカウント (@e869120) 2021年3月29日
今日の典型問題です。解説は翌日の 7:40 に投稿されます。なお、要望が多かったので入力形式・入出力例を GitHub に追加しています。#競プロ典型90問 pic.twitter.com/cc8NTPhFLc
そこで「中央値がX以下になることがあるか」という判定条件で二分探索を行うことを考えました。この判定は各マスの値がXより大きいか否かで-1,1に変換して区画内の和を取れば出来そうです。ここで区画の和は二次元imos法か二次元累積和を使えば高速化できるとTwitterで見たことがあったので、今回は二次元累積和を採用することにしました。
【28 日目】
— E869120@公開アカウント (@e869120) 2021年4月29日
昨日の解説と今日の典型問題です。今日は標準的な難易度(★4)となっています。なお、AtCoder ジャッジには 15 時頃に追加される予定です。(昨日と同様、入力形式・入出力例は GitHub を参照のこと) #競プロ典型90問 pic.twitter.com/6bx90GPcQb
つまり流れとしては、
- 解をxと仮定して、各マスの高さとxを比較して-1と1に変換
- K×Kの区画内の和を二次元累積和を取り、中央値がX以下になるものが存在するかをチェックする。
- これを二分探索で知らべて条件を満たす境界の右側の値を出力
を実装しようと思っていました。
結局、二次元累積和の実装で失敗してしまい解けませんでした。
まとめ
最近精進はあまりできていませんでしたが、コンテストの復習と典型90を毎日考えることをしていたおかげか、問題文を見たときにあれ使えそうかな?みたいな発想が出やすくなった気がします。今回もD問題は解けませんでしたが解法は大きく外していなかったのでもう一息だと思います!(そう思いたいです)