20190427のatcoder埋め

そこそこ時間が取れて、abc081から解いていった。過去に解いたことがある問題は飛ばしている。

abc081

  • c - 6:50でAC。
  • d - 解けずに諦めた。問題文を読み違えていて最小手順を求めなければいけないと思って完全に難しすぎると思っていたら、後から見たら手順の一例を出力すればよかった。
    • 反省
      • ちゃんと問題文を読む
      • まず簡単なケースで考えて、問題をその簡単なケースに変換できないか考えてみる

abc082

  • a - 1:10でAC。
  • b - 2:30でAC。
  • c - 3:40でAC。
  • d - 31:30でAC。５分くらい考えて方針がわからなかったので解答を見ようという気持ちに負けずに紙で具体的に考えたら方針が見えて、でもその方針だと計算量が2nになると思ったらdpで解決した。
    • 反省
      • 具体例を紙に書いて考えてみる
      • 問題がなぜ難しいと感じるのかを明確にして、その難しい点を回避するように問題を捉え直せないか考える
      • 全探索で計算量が足りなさそうだったらdpを検討する
      • dpの配列が疎の場合は配列じゃなくてハッシュでやったほうが考えやすいし速そう

abc083

  • a - 1:20でAC。
  • c - 4:10でAC。
  • d - 18:20でAC。なんとなく思いついた方針で確信がないままコードを書いてみたら通った。解答をみたらちゃんと解けることが証明されたアルゴリズムで解いてて感心した。

abc084

  • a - 0:40でAC。
  • b - 1:50でAC。
  • c - 9:00でAC。
  • d - 20:30でAC。n以下の素数の求め方を忘れていたのでエラトステネスの篩のやり方を検索してなんとかなった。最後、クエリに対して個数を数えるところで普通にやったらTLEになったので、Array#bsearch_indexを使ったら通った。

abc085

  • a - 1:00でAC。
  • d - 22:30でAC。少し考えたら方針がわかった。特定条件を考え忘れて一回REになってしまった。

abc086

  • b - 2:10でAC。
  • d - 解けずに諦めた。解説を読んでもよくわからんので一旦置いておいてあとで戻ってくる。

abc087

  • c - 3:50でAC。