taki["blog"] = 2020 (R2)

社会人5年目(東京2年目)の日常

2020/9/13 ABC178

今日は珍しくABCEです.

f:id:takilog:20200913231115p:plain

  • Aはそのままです
  • Bは間はいらないので,4つの積のmaxでいいかなと思って提出したらいけました
  • Cは悩みました.とりあえず全ての候補が10Nなのは分かったので,あとはそこからいらない候補をマイナスすればよいか,と思ってとりあえずnaive実装を書いてみていました.結果として,10Nから9Nを2回引いて(0と9です),両方を足し直すために8Nしました.一度WAが出て「ん?」となりましたが,modがダメなところでした.Pypyはmodintがうまく入れられないので少しネックですね(C++だったらもっと簡単だったでしょうか?modpowを実装するので同じぐらいかもしれないですが,コピペしたらいけそうですね)
  • Dが分からず,DPの式を書いたのですが,答えが合わなかったのでEを見ました.
  • Eです.マンハッタン距離の最大で,ナイーブにはO(N2)ですが間に合いません.なんとなくですが,全部第一象限なので,適当に遠いところを計算すると良さそうとなり,ぐぐったらmaxのx+yとx-yで計算すればよいと分かったので実装したら通りました.ほぼコピペです(検索力).理屈としては|x-x'| + |y-y'|は,うまくabsを処理すると(x+y)と(x-y)に分けられる,みたいな分割が正当性がありそうです.

これは感想です. - Dは明らかにDPとは分かったのですが,式もそれっぽいものを立てていたのですが,もう少しでしたね(60分ほどD).頑張ってDPもなれていきましょう.