はむこの勉強記録

http://bit.ly/2ktf20t の写し

AtCoder 300点問題の傾向まとめ

だいたい

  • 大体1/3くらいは本当に2重3重ループしてれば終わる
  • あとの1/3くらいは素因数分解なりLCMなり連結性なりグラフなりsetとかの基本的なデータ構造が必要
  • あとの1/3くらいはbit全探索、combination全探索などの考察・実装や、DP初歩++、発想が必要な貪欲や累積和など、「アルゴリズム」が必要

勉強しないと身につかなそうなスキル

  • combination全探索
    • コーディングパターンとして持つ必要はない
    • そういう発想が必要というだけ
  • bit全探索
    • コーディングパターンとして持たないと解けない問題もあった
  • グラフの扱い方
    • 隣接グラフなり何でもよいから、とにかくグラフを持ち、最低限遷移をする程度の気持ちが必要
    • 連結性判断くらいは必要っぽい(Union Findを持っていれば殴れる)
  • 「階段を1段飛ばしor2段飛ばし」のDPに毛を生やした程度のDP力

ABC Only

  • 51C 構成、コーナーケースに注意するだけ
  • 57C 約数を全探索するだけ
  • 54C グラフを扱う必要がある。permtationの全探索も必要
  • 61C バケットソート的な発想が必要
  • 64C コーナーケースに注意するだけ
  • 70C LCMを取るだけ
  • 73C setのinsert, eraseを使って愚直シミュレーション
  • 75C 辺を全探索しながら、グラフの連結性を判断していく
  • 76C 二重ループの中のループで「すべての〜が満たされる」を判定するだけ
  • 79C 8個場合分けするだけ
  • 80C 3重ループするだけ。読解ゲー
  • 84C 二重ループしてシミュレーションするだけ
  • 87C a+b+c=nみたいなやつは変数が3つでも自由度が2つだけっていう典型
  • 88C 一次方程式をいじくるだけ
  • 89C(難) 頻度を取って、5C3の全列挙をする中で場合の数を足しこんでいく。全列挙は10個なのでcombination全探索をしてもいいし、10行書いてもよい。
  • 96C 盤面なんだが配列外参照が怖いので番兵をおいたりして工夫したほうが良い
  • 99C(難) よくある「階段を1段飛ばしor2段飛ばし」系のDPするんだが、遷移が多いのでちょっと工夫がいる。
  • 100C 流石にこれはやるだけ…

ABC/ARC

  • 58C 二重ループの中で「すべての〜が満たされる」の判定をやる
  • 60C(難) いやこれCじゃないでしょ。3次元DPをする。
  • 62C ガウス記号系の数学をやる
  • 64C 貪欲なので発想力が必要
  • 65C(難) 貪欲だと明らかに死ぬので、状態遷移図を気合でまとめてく
  • 66C(難) 解を一例あげる
  • 67C 素因数分解するだけ
  • 68C 貪欲なので発想力が必要
  • 69C 貪欲なので発想力が必要
  • 71C 頻度を数えて最小値を取るだけ
  • 72C 貪欲なので発想力が(ry
  • 73C 気合い実装するだけだが実装めんどそう。UFなりなんなりを使って脳の負荷を下げたい。