ABC062

README

ABC062過去問感想

• A問題はちょっと戸惑ったが、立ち止まってから使った解法が提示されている解答と同じだったためよかった
• B問題は文字列処理、たまにはこういったものもやっておきたい
• C問題はわからなくて答えを見た
  • 解答みても利用する性質の証明がなぜ？？となったが、冷静に状況を整理して考えると納得できた
    • ループさせるものがあと1つ減らせられればTLEしない、というケースの場合、なにか1つを固定して減らす、という発想を試みてもいいかもしれない
  • 結局は全探索に落ち着く、こういうのがちゃんと解けると良い
  • 形を変えて頻出するタイプの問題の香りがするので、覚えておきたい
• D問題
  • 最初に思いついた方法は、ヒープを用いる発想は間違ってはいなかったが、必ずしもうまくいくとは限らない方法だったため、WAしてしまった
    • 部分点が設定されている問題だが、方針が間違っていたため、部分点ももらえず
  • 配列を2つに分割して、それぞれの最大・最小の総和を考えるのが正解
    • これをあり得るすべての分け方（N通り）に対して全探索する！
  • heapはpush, popに対してリストの順序をキープしてくれるため、先頭だけでなく中身の全体的なチェックも可能であることを理解する！
  • 部分点がソートを利用した方法を許容するような配点だったことから、それを前提とした解法をまずは考えるべきだったかもしれない
    • 部分点が設定された問題を初めて解いたので、軽率に他の問題には適用できない