Tsuna lab

国の端っこで---しながら競技プログラミングなるものをしてみます

AtCoder Beginner Contest 203(Sponsored by Panasonic)の感想

AtCoder Beginner Contest 203(Sponsored by Panasonic)に参加してきました!結果はABCの3完(perf:937)でレートが44上がりました。以下簡単にコメントしていきます。

 

A - Chinchirorin

atcoder.jp

3つのサイコロを投げて、出目が全て揃ったらその値、出目が2つ被ったら残りの一つの出目、出目が揃わなかったら0を出力せよという問題。

前回に引き続きサイコロ問題。if文を使って出目が2つ被ったら残りの一つの出目を出力し、それ以外は0を出力するようにしました。こうすれば3つの出目が同じ場合もカバーできるのでコード長が短くて済んで衛生的です。

ここまでで1分38秒。なかなかいいペースで解けたと思います。 

B - AtCoder Condominium

atcoder.jp

N階建てのマンションの各階にK部屋ある。i階のj部屋目の部屋番号をi0jとするとき、すべての部屋番号の総和を求めよという問題。

つまるところiとjは別々に考えてよいので、3桁目と1桁目で別々に計算して最後に和を取ることを考えました。注意すべきは1-indexにすることと、iの成分は3桁目なので100倍してから加えることぐらいですかね。

ここで5分18秒。悪くないペースだと思います。

C - Friends and Travel costs

atcoder.jp

所持金K円で村番号0の村からスタートして、なるべく番号が大きい村へ移動することを考えます。i村からi+1村へは1円のコストで移動することができ、訪れた村に友達がいる場合はB円もらうことができます。最終的にたどり着ける村を出力せよという問題。

問題文を見た瞬間この問題を思い出しました。

ABC185 B - Smartphone Addiction

atcoder.jp

今回の位置AでB円もらえるという条件は、この問題は時刻Tでバッテリーが(B-A)回復するのと同じように見ることができます。この問題ではすべての時刻でバッテリーをチェックするのではなく、バッテリーの充電タイミングでバッテリーが切れるかどうかのチェックをしていました。

そこで今回もお金を貰えるタイミングにその村にたどり着けるかのチェックを行い、

  • すべての友人からお金をもらう
  • 途中で所持金が0になる

タイミングで最終的な到達点を計算して出力しました。

ここまでで19分55秒。少し早いだけでパフォがかなり伸びたようなのでちょっと悔しいです。ただ類題にすぐに気づけたのは精進の成果がでたということなのでよかったと思います。

D - Pond

atcoder.jp

各マスに高さが与えられたN×Nマスのグリッド内に自由にK×Kの区画を取るとき、この区画内の最小の中央値を出力せよという問題。

中央値の扱い方が難しいなぁと思い初手でGoogle検索。「AtCoder 中央値」でggrと決め打ち二部探索法が出てきました。

決め打ち二部探索法は、競プロ典型90問やZONeコンに出題されていたのでかなり記憶に新しいですね。

 

atcoder.jp

 そこで「中央値がX以下になることがあるか」という判定条件で二分探索を行うことを考えました。この判定は各マスの値がXより大きいか否かで-1,1に変換して区画内の和を取れば出来そうです。ここで区画の和は二次元imos法か二次元累積和を使えば高速化できるとTwitterで見たことがあったので、今回は二次元累積和を採用することにしました。

 つまり流れとしては、

  1. 解をxと仮定して、各マスの高さとxを比較して-1と1に変換
  2. K×Kの区画内の和を二次元累積和を取り、中央値がX以下になるものが存在するかをチェックする。
  3. これを二分探索で知らべて条件を満たす境界の右側の値を出力

を実装しようと思っていました。

結局、二次元累積和の実装で失敗してしまい解けませんでした。

まとめ

最近精進はあまりできていませんでしたが、コンテストの復習と典型90を毎日考えることをしていたおかげか、問題文を見たときにあれ使えそうかな?みたいな発想が出やすくなった気がします。今回もD問題は解けませんでしたが解法は大きく外していなかったのでもう一息だと思います!(そう思いたいです)