AtCoder Beginner Contest #119
A. Still TBD
0埋めされた数をきちんとscanfで読めるか不安だったのだがどうやらできるらしい. 解答例
また文字列の辞書順比較でもよかったらしい.
B. Digital Gifts
換算して合計する. 解答例
C. Synthetic Kadomatsu
正答率が低い問題.300点とはいえ私の苦手な操作の特性を考える系の問題が解けたのは大きいと思っている. 解答例
まずに注目して何らかの全列挙を考えるが,すべての操作について全列挙するのは流石に間に合わなそう.ここで延長/短縮魔法は合成魔法の後に使っても同じであることに注目すると,合成結果を全列挙してから延長/短縮を行えばよいことが分かる.全列挙の計算量はが小さいので問題ない.
これにより合成結果が列挙できたから,これに延長/短縮魔法を適用してA,B,Cの候補を選べばよい.これは順序を入れ替えて,A,B,Cの候補を選んでからA,B,Cに揃うように魔法をかければよい.候補をうまく選ぶ方法は割と考えにくそうだが,実はこれも全列挙で間に合う:3重ループでA,B,Cの候補を適当に選んで差を計算すればよい.
別解(editorial)
竹の用法は「Aに使う,Bに使う,Cに使う,使わない」の4通り.よってこの通りを試行すればよい.合成回数について:使わなかった竹の本数をとおくと,本の竹が合成によって3本になる.一回の合成で竹が1本減ることから合成の回数は回となる. 解答例
D. Lazy Faith
最近のABC-Dにしては簡単.最初のACコード(綺麗なものは下掲): 解答例
各をそれぞれ配列に入れておく.すると各に対してを二分探索すれば,左右についてに最も近い値が得られる.存在しない場合が面倒で,変な関数を作ってしまった.もうちょっと簡潔に書けたとは思うが.
移動の方法は次の8つ:
- (折り返す)
これはまず(直進)と(折り返し)を考え,左右反転版を考え,最後に訪れる順番がとなるものを考えることで列挙した.このうち上4つは次のように纏められる(下4つも纏めると却って複雑になるため行わない):
これらのコストを愚直に計算して最小値を取ればよい.コスト計算を1箇所凡ミスして1WA.
editorialでは配列の先頭と末尾に-infとinfを加えている.こうすると二分探索で現れるindexが必ず配列の範囲内になるから取り扱いが楽になる.これは覚えておきたい.このテクニックを用いたコード: 解答例
なお私の解法では1クエリに対して4回二分探索を行ってを求めているのだが,editorialでは「」という性質を利用して2回に抑えている.確かにはを満たす最小の候補であるからは未満であり,これはを満たす最大の候補(本問ではと等しくなるようなは存在しない).