情報オリンピック布教用チラシ

学校でプログラミング講習なるものをやっていたので、先生に言って受講生に配らせてもらったチラシです。なので、プログラムが少し書けることを前提に累積和を入れてあります。
デザイン能力が無いのでみんなで改善してね(?)
(配布の際は1,2ページを表面、3,4ページを裏面として、B4で印刷しました)

AGC011 A Airport Bus:実装の解説

A: Airport Bus - AtCoder Grand Contest 011 | AtCoder

解法:早く着いた人からバスに乗せていけば良いです。
以下、実装のテク。

  • バスには必ず一人以上乗っている。そのバスの出発時刻は保存しておく。

とします。 始めに、1番目の人をバスに乗せます(まだ誰もバスに乗っていないので例外処理)

i番目の人について、今搭乗中のバスの出発時刻より

  • 後にi番目の人が到着するなら、今のバスは出発させて、新しいバスにその人を乗せる
  • 先にi番目の人が到着するなら、
    • バスがいっぱいなら、今のバスは出発させて、新しいバスにその人を乗せる
    • バスに空きがあるなら、今のバスに乗る

最後に、最後のバスを出発させる。(このバスには一人以上必ず乗っている)

Tのソートを忘れないようにしてください。

僕のコード:Submission #1156589 - AtCoder Grand Contest 011 | AtCoder
このコードだと出発時刻じゃなくて搭乗はじめの時間を保存してますがまあ大体同じです。

SRM 245 Div2 Med (Problem 600) Flush:日本語訳のようなもの

フラッシュ

eiya君はフラッシュというカードゲームをしています。このゲームは、手札の中の同じマークのカードの枚数の最大値が得点になります。例えば、手札にスペード5枚、ハート2枚、他0枚の場合、5点です。eiya君はこのゲームを有利に進めたいです。

 

eiya君は今手札を持っていません。今からデッキからnumber枚のカードを引きます。デッキのカードはマークで4種類に分けることができ、これらはそれぞれS0,S1,S2,S3枚です。このとき、number枚のカードを引き終わった後のeiya君の得点の期待値を求めてください。

 

補足:例えば、1/2の確率で得点が3に、残り1/2の確率で得点が2になるとき、期待値は(0.5*3)+(0.5*2)=2.5です。

クラス定義

  • クラス名:Flush
  • メゾット:size
  • 引数:vector<int> , int
  • 戻り値型:double
  • メゾット宣言:double size(vector<int> S, int number)
(メゾットは必ずpublicにしてください)

制限

  • 実行時間2.000
  • メモリ (MB)64

注意

  • 値は32bit整数に収まらない可能性があります。
  • 答えは絶対誤差or相対誤差で10^-9以下になるようにしてください。

制約

  • |S|==4.
  • 0<=Si<=13
  • 0<=number<=Sの合計

テストケース例

  1. input
    • S { 2, 2, 2, 2 }
    • number 2
    output
    Returns 1.1428571428571428
    note
    始めに一枚引きます。次に1/7の確率で始めに引いたカードと同じマークのカードを引きます。
    得点の期待値は (1/7 * 2) + (6/7 * 1) = 8/7 = 1.1428571428571428です。
  2. input
    • S { 1, 4, 7, 10 }
    • number 22
    output
    Returns 10.0
    note
    全てのカードを引くため、一番大きい枚数の10が答えになります。
  3. input
    • S { 13, 13, 13, 13 }
    • number 49
    output
    Returns 13.0
    note
    48枚引いた段階で、少なくとも一つが13枚になっているか、全て12枚かのどちらかです。そこからさらに一枚引くので、少なくとも一つは13枚になります。
  4. input
    • S { 13, 13, 13, 13 }
    • number 26
    output
    Returns 8.351195960938014
  5. input
    • S { 13, 13, 13, 13 }
    • number 0
    output
    Returns 0.0

topcoderのstd::bad_alloc

topcoderでstd::bad_allocが投げられて、自分のコードのどこからもstd::bad_allocが投げられていないとき、それはtopcoder側の採点の際のCLASSのnewで投げられているかもしれない。

classの中に大きな配列を置くのはやめましょう。グローバルにしましょう。

あと、MLEの際はKILLされるので、なんかTLEでもないのにKILLされてるなーと思ったら、MLEを疑ってください。

 

(書きかけ)TopCoderの設定記録(Windows)

主に自分用。(書きかけなのに公開するなという話もある)
WindowsTopCoder環境を整える。

面倒な人へ

完成品が僕のgithub上にあげてあります。 topcoderアカウントの取得とjavaのインストールをした後、!TopCoder起動から立ち上げて、

  • Options->Editor->Common Class Pass
  • Options->Editor->Greed2のClass Pass
  • Options->Editor->Greed2のClass Pass
  • Options->Editor->Greed2のConfigure->Workspace

  • work/greed.confのexecute =の部分のパス

の計5か所のパスを指定しなおしてやれば使えるはずです。たぶん。

javaアプレットの用意

まずはjavaのインストールと、ContestAppletProd.jnlpjavaアプレットの本体)の入手をなんとかやります。(雑)
この時、こんな風にディレクトリを設置すると良いです。

絶対パス表記して、全角やスペースがないパス
└─ topcoder
     ├─ ContestAppletProd.jnlp
     └─ work
         ├─ Greed-2.0-RC-7.1.0.jar
         └─ 色々

その後、
javaの構成->セキュリティ->例外サイトリストの編集
から例外サイトにhttp://www.topcoder.comを追加。
ContestAppletProd.jnlpを開いて、下の画面が出れば成功。

f:id:eiya5498513:20170313170731p:plain

Greedを入れる

このままだと使いづらいので次は、Greedというプラグインを入れることを試みます。

参考:topcoderのSRMでGreedに乗り換え : 備忘録 - 裏紙

上のページに従えばプラグインを入れること自体は出来ました。(雑) ただし、Configureの部分は、/xxxx/yyyy/topcoder/SRMでなく、先ほど作ったworkフォルダへのパスにしておいてください。

Greedのカスタマイズ

ここからVS2017で使うために僕流の設定をしていきます。 目指すのは

です。

基本的に下のページに従っていきますが、これはLinux用みたいなので、一部変えていきます。
参考:TopCoder の強欲プラグイン、Greed を使う! - Qiita

Greed のカスタマイズ

greed.confを以下のようにします。解説は後。

greed.codeRoot = "${Contest.Name}"

greed.shared.templateDef.problem-desc {
  options {
    theme = darkgray
    gridArrays = true
  }
}
greed.language.cpp {
  longIntTypeName = int64_t
  templateDef {
    source.templateFile = template.cpp
    filetest.templateFile = tester.cpp
    script {
      overwrite = skip
      outputFile = "${Problem.Name}.script"
      templateFile = template.cpp
      afterFileGen {
        execute = "/CP_MAIN/topcoder/work/afterFileGen.bat"
        arguments = [ "${"Problem.Name"}", "${"Contest.Name"}" ]
      }
    }
  }
  templates = [ filetest, source, problem-desc, script ]
}

細かい解説は参考ページの方を見てください。

  • greed.codeRoot
    問題のhtmlやソースの出力フォルダです。デフォルトなので、書かなくても良いです。
  • greed.shared.templateDef.problem-desc
    出力する問題文のhtmlのデザイン設定です。
  • greed.language.cpp.longIntTypeName
    問題にlong longが出てきた場合のlong longの型名。(typedefは別に必要)
    LLにする人が多いと思う。
  • greed.language.cpp.templateDef.source.templateFile
    ソースコードのテンプレです。(後述)
  • greed.language.cpp.templateDef.filetest.templateFile
    テストコードのテンプレです。(後述)
  • greed.language.cpp.templateDef.script.overwrite
    skipを指定すると、問題を再度開いたときに、ソースを初期化しないようになります。
    backupを指定すると、今までのソースはバックアップされ、新しいソースが生成されます。
    skipでもhtmlを開きなおしたり、コンパイルする問題を変更したりする手間はどちらにせよかかるので、一長一短。
  • greed.language.cpp.templateDef.script.outputFile
    とりあえず問題名に依存する何かを書いておけば良いと思います。問題を既に開いたかのチェックに流用するので。
  • greed.language.cpp.templateDef.script.templateFile
    適当に存在するファイルを書いておけば良さそう。(理解していない)
  • greed.language.cpp.templateDef.script.afterFileGen.execute/arguments
    後で説明します。

ソースコードのテンプレ

こちらは実はいじらなくても良いのですが、一応僕のファイルを載せておきます。

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <sstream>

using std::string;
using std::vector;

${<if Problem.Description.Modulo}
  static constexpr int64_t MOD = ${Problem.Description.Modulo};
${<end}

struct ${ClassName} {
${<foreach Method.Params p}
  ${p.Type} ${p.Name};
${<end}
  ${Method.ReturnType} ${Method.Name}(${foreach Method.Params p , }${p.Type} ${p.Name}_${end}) {
    ${foreach Method.Params p , }${p.Name} = std::move(${p.Name}_)${end};
    return ${Method.ReturnType;zeroval};
  }
};

${CutBegin}
${<TestCode}
${CutEnd}

始めのincludeは片っ端から詰め込んだだけです。
using~ですが、using namespace std;で良いです。
僕は使いたくない派なのですが、Greedで生成されるテンプレで、stringやvectorが出てきてしまうのでこの二つはusingしています。
その次の良く分からないMODのようなものは、Greedが問題でMODが必要と認識してくれた場合に、有効になるようです。どうも完全ではないようですが。
あと、説明はしませんがこのテンプレでは、関数の引数をクラスのメンバ変数にmoveする式も埋め込んでいます。メモ化再帰やdfsを使うときなど、引数にとらずに参照できると便利なことも多いので。使えばわかると思います。

テストコードのテンプレ

こちらはいじらないと、VS2017でCE起こします。原因はstd::data::dataの競合です。using namespace std;許すまじ。
コンパイルできるようにカスタマイズすればなんでも良いんですが、面倒な人は僕のファイル(work/template.cpp)を使ってください。

afterFileGen

一通りファイルを生成した後の処理を書きます。外部プログラムの呼び出しなので、非常に自由度が高いです。

  • execute

<ここから書きかけ>

まずはVisual Studioのプロジェクトを適当な場所に作成します。 「ソリューションのディレクトリを作成」は外して「Win32コンソール」を「空のプロジェクト」で作成してください。 その後、

  • *.sln
  • *.vcxproj
  • *.vcxproj.filters

をworkにコピーします。 その後適当にSource.cppを作成し、プロジェクトに追加してください。