0.はじめに
今一調子に乗り切れない今日この頃。
今回はABCを順調にクリアしましたが、D問題でブレーキ。
小手先のTLE対策で何とかなるかと思いましたが
最後の方で根本的な考え方の違いに気づき修正するも時間切れ。
3問正解だったのでちょっとだけレートは上がり、+6の756と
またもや微増でした。
1. A - Black Square
A問題なのに一見ややこしそうな問題。
とはいえ、よく読めばXとYの範囲がそれぞれともに
PとQから+99マス以内にあれば条件を満たすので
それを判断してYes or Noを出力してACとなりました。
https://atcoder.jp/contests/abc441/submissions/72502305
2.B - Two Languages
こちらもBとしてはまぁまぁ難しい問題。
最初勘違いしていて解答自体は変なロジックになっていますが
単語の文字毎にがSとTにある数をそれぞれカウントし
単語の文字数とそれぞれのカウント数がどちらかのみ一致すれば
一致した方の名前を、両方一致したらUnknownを出力することで
ACとなりました。
https://atcoder.jp/contests/abc441/submissions/72517509
3.C - Sake or Water
一転、C問題にしては簡単だった問題。
【考え方】
・最悪のケース（一番液体を選ばないといけないケース）は
カップ内の液体の量が多い方からN-K分水が入っていて
それ以外のKカップに日本酒が入っている時
・その場合にXml以上酒を得るには
少ない方からKカップ内の多い方から
Xmlを超えるまでカップを選べばよい
【実装】
1.N,K,XとリストA(index-0)を入力する
2.リストAを昇順ソートする
3.変数sml(飲んだ酒の量を保持)変数C(飲んだカップの数)を0で初期化
4.以下、iをK-1から0までの間1ずつ減らして繰り返す
-1.smlにA[i]を加算
-2.Cに1を加算
-3.smlがX以上の時C+NからKを引いたものを出力して終了
5.ループが終わってもsmlがX以上にならない場合は-1を出力して終了
https://atcoder.jp/contests/abc441/submissions/72524742
4.D - Paid Walk
一見難しそうですが、Lが10以下という制限があるので
何とかなりそうと思い取り掛かりましたが、てこずりました。
【誤った方法】
・スタートする頂点を１～Nまで設定して繰り返し
条件に見合う形で1に到達できれば回答用リストに登録
最後にリストを出力して終了
この方法だと、４の10乗をN回繰り返すことになりTLE
時間終了間際、こういう問題では１から各頂点に到達する形で
1回の４の10乗の走査で問題を回答できると思い出し何とかしようと
しましたが、ACとなったのは終了6分後でした・・・。
https://atcoder.jp/contests/abc441/submissions/72561183
以上