見出し画像

ABC163【D問題を少し復習】時間ギリギリだがACできたのはよかった

4月19日に、競技プログラミングサイトAtCoderで開催された競技プログラミングコンテスト「AtCoder Beginner Contest 163」に参加した。

【今回の結果】
     順位:3439 / 11548 (上位 30 %くらい)
    レート:665(Unratedのため変更なし)
パフォーマンス:-(Unratedのため変更なし)


全6問出題され、A、B、C、D問題をACすることができた。今回のD問題は(Unratedだが)およそ3割の方がACしている「少し難しい問題」。残り7分でACできたのは良かった。WAもなかったし。

【D問題を少し復習】

問題文はこちら

今回のD問題はざっくり言うと「和としてあり得るものの個数をmod(10の9乗+7)で求める」という問題。問題文のパッと見た感じ、

・組み合わせの数をどう上手に数えるか?コンビネーション使うパターンだ。

と発想し、実装していたが、なかなかうまくいかなかった。

「まぁ、200000回くらいのループで、組み合わせの数を計算するのは計算量が多すぎるよな。」

と思い、考え方を変えた。

出力例1の10通りの組み合わせを見ていると、

・10の100乗は無視していいな。
・+「なんとか」の「なんとか」部分は、1、2、3って綺麗に並んでるよな。
・これってKが違うのに同じ値になるというパターンはないよな。

文字でうまく表現できていないが、まぁなんとなく

・K個選んだときの最大値と最小値は式で表現できて、個数は最大値から最小値までの個数でいいんじゃないか。

という発想になり、ACにつながった。

今回は出力例として記載してくれていたから助かったものの、実際に条件に当てはまる値をいくつか書き出してみるのはやっぱり大事だな。
前回は発想の切り替えが時間外になってしまったが、今回は時間内にできACできた。過去問練習とかあんまりできていないが、この調子でがんばろう。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

スキありがとうございます!
1
三重県伊勢市でiOS・AndroidアプリのUX設計・UIデザイン・実装、Webサイト、Webアプリの情報設計、UIデザイン、実装を行なっています。また、競技プログラミングに参加したり、読書をしたり、2羽の文鳥と遊んだり、写真を撮ったり、洋菓子を作ったりしています。

この記事が入っているマガジン

AtCoder参加記録
AtCoder参加記録
  • 25本

AtCoderのABC等に参加した記録です。

コメントを投稿するには、 ログイン または 会員登録 をする必要があります。