0.はじめに
歯ごたえを感じつつも、C問題までは順調に解け、Dは挑戦はできたくらいの
自分なりには満足できた回でした。
レートはちょい上げの+5。でも暫定みたいです。
不正者が多かったとのことですが、その結果後で上がるのかさがるのか・・・。
運営者の方に余計な手間を掛けさせないでほしいものです・・・。
1.A - 321-like Checker
インプットを文字列にして、
スライスしつつ頭からチェックをしていきました。
C問題に続く問題のようです。
https://atcoder.jp/contests/abc321/submissions/45819331
2.B - Cutoff
Bにしてはなかなか歯ごたえのある問題でした。
4つに場合分けして考えました（3つでよかったのかも・・・）
まず、リストAをソートして
１）一番大きい数字を除外して合計してもXを超える場合
→最後は0点でもOKなので、0を出力
２）一番小さい数字を除外して合計した数字がXと同じ場合
→最後は最大の得点以上であればOKなので、リスト内の最大値を出力
３）一番小さい数字を除外して合計した数字がXより大きい場合
→最後は最大の得点より小さくてもOKなので
最小値を求める
→Ｘから、リストから最小値と最大値を除外した合計を引いた
値が答えとなるのでそれを出力して終了
４）上記に当てはまらない場合は、どうあがいてもだめなので
-1を出力して終了。
https://atcoder.jp/contests/abc321/submissions/45830093
3.C - 321-like Searcher
ためしに、ansを1ずつ増やしていって、321-like Number(以下321数)の場合
カウントしていき、カウントがKと一致したら、その数字を
出力としたところ、例題は行けたけど、1000位でタイムアウトに。
諦めて真面目に実装。
1）Kを読み込み
2)リストLを用意、10を15個で初期化(ほんとは11でいいけどなんとなく)
リストL:L[0]に回答の1桁目、L[1]に2桁目、L[n]にn-1桁目がセットされる。
初期値は10で10の場合はそこまで桁が行っていない。
3)変数NKを0で定義（今何個目の321数かを保持）
4)リストL[0]に0をセット
--以下関数LP--
関数LP 引数はリストLとi(Lのどの位置に加算するか)
返り値はリストL
LP1)L[i]に1を加算
LP2)L[i]がL[i+1]以上の時→321数をみたさないので繰り上がり処理
LP2-1)L[i]に0をセット
LP2-2)L[i+1]が10の時(繰上りによる新桁の時)
LP2-2-1)L[i+1]に1をセット
LP2-3)L[i+1]が10以外の時(繰上りによる新桁でない時)
LP2-3-1)LP(L,i+1)をコール
LP3)Lを返す
--以下4の続き--
5)NKがKと同じになるまで以下くりかえし
5-1)NKに1加算
5-2)LにLP(L,0)をセット
※繰上りにより、321数が崩れていないかチェック
5-3)リストLを頭から見ていく
5-3-1)L[i]==L[i+1]の時
5-3-1-1)NKを1減算（加算処理をもう一回。）
5-3-1-2)5-3のループを抜ける
5-3-2)L[i]==10の時(問題なし)
5-3-2-1)5-3のループを抜ける
6)ansを””で初期化
7)以下、11回くりかえし
7-1)L[i]が10でない場合
7-1-1)L[i]を文字型にしansに+
8)ansを逆向きに変換
9)ansを出力して終了
我ながら無駄にややこしい感じに実装した感じですが
解説をみるとなんか、全然違うような感じな回答でした。
最初5-3辺りを実装していなかったため、3桁目あたりでansが100となってしまい
321数ではなくなってしまう。
5-3あたりは強引なロジックつけ足しでしたがなんとなくうまくいきました。
https://atcoder.jp/contests/abc321/submissions/45867675
4.D - Set Menu
まずは、素直に実装。
AC9、TLE21とけっこうなTLE。
A、Bを昇順に並べて、P-AでBを2分探索し
A+Bが値段になるのか、Pが値段となるのかの境目を
もとめ・・・と工夫しようと四苦八苦しているうちに
時間終了。
解説を見ると、Bの累積話を用意することで簡潔に
回答していて目からうろこでした。
C++の解答例を丸パクリして、Pythonで書き直し
とりあえず試験後にAC頂いときました。
C++の2分探索関数lower_boundはpythonで
bisect.bisect_rightを使えばよいことをググって学びました。
https://atcoder.jp/contests/abc321/submissions/45888403
以上