AtCoder Beginner Contest119
AtCoder Beginner Contest 119に参加しました。
本番ではA問題とB問題を解くことが出来ました。今回のコンテストに向けて過去問を001から005まで解いてきましたが、その様な古い問題とは何となく傾向が違うのかなと感じました。古い問題よりも新しい問題に優先的に触れた方が良いとのアドバイスを何回か貰っているのでそうしていこうと思っています。
今回のコンテストで特に悔しく感じたのがC問題を解けなかった事でした。ABC002のD問題やABC113のD問題で学んだように、プログラミングを用いて問題を解くことの大きなメリットとして総当たりで探索できることがあります。今回のC問題も総当たりで探索すれば解ける問題でしたがその発想に至れなかったことが残念です。 D問題も解法自体は思いついたのですが、実装が上手くいかずに解けませんでした。C++の使い方を一つ一つ覚えていくしかないですね。
C問題
今回の問題が与えられた竹それぞれについて「Aに使う、Bに使う、Cに使う、使わない」の4(22)通りなので4進数を用いて実装できました。 パターンがそれ以上ある場合は深さ優先探索(DFS)を用いると良いみたいです。深さ優先探索聞いたことあるけどよく知らないな～と思って調べてみたところ、以前解いたABC113-D.Number of Amidakujiで僕が最初に思いついたけど上手くいかなかったアルゴリズムの事みたいです。振り返り記事では「再帰的に潜っていく」など表現していますがちゃんとアルゴリズムに名前ついていたんですね。何か伏線回収されたような気分です。 深さ優先探索のほかにも幅優先探索などのアルゴリズムもあります。それぞれ実行時間やメモリに問題がある場合があるのでメモ化などとうまく組み合わせる必要があるかもしれません。
また、同じくらいの難易度の問題としてARC092-C問題をオススメされたのでそのうち解いてみようと思います。
D問題
解法はすぐ思いつきましたが、実装に手間取りました。学んだことを覚書します。
lower_bound
ソート済みの配列の、任意の要素以上の要素の場所を二分探索する関数としてlower_boundがあります。論理値を返すbinary_searchと違って探したい要素の位置が分かるのが大きなメリットです。取得されるのはイテレーターとなるので以下のように扱うと良いみたいです。
//size_t : コンテナの要素数などを表現するために用いられる. //distance : イテレータ間の距離を求める.下の処理で配列sのいくつ目の要素かが分かる. //lower_bound(first, last, value) : first-last間でvalue以上の最初の要素.もしなければlastが返る. size_t spos = distance(s.begin(), lower_bound(s.begin(), s.end(), x)); }
lower_boundの使い方も、過去問を解いていく中でvectorやiteratorに触れていなければすっと入っていなかったとは思います。問題を解くことは出来なかったけど一応勉強の成果は感じました。
探索を行うときはINFを使う
lower_boundで二分探索を行うとき、見つけたい値以上、以下が無いと望んだ挙動をしない場合があります。そこで配列の先頭に十分小さな値を、配列の最後に十分大きな値をぶち込んでおくと気持ちよく動いてくれます。無限遠に建つ神社や寺を想像すると面白いですね。
まとめ
まずは全探索を疑う事。深さ優先探索や幅優先探索を自分で実装してみること。lower_boundの使い方になれること。long long型を使う事。古い問題だけでなく新しい方の問題にも触れて行く事。C問題以降が解けなかったのは悔しいのでもうちょっと勉強して次のコンテストではC問題まで解ける状態に持っていきたいです。まずは毎日勉強ですね。
参考文献
cpprefjp - C++日本語リファレンス
「size_t」
「distance」
