ABC128 D Lamp
問題の解き方よりも実装のほうが大変だった問題。他の人の解き方を見て、条件分岐の少ない再実装をしました。配列の実装を1から始めるのがポイントのようです。
ABC128 C-Switches
典型的なbit演算の問題として自分なりに整理しました。
コンテスト時には、bitの配列として処理したものを、各bitを桁とする一つの数字にすると処理が簡単になるのが、目からウロコでした。
ただそれなりに独特の考え方をするので慣れていかなければと思います。
(特に入力時に苦労しました)
ARC 001 B リモコン
はじめ通貨問題のように貪欲法で解いたところ撃沈。
通貨問題では、使うコインをa,b,cと昇順に並べたときbが
aの倍数、cがbの倍数であれば、貪欲法が使えるが、この問題では
プラス・マイナス両側から近づくので使えないらしい。
回答をみてBFSで実装しました。温度に対する操作回数を保存するのは嫌だったので(温度がマイナスになる可能性もあるので)、mapを使いました。初めてBFSでmapを使いましたが、相性はいいと思います。
CODE FESTIVAL 2018 Final (Parallel) C - Telephone Charge
結構難しいlower_boundですが、面白い使い方を見つけたので、使ってみました。
イテレータから値を取り出す書き方は、auto x=*lower_bound(.....)といった*を使う方法しか知っていましたが、
一旦auto it=lower_bound(.....)とイテレータ自体を変数で受け取っておいてから,
it[0],it[-1],it[1]と前後の値も配列のように取り出す方法は知りませんでした。
配列の端っこのコーナケースを処理するのに便利そうです。
M-SOLUTIONS プロコンオープン E - Product of Arithmetic Progression
最近作った剰余演算用のライブラリを試すのにうってつけの問題。
nCmは使わないけど、累乗や逆数、そしておまけで作ったnPmの計算を使っています。
計算自体はよくある手法だと思うけど、配列をコンストラクタの中で初期化するので
サンプルごとにメモリの使用量が変化するのが見ていて楽しいです。
ABC128 B Guidebook
オブジェクトを作って、それに独自の順序を与える方法を
事前に調べていたので、僕にしては爆速で解くことができました。
典型問題
atcoderの問題はちょっと捻ったものが多いので、アルゴリズムを習得するために解くと良い典型問題が逆に少ない気がします。
そこで自分用のメモとして典型問題として使えるAtcoderの問題を上げておきます。
(主観的な意見なのであしからず)
- bit演算 ABC128 C - Switches
- 尺取り法 ABC98 D - Xor Sum 2