トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

競技プログラミング指針

[競技プログラミング,アルゴリズム]

問題を見たとき、どの方向に行くべきか簡単な指針を作りたい

標準入力からのEOFまでのテンプレート

問題を解くための共通フォーマットを用意しとくだで

  Ruby

  • とりあえず入力値をうけとるだけ
    • ヒアドキュメントで入力値をデバッグする
#lines = <<'EOS'
#abcdeffg
#EOS

lines = $stdin.read
array = lines.split("\n")

puts "#{answer}"

  Crystal

  • Crystalのヒアドキュメントは <<-EOS
#lines = <<-EOS
#abcdeffg
#EOS
#array = lines.split("\n")

array = STDIN.each_line.map{|line| line.dup}

array.each do |e|
    puts e
end

  D言語

  • dmd main.d && ./main で実行する
import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;
 
//string lines = q"[
//abcdeffg]";

void main()
{

  string lines;
  string buf;

  while (!stdin.eof) {
    buf = stdin.readln();
    lines ~= buf;
  }

  string[] array = splitLines(lines);
  writeln(to!string(array));
}

高階関数

  Ruby

  • こういうのをやりたいのですよ
a = array.map{|e| e.split(" ")[0].to_i }
b = array.map{|e| e.split(" ")[1].to_i }

except = array.map do |s|
  n = 2 * (s.split(" ")[0].to_i + s.split(" ")[1].to_i)
  r = 2 * s.split(" ")[1].to_i
  dp[n][r]
end.inject(:+)


# 'e'がスペース区切りならこんなこともできる
a,b = e.split(" ").map(&:to_i)

  Crystal言語

# 少し記法が異なる
a,b = e.split(" ").map(&.to_i)

# あと、Map/Reduceのような対応でメソッドが命名されているので注意(injectは使えない)
list.inject(&.+)  # error!
list.reduce(&.+)  # OK

  D言語

  • D言語もできますねぇ!
  // 文字列の配列をすべて一度splitしてlongに変えてまた配列に戻す
  immutable long[] a = array.map!(e => e.split(" ")[0].to!long).array;
  immutable long[] b = array.map!(e => e.split(" ")[1].to!long).array;

  // 配列の中での最大値
  int A = reduce!(max)(a);
  int B = reduce!(max)(b);

巨大数

  Ruby

ただ、性能的に追いつけないと思われる

  D言語

  • 実際こういうので苦戦する
import std.stdio;
import std.bigint;

BigInt factorial(int n) {
   return n>0 ? factorial(n-1) * n : BigInt(1);
}

void main()
{
   writeln(factorial(1000));
}

配列・ハッシュ

  Crystal

空の配列・ハッシュの宣言がやや面倒

[] of Int32 # Array(Int32).new と同じ
[]          # シンタックスエラーになる
{} of Int32 => Int32 # Hash(Int32, Int32).new と同じ
{}                   # シンタックスエラーになる
# rubyなら
for i in 0...5

end

# crystal(?)
(1...5).to_a.each |e|

end

お名前: コメント: