ABC195(2021/03/14) 振り返り
余りの演算子使えますか？ってだけ。
よくわからなかったからとりあえず提出してみたけどWA。
入力例2を見ると、2種類のみかんの組み合わせを考えて解くの...？みたいに思ってしまってだいぶ時間ロスしてしまった。
Cを先に解いてから考え直したらぎりぎりACできたから、以下その説明。
例えば、入力例「A=300、B=333、W=1」の場合だと、
1000gを構成するのが1つのみかんだと1つあたりの重さは1000g、2つのみかんなら1つあたり500g、3つのみかんなら333.33...g、4つなら250g、...
って感じでどんどん増やしていって、1つあたりの重さが初めてB以下(かつA以上)になったときが最小の個数で、逆に、A未満になるぎりぎりの個数が最大の個数。
みたいな感じで考えた。
上の例では、A以上B以下を満たす個数は1つもないから、"UNSATISFIABLE"を出力する。
入力Nに対して、1~Nのループを行って、f(12345)=1、f(1234567)=2、みたいにカンマの個数を返す関数でも作ろうかなって思ったけど効率悪そうだからやめた。
カンマの位置ごとにそれぞれ考えることにした。
N=123,456,789 のとき、6と7の間にあるカンマは数値が1000以上のとき必ずある(=999以下のときのみない)から、その位置のカンマの数は(N-999)個ある。
同様に、3と4の間にあるカンマは(N-999999)個ある、...を繰り返すだけ。
(ただし、引き算の結果がマイナスの値になったらよくないから、いい感じのとこで打ち切るようにする)
って流れで書いてみて無事AC。
(後からコード読むと、for文の書き方とかちょっと読みずらいなって反省してる)
コンテスト中間の40分間くらい個人的な都合で参加できなかったせいで、順位的にはイマイチだったけど、ABCの過去問を少しずつ埋めれていることもあって灰色、茶色問題を安定して解けてよかった。
引き続きPAST本を読み進めつつ、灰色、茶色あたりは過去問全部埋めれるようにこつこつやることにする。
(反省：今回は振り返り書くのが遅すぎて最終的に完成したのが3/17 1:00だから、なるべく終了直後に書く)
この記事が気に入ったらサポートをしてみませんか？