20190429のatcoder埋め

今日は、D問題がわからなくてもすぐ解説を見ずに頑張って考え続ける習慣を取り戻せたのでよかった。その分進みが悪いが...。最近ABCの過去問を埋め続けているが、C問題までは元からほぼ解けるしD問題は相変わらず解ける時は溶けるし解けない時は解けないので、なかなか成長が実感できない。

abc092

  • a - 1:40でAC。
  • b - 3:40でAC。
  • c - 9:20でAC。
  • d - 解けずに諦めた。解答見たら簡単だった…諦めるのが早すぎるので、次からもう少し考えるようにする。

abc093

a - 1:50でAC。 b - 3:40でAC。Nが109であることを見逃してて一回TLEになった。 c - 7:50でAC。 d - 解けずに諦めた。大体の方針はわかったけど、細かい場合分けを詰められなかった。解答を見たけど、どうやったらこの場合分けをちゃんと思いつくのかわからん。

abc094

  • a - 1:50でAC。
  • b - 2:50でAC。
  • c - 6:00でAC。
  • d - 14:30でAC。ようやく気付いたが、D問題はコンテストごとに点数が違って、今の実力だと400点だとだいたい解けて500点以上だとだいたい解けないっぽい。

abc095

  • a - 1:30でAC。
  • b - 1:50でAC。
  • c - 9:40でAC。
  • d - 解けずに諦めた。場合分けの仕方に見落としがあった。解説で言う所のf(a)だけでなくてg(a)まで事前に求めておくところが勉強になった。簡単な工夫で計算量のオーダーが落ちるのに気づかないことが多い。とにかく事前に求められるものは、都度求めるのではなく事前に求めておくことが大事。

20190428のatcoder埋め

今日は響けユーフォニアムの映画を見にいったので少しだけ。今までずっとrubyで解いてたけど、今後のことを考えるとpythonの方が良さそうな気がしたので今日からpythonで解いてみる。本当に今後を考えると完全にc++の方が良さそうだが、これは困るまで置いておく。

abc090

  • a - 2:30でAC。
  • b - 3:30でAC。
  • c - 5:10でAC。
  • d - 8:20でAC。今回のD問題は簡単だった。

abc091

  • a - 1:10でAC。
  • b - 11:30でAC。
  • c - 7:30でAC。Cにしては難しすぎる。たまたま前に同じような問題を解いたことがあったので解けた。
  • d - 解けずに諦めた。解説を読んでなんとなくは納得したけど解く気力が無いので置いておく。

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。

ABC125 の反省

ABC125に出たので反省します。

A問題

掛け算と割り算をして終わり。コード。

ここまで1:56。

B問題

配列を変換して足し上げて終わり。コード。

ここまで4:24。

C問題

とりあえずユークリッドの互除法を再帰的に使って云々すれば良いんだなと思ってやってみるが、TLE。rubyだからか？と思ってgoで書き直してみるも同じくTLE。その後、アドホックな高速化（ユークリッドの互除法の適用の仕方を変えたり、適当なメモ化をしたり）を試してみるけどTLE。最近abcの過去問埋めをしてるが、C問題を解けないことなんてほとんどないので悲しくて呆然と過ごしていた。科挙で頭が真っ白になって気が狂ってしまう人ってこういう感じなんだろうな...と思った（全然違うと思います）。

反省点として、計算量を落とすテクニックが足りていないと感じる。最初に計算しておくやり方だったり、n個の要素があった時に1個ずつ要素を増やしながら値を求めていくやり方（伝）だったり、よく見るはするが、いざという時に実践できないのでは困る。また、ユークリッドの互除法の計算量を把握せずに、闇雲に有効でない高速化を試したのもよくなかった。

ここで時間切れ。

D問題

C問題が解けなくてきれてる合間にちらちら見たがちょっと考えてわからなかったので放置。あとで順位表を見ると、CよりもDの方が全然簡単だったようだ。コンテストの途中で難しい問題があった時に順位表を見て、後の問題の難易度を見て場合によっては難しい問題を飛ばすというどうでも良すぎるTIPSを手に入れたので、次回から活かしたい。

反省

  • 実力が足りていないので過去問を解き続ける＋蟻本を解き続ける
  • 計算量の落とし方を上手くなる
  • 闇雲に高速化を試みるのではなく、現状の計算量とACに必要な計算量を把握して何をすれば良いか考える
  • 難しい問題があったら順位表を見てみる

以上です。