読者です 読者をやめる 読者になる 読者になる

後期実験であったラピッドプログラミングについて

「ラピッドプログラミング」で検索してくる人がちらほらいるようなので今学期やった実験の内容をメモっておきます。うちの学科の後輩が見たら参考に・・・はならないか、どうも来年からカリキュラム変わるっぽいし。まあいいや、メモメモ。

  • そもラピッドプログラミングとは
    • rapid 速く、というわけで一定の時間制限(数十分〜時間のオーダー)をかけた中でプログラムを作成し、動かそうという趣旨。速く、正確にということで試験・コンテストや教育目的でやるようです。
    • 自分がやった実験はACM ICPCの問題のうち五段階評価で難易度1〜3.5程度の問題を3時間の実験中に何題解けるかなというものでした。
  • 内容・1日目
    • 基本的なIOが出来ていれば解ける問題をやりました。まあシステムに慣れようということです。
    • ちなみに入出力は標準入力を使ってリダイレクトするのが失敗少ないし楽です。
  • 2日目 似たもの・同じものを探す
    • まあソートして探せのアレでした。
    • 似たものを探す方法として「似たもの」の属する同値類で分類するハッシュを作って該当する同値類中だけで似たものを探す(例:距離d以内にある点を探すときに空間をd/2幅のメッシュで区切る)というのも紹介されましたが使いませんでした。
  • 3日目・組み合わせ探索
    • backtrack searchと基本的な枝刈りについて。まあこれはいくらでも詳しいサイトあるんじゃないかな。調べてないけど。
  • 4日目・動的計画法 Dynamic Programming
    • edit distanceとかのアレです。
    • 難易度3.5の問題として円周上の与えられたm点からn点を選び、それを頂点とするn角形の面積の最大値を求めよというのが出題されました。何をどう動的計画法するかは脚注*1に。
  • 5日目 まとめ
    • 2〜4日目で習った方法を使って解いてみようという感じ。

*1:適宜開始点Sを決め、Sから右回りにk(≦m)点を取り、このk点中j(≦k)点を選んで作るj角形の面積を最大にするのが部分問題。記録しておくのはk個の中からj個を選んで作れるj角形の最大のものの面積。Pのすぐ前の点Qをどれにするかは△SPQの面積を最大にするように選ぶ。S〜Qまでを使ってできるj-1角形の面積の最大のものは部分問題として計算・記憶済み。この問題ではどの点を選べばいいかまで記憶する必要はないことに注意。どの点を選ぶかも本質的に同じ方法で出来る