TODO

Topcoder †

  • codeprocessorで何故か必要な部分がカットされちゃう
    • 変なことがあったら、一旦Removeしてもう一回設定しないと変更が反映されない
  • Options -> Setup User Preferences -> Editors -> Default Language
↑

問題の見方 †

  1. google翻訳に問題文を突っ込む
  2. 原始的順像
    1. 具体的な簡単な問題を自分の手で解こうと試みる。問題の概要を把握する。
    2. 明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
    3. その他、貪欲でいけるかなど、発想重視で色々考える。
  3. 求められる情報量の確認
    • yes-noか、max-minか、numかなど。
  4. 特性関数の作りやすさ
    • この答え（以上・以下）は問いの答えたりえるか？という質問に簡単に答えられるかを確認する。
  5. 計算量
    • アルゴリズムに要求される計算量のキツさを確認する。
  6. 頑張って実装
  7. テスト
    • 時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。
↑

Challenge †

  • vectorのチャレンジの仕方 
    hoge,foo,test
  • とすると、vector[3]={hoge, foo, test};となる。
  • 変なスペースはつけてはならない。
  • 最後にカンマをつけてはならない。
↑

虎本まとめ †

  • 探索
    • n次元の全探索
    • グラフの幅優先、深さ優先の全探索
      • しかし、格子状の道の最小ステップ経路の場合の数などでは、h*wの格子について$2^{h+w}$の探索をすることになる→メモリを使ってメモ化することで余分な探索を省く
    • 幅・深さ優先のメモ化可能性
      • まず、指数関数計算量の探索方法を考えることが重要。その後、複数のルートから同じ計算を行なっていないか（グラフ上で合流する部分はないか）をチェックする。
      • 返り値がある形でないとメモ化できない
      • 「それ以降に得られる〜」をメモ化する
    • メモ化からの漸化式構築＝動的計画法
      • 「これまでに得られる〜」をメモ化する
      • 幅・深さ優先探索のメモ化のときに保存した状態と、ここで計算するテーブルの状態変数は一致する？
      • 「ありえない組み合わせ」というものが存在する
      • まず、丸の中に「添字」や「重さ」や「価値」を書いたグラフを書いてみる！すると、合流を見つけることができる。合流を見つけると、その上流すべての情報を集めれば、その添え字での値が確定することになる。
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS