C++ の動作確認をしてみた(8)

C++の練習を兼ねて, AtCoder Beginner Contest 077 の 問題C(Snuke Festival)を解いてみた.

■感想.
① N が 最大 10の5乗 と指示があったので, for文 の 3重ループは, TLE になると推測し, 二分探索などを模索した.
② lower_bound, upper_bound という便利な関数が用意されていることが, ネット上の情報で判明したので, 計算量削減に使えないか, 検討してみた.
③ 最初, A を 基準に試行錯誤してみたが, 条件を満たす組み合わせの数え上げが上手くいかず, 次に, B を 基準に試行錯誤してみたところ, 条件を満たす組み合わせの数え上げが上手くいった.
④ 本家の解答を見たところ, おおよそ解答方針が一致していたので, 時間かかってしまったものの, とりあえず粘ってみた甲斐があったと思われる.


本家のサイトARC084/ABC077 解説をご覧下さい。


■C++版プログラム


■参照サイト
AtCoder Beginner Contest 077
lower_bound、upper_boundの基本的な使い方

カテゴリーC++

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください