構文解析のような問題です。個人的に競技プログラミングの問題としては初めての分野ですが、コーディング面接では何度か直面してきました。心をくくり、この問題と向き合うことにします。計算時間は無視して、正しい値を返すようなプログラムを考えてみることにします。30分ほど紙と向き合ってうんうん唸り続け、この問題はまずは次のようなサブ問題に分割できそうだと気づきます。入力文字列を上のように「括弧の対応が取れている文字列」(以下Good-String)に分割するのはスタックを使えばできそうです。あとはそれぞれのGood-Stringを独立に受け取って、それが合計何種類のGood-Stringを部分文字列として持つのかを計算する次のような関数を定義すれば良さそうです。これは再帰を使ってどんどんサブGood-Stringに分割して行くことで、なんとか計算できそうです。上のアイディアに基づき、Pythonで実装を行い、提出。残念TLEです!(実行制限時間を超過すること)。この時点で開始からおよそ90分が経過。トイレへと向かい、怒りを放尿します。上の提出でTLEにならなかったサンプルケースは全てAC(Accepted)でプログラムの動作としては信頼しても良さそうです。そこでC++でプログラムを書き換えることで高速化を図ることにしました。(ここでそもそもの計算量を疑えなかったのは大きな反省点です。冷静に考えれば、上のサブGood-Stringへの分割は毎回文字列長スキャンするうえ、再帰の深さは最悪の場合文字列長の1/2になるのでO(N2)であり、C++にしても意味の無い書き換えであることに気付けたはずです。)30分かけてC++に書き直し提出。TLEです!雲行きが怪しくなってきました。プレイリストをサザンオールスターズに変更し巻き返しを計ります。B問題Cは諦め、先ほど保留したB問題に戻ってきました。してクエリ間で共通する処理をくくり出したいです。しても10分ほど図を書きながら唸っていると、以下のような図が出来上がってきます。これは累積和か...?上の図で線として表現されている部分の累積和をO(N)で最初に計算しておくと、その引き算で基準点の左側の人々のコストが求まることに気付きます(図の丸で囲った部分)。累積和の関数cumは、最初に全てのXiについて値を求めておいて、cum(C)を求める時はCから最も近いXiのcum(Xi)に適宜必要な分だけ足し算すれば求まりそうです。近いXiは二分探索で求めることができるので、それぞれのクエリはO(logN)となり、無事に制限時間をクリアできそうです。ここから頑張ってC++で実装を開始しますが、ギリギリタイムアップ。悔しい試合となりました。懇親会オタクプログラミングバトルも終わり、お洒落な六本木の街に平穏が戻ってきました。C共に知っている人には典型問題だったようで、経験不足を痛感しました。復習し今回で自分のものとしたいです。結果自体は残念でしたが、久々に頭を長時間フル回転させる楽しい経験になりました。bitFlyerさん及びにAtcoderさんに改めてお礼申し上げます。»プロフィールid:reqly-tokyoプロの料理レシピ専門検索エンジンREQLY(レクリー)の開発ブログです。アーカイブはてなブログをはじめよう!reqly-tokyoさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。