2つの言語、1つのカップ。 RCC 2016ルールに関する考察

こんにちは、Habr！ 以下は、進行中のロシアコードカップ2016についての短い投稿です。あるいは、ウォームアップラウンドのタスクの1つに私を促した私の考えを掲載しています。

ラウンドの技術ルールはここで詳細に説明されます 。 それらをすべてコピーするのではなく、2つのポイントのみを強調します。

• 異なる言語（Java、Python、C / C ++ / C ++ 11、C＃、Perl、PHP、Ruby、D）でソリューションを送信できます
• すべてのタスクには、決定を実行するための時間制限があります

タスク「A」シークレットコード（直接リンク）についてです：

制限時間 2秒

256 MBのメモリ制限

説明

マーティは過去にあり、1985年に帰国したいと考えています。 彼はすでに両親と恋に落ち、プルトニウムを発見していました。 やらなければならないことは、タイムマシンの電源を入れて道路に行くことです。 ここでマーティは別のテストを待っています。 タイムマシンをオンにするには、シークレットコードを入力する必要があります。 シークレットコードを知っているのはDocだけです。 マーティは、コードを構成するすべての文字が異なることを知っており、文字数も知っています。 マーティはDocが到着するのを待っている間に、コードを推測し、さまざまな文字の組み合わせを入力しようとします。

あなたの仕事は、Martyが各リクエストに対して2つの数字を与えるプログラムを書くことです-その位置にある有効な文字の数と、コードに現れるが間違った位置にある文字の数。

入力形式

最初の行には、文字列s-秘密コードが含まれています。 コードはラテン大文字と数字で構成され、コード内のすべての文字は異なります。

2行目には、正の整数n（1≤n≤10 ⁵ ）-Martyの試行回数が含まれます。

次のn行には、マーティが導入する次の組み合わせが含まれています。 組み合わせもラテン大文字と数字で構成されます。 各組み合わせの文字は異なります。 各組み合わせの長さは、シークレットコードの長さと一致します。

出力形式

Martyクエリごとに2つの数字aとbを出力します。aはtrueの数、bはコード内で見つかったが間違った位置にある文字の数です。

例

入力データ：

BACKTO1985

3

BACKTO1958

BACKON1985

TOYEAR1985

出力データ：

8 2

8 1

4 3

---

解決策

タスクは難しくありません。 解決するためのトリックはほとんど必要ありません。

組み合わせをソートし、それぞれを文字ごとに秘密のコードと比較します。 次の文字のペアが一致しました-を増やします 。そうでない場合、この文字が秘密コードに存在するかどうかを確認します（秘密キーをシンボルキーを持つ連想配列に分解した後、条件付きの対数時間を探します）。 存在する場合、 bを増やします。

Rubyの簡単なソリューションを次に示します（コードは、ラウンド中に送信したものとまったく同じです）。

input = STDIN.read.split("\n") code = input[0] tries_count = (input[1]).to_i tries = input[2,tries_count] #puts code #puts tries_count #puts tries code_a = code.split(//) code_h = Hash[code_a.map {|x| [x, 1]}] #puts code_h tries.each do |t| total_right = 0 missed_right = 0 t.each_char.with_index do |c, i| if c == code[i] total_right += 1 else missed_right += 1 if code_h.has_key?(c) end end puts "#{total_right} #{missed_right}" end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

応答でTime Limit Exceededを受け取ったときの不満を想像してください。 さらに、面白いのは、ラウンドの終わりに、同じコードをもう一度送信することを楽しみにしていたことです。 そして彼はテストに合格しました！ つまり、ほとんどの場合、時間制限の寸前で実行されました。 私はそれを理解することにしました。

C ++で同一の（可能な限り）ソリューションを書きました：

 #include <iostream> #include <map> int main() { std::string code; std::getline(std::cin, code); std::string s_tries_count; std::getline(std::cin, s_tries_count); int tries_count = std::stoi(s_tries_count); std::string tries[tries_count]; for(int i = 0; i < tries_count; i++) { std::getline(std::cin, tries[i]); }; std::map<std::string, int> code_h; for (char& c : code) { std::string s(c, 1); code_h.insert(std::make_pair(s, 1)); } for (std::string t : tries) { int total_right = 0; int missed_right = 0; for (int i = 0; i < t.length(); i++) { if (t[i] == code[i]) { total_right++; } else { std::string s(t[i], 1); if (code_h.count(s)) { missed_right++; } } } std::cout << total_right << " " << missed_right << std::endl; } return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

はい、特にchar



からstring



へのこれらの変換のために、コードは悪いですが、Rubyで可能な限りソリューションを繰り返すという目標を設定しました。

<キャプテンの証拠>

そのため、C ++コードはRubyよりもはるかに高速に実行されました。

</キャプテンの証拠>

ラウンドの終了後すぐに、テスト入力セットが使用可能になり、コードNo. OPYB4R7JNHVGEKC3I6285TU90ASMFXLZW1Dと94432の組み合わせを含むLimit Exceededを初めて受け取ったテストNo. 17をダウンロードしました。

パフォーマンス測定

G ++ 4.8.4でコンパイルされたC ++

スクリプト：

 g++ -x c++ -std=c++0x -O2 -o ./solution1.a solutions/solution1.cpp && echo "solution1.cpp (with diff):" && time diff <( cat data/output.txt ) <( ./solution1.a < data/input.txt ) && echo "solution1.cpp (> dev/null):" && time ./solution1.a < data/input.txt > /dev/null
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

結論：

 solution1.cpp (with diff): real 0m0.411s user 0m0.341s sys 0m0.171s solution1.cpp (> dev/null): real 0m0.347s user 0m0.319s sys 0m0.028s
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Rubyバージョン1.9.3

スクリプト：

 echo "Ruby base solution (with diff):" && time diff <( cat data/output.txt ) <( ruby solutions/solution1.rb < data/input.txt ) && echo "Ruby base solution (> dev/null):" && time ruby solutions/solution1.rb < data/input.txt > /dev/null
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

結論：

 Ruby base solution (with diff): real 0m1.422s user 0m1.416s sys 0m0.009s Ruby base solution (> dev/null): real 0m1.413s user 0m1.404s sys 0m0.008s
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご覧のように、一般的には同様のアルゴリズムで、動作時間の3倍以上の差があります。

セット全体（テストNo. 17の入力/出力データ、cppおよびrbソース、パフォーマンスを構築および測定するためのスクリプト（* nixのみ））は、ここでgithubにコピーされました 。

私はまだキャプテンエビデンスタグを閉じていないと思うかもしれませんが、ここで私が議論のために提出している結論は次のとおりです。

• 各言語に独自のタスクがある現実の世界では、状況は絶対に公平です。
• しかし 、olympiadプログラミングでは、この状況はやや不公平だと思います
• 選手権では、まるで好みの楽器を配置しているかのようです。 実際、いくつかのツールは他のツールよりもはるかに効果的です
• はい、もちろん、Rubyは、私の頭の中で既に解決策が見つかったときに、コードを直接書く速度と使いやすさが向上しています。
• しかし、同等の能力を備えたRubyとC ++の専門家をまとめると、最初の専門家は、コードをより速く記述した場合、統計エラーの枠組み内に収まるに違いない
• 決定コードの実行時間に厳密なフレームワークを設定することにより、主催者は実際、一部の言語を他の言語より「より平等」にしますが、オリンピアードの目標はわずかに異なります
• ベルタワーから何を提案しますか？ ソリューションの計算の複雑さを評価します（ Big O ）！ 入力データの数nが増えると、コードの実行速度がどのように変化するかを確認してください。 また、たとえば、実行時間が線形数学O（n log（n））よりも大幅に速くなる場合、拒否する決定
• そして、はい、あなたは定数O（100500）のソリューションでcな仲間からの保護が必要になります

ご清聴ありがとうございました！ トピックに関するあなたの意見を知ることは非常に興味深いでしょう。