seri::diary::competitive_programming

AtCoderで茶から赤を目指す競プロ精進日記

ABC144

atcoder.jp

結果

問題 ACまでに要した時間 AC WA TLE
A 2:40 1 0 0
B 7:41 1 1 0
C - 0 0 0
D - 0 0 0
Rating 順位
516 (-39) 4478

コメント

  • 久々のAtCoderコンペだったがおそらくこれまでで一番ひどい出来だった.
  • ABC143がエラく簡単だったので最近のABCはユルくなったのかと思ったがそんなことは全く無かった.
  • C問題,D問題をコンスタントに解けるようになりたい.どうすればいいのか..

所感

B問題

  • つまらないWAでめちゃくちゃRatingを失った.情けない.
  • 何をミスったかというと Yes NoYES NOtypoしてまさかの全WAをキメた.
  • 前にもLeetCodeで同じミスをしたことがある気がする.本当にもったいないので気をつけたい.

C問題

  • 回答中に考えていたこと

    • 最短経路となるi, jの組わせをどうやって決定するか?
    • 移動距離は目標の座標がa,bならば a + b - 2 になるが,これが最小になる座標をどうやって決定するか?
    • しかも探索範囲が広いのでどうやって計算量をへらすか?何も考えずに総当りすると,時間計算量は  \mathcal{O} \left( \displaystyle \frac {N ^ 2} {2} \right) となり,Nの最大値は 1012 なので確実にTLEする
  • どうすべきだったか

    • 25,30とかのわかりやすい値について検討すれば   \sqrt{N} までの範囲で探索すれば十分であるということはすぐわかったはず
    • Nの最大値にビビらずに総当りで解く方針を崩さずに考えればよかったのだが,いきなり「計算量の少ない方法があるのでは?」と疑って手が止まってしまったのは良くなかった
    • 提出数と正答率を見ても結構高めなのでそれほど難しい問題ではないはず.これは解けないといけなかった.

D問題

  • 回答中に考えていたこと
    • 水筒を二次元の図として捉えて,水筒を傾けたときに動く水面の位置の点(x,y)までの角度はstd::atan2(y, x)で求められるが,これと傾ける角度との相関性がわからない
    • ってかホントに二次元の図として捉えていいのか?多分傾ける角度と水面の位置は連動して動くから,水の三角柱の底辺の面積とかを考慮する必要はないはずだけど本当にそれでいいのか?(これは気にしなくていい話だった)
  • どうすべきだったか
    • atan2で角度を求めるところまでは正しいので,根気よく傾ける角度と動く水面までの角度との相関性を調べれば解けた可能性がある
    • 場合分けが必要だったので完答までいかなかったかも知れないが,それでもいくつかのテストケースは通せるぐらいの実装ができないと厳しい