たくあんポリポリ

勉強したことを載せていきます。最近、技術系の記事はZennに書いています。(https://zenn.dev/chittai)

【C#】AtCoder Grand Contest 038 のA問題に正解した

AtCoder Grand Contest で初めてA問題が解けたので、その時の思考について残しておこうと思います。(初めてと言っても、過去2回しか参加したことないけど・・・)

atcoder.jp

A問題の概要

A問題は300点問題なので、ABCにおけるC問題ぐらいの難易度だと思います。実際は、最近のC問題よりも少し難しい印象を受けましたが。

  • H行W列からなるマス目
  • そのマス目には 0 or 1 が書かれている
  • 入力として”H W A B”が与えられる
  • Aとは、”行に含まれる0と1の個数を数え、その個数で小さい方の値がAとなる”
  • Bとは、”列に含まれる0と1の個数を数え、その個数で小さい方の値がBとなる”
  • 出力は、この入力を満たすように各マスに 0 or 1 を書き込めるか判定し、可能な場合は条件を満たす書き込み型を1つ出力する

思考の順番

例の確認

正直、問題の意味はわかっても、なんかピンとこなかったので例を確認しました。ここで、入力例と出力例をみてゴールイメージを固めました。これは、他の人もやっていると思いますが、出力までちゃんとイメージを固めないと、結局なにやりたいんだっけ?となることがあります。(自分だけかも?)

満たさない条件について考えてみる

次は、問題を読んで、満たす条件がすぐに思いつかなかったので、”じゃあ逆に満たさない条件がわかれば、それ以外満たせると言えるのでは?”と思い、満たさない条件について考えてみました。

f:id:c_taquna:20190922163018j:plain:w500

例を参考にしてNGなパターンについて考えてみました。”3 3 2 2”を入力します。これは感覚的な話なのですが、入力されたABが前回の値に1がプラスされ、2になっているので、前回個数の小さい方だった1を各行に追加してみました。そうすると、今回は0のほうが少なくなってしまい、”正しい”ABは”1”となってしまいました。

この時に、入力されたAが、列の値(W)の半分より大きい場合、条件を満たすことができないことに気がつくことができます。そして、Bも同様で、行の値(H)の半分より大きい場合、条件を満たせません。

なぜなら、0でも1でも、半分より多い数が書き込まれると、もう一方の方の個数の値がほうが、小さくなってしまうからです。つまり、どんなに頑張っても取れるABの値はW/2, H/2以下となります

ここで、あらためて与えられた制約を見てみましょう。

  • 0≤2×A≤W
  • 0≤B2×B≤H

AとBの2倍がHとW以下。つまり、AとBは最大でもW/2, H/2しか入力されません。ということは、前に説明した条件を考慮すると、Noとなる値は入力されないので、Noになるパターンは考えなくていいことに気が付きます。(私は解いている間この制約に気が付かなかったので、条件を書いてしまいましたが。。。)

あらためて満たす条件について考えてみる

上記から、入力されるすべてが条件を満たすということがわかりました。つまり、あとはその条件を満たすマス目を作成することができればOKです。

ここで、試しに5 5のマス目について考えてみましょう。ABは最大で2までしか取らないので、ABは2としておきます。

f:id:c_taquna:20190922230108j:plain:w500

左図のほうは、条件を満たすように適当に配置しました。ただ、このままだとコードに落とせないので、なにか法則性がないか探しました。それが右図になります。

このあたり、言語化できてなくてうまく説明できていないのですが、絵を書いてるうちに、”あ、これでいけるんじゃない?”となりました。ここまでくると、あとはコードを書くだけなのですが、HxW回処理を回すとTLEになってしまいました。

なので、今回は2種類の配列を作成し、それを文字列化してH回処理を回すようにしたところACを取ることができました。

実装について

コードは下記に載っています。

github.com

感想

今回は特別アルゴリズムを知っているかどうかより、絵を書いたりして、ちゃんと問題の性質だったり法則を理解することが重要なんじゃないかなと思いました。

AtCoderの過去問をときまくっていると、このあたりの考え方が鍛えられていくので、これからもどんどん解いていきたいと思います。