0.はじめに
昨日のARCは、参加はしてたけど1問も解けず記事にできませんでした・・・。
気を取り直してABCに臨んだところ、A~Dが快調に解け気分も上向き。
E以降は難しかったです。。
2023/4/12 Eの解説動画を見て理解できた＆新テクニックを
習得したので5.を追記
1.A - Double Click
設問内容は簡単だけど、実装は意外とややこしい感じ。
早さ優先であまり洗練した書き方になっていないながらもAC。
【考え方】
1)N=1の時は、ダブルクリってないので-１を表示
2)N>1の時、以下をN-1回繰り返す（変数i）
2-1)入力のリストをTとし、T[i+1]-T[i]<=Dを満たしたら
T[i+1]を出力して、プログラム終了
3)N-1回繰り返してもPGが終わってなかったら、条件を満たす
クリックは無かったということで、-１を出力して終了
https://atcoder.jp/contests/abc297/submissions/40457245
2.B - chess960
またまた、設問内容は簡単だけど、実装は意外とややこしい感じ。
早さ優先であまり洗練した書き方になっていないながらもAC。
Bの位置、Rの位置、Kの位置をそれぞれ配列(Kは変数)に格納し
IF文2つで条件を満たすか判定し、満たしてればYesそうでなければNoを出力
https://atcoder.jp/contests/abc297/submissions/40465244
3.C - PC on the Table
問題文を読むと、縦方向のチェックとかも必要かと思いきや
よく見たら、行の中でチェックは完結しそう。
入力行1つずつ、TTと並んでいる部分があったら
PCに置き換えた出力用行に複写していき
1行ずつ出力して終了
https://atcoder.jp/contests/abc297/submissions/40473655
4.D - Count Subtractions
まずは素直に実装。
例題は難なくクリアするも、問題上限である
10の18乗の数字をABに設定してテストするとTLEに。
TLEになるようなケース例
Aが10の18乗、Bが1 →素直な処理だと10の18乗回処理を回す必要がある。
上記ケースの省力化方法は、AとBの差をBで割った商（割り切れるときは商-１）＝
操作数となる。と気づき、それを軸に実装。
【実装】後から見るといろいろ短くできそうですが回答をもとに記載
1)A、Bを入力
2)変数ansを0で初期化
3)以下A!=Bの間繰り返す
3-1)A>Bの時
3-1-1)変数saにA-Bをセット
3-1-2)sa>B×2の時（AからBをマイナスする操作が繰り返されるとき）
3-1-2-1)sa%Bが0の時
3-1-2-1-1)変数syouにsa/B-1をセット
(1をマイナスしないと、この後の操作でAが0となり操作が1回多くなる)
3-1-2-1-2)AからBsyouをマイナス
3-1-2-1-3)ansにsyouを加算
3-1-2-2)sa%Bが0以外の時
3-1-2-2-1)変数syouにsa/Bをセット
3-1-2-2-2)AからBsyouをマイナス
3-1-2-2-3)ansにsyouを加算
3-1-3)sa<=B×2の時（AからBをマイナスする操作を1回したらABの大小が変わるとき）
3-1-3-1)AからBをマイナス
3-1-3-2)ansに1を加算
3-2)B>Aの時（3-1のABを逆に操作をするので略）
4)ansを出力
https://atcoder.jp/contests/abc297/submissions/40479097
5.E - Kth Takoyaki Set
https://www.youtube.com/watch?v=j6GEzcTqq-U
こちらの解説動画を見て理解できたので追記。
新テクニック ： set
重複しない要素のコレクション。
いままでわざわざ辞書型でやっていたことがこちらでできそう。
python学習過程で学んだはずだけど忘れてました。
新テクニック ： heapq
優先度付きque 最小値(最大値)を取り出したいときに便利
【考え方】
1個以上買うのが条件なので、0を0番目に安い値とする。
0番目に安い値に、リストAにある金額をそれぞれ足していった値を
取りうる金額リスト(以降q)に入れていく。
q内で一番安い金額が、全体でも一番安い金額となる。
(1回目の操作後に1番安い金額がq(heapq)の先頭に来る)
次に、1番安い金額をqから取り出すと、qには暫定2番目に安い金額が残る。
1番安い金額に、リストAにある金額をそれぞれ足していった値をqに
入れたのちに、q内で一番安い金額が、全体でも２番目に安い金額となる。
(2回目の操作後に2番安い金額がq(heapq)の先頭に来る)
これをK回繰り返した後のq(heapq)の先頭が
K番目に安い金額となる。
注意
heapqに重複した値が入らないように(同じ金額を支払う方法が複数存在する場合は 1 回だけ数える)
setリストを用意して管理する。
以上