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

競技プログラミング指針

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

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

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

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

  Ruby

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

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

puts "#{answer}"

  Crystal

lines = <<-EOS
aa
bb
cc
EOS
array = lines.split("\n")
#array = STDIN.gets_to_end.split("\n")

array.each do |e|
    puts e
end

  D言語

#!/usr/bin/env rdmd

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

  • 大きな数を表したいときはビットシフトで
INF   = 1 << 25
MOD = 1_000_000_007

  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 と同じ
[]          # シンタックスエラーになる
  • 二次元配列
Array.new(n, Array.new(n, 0))     # crystal-lang
Array.new(n).map{Array.new(n, 0)} # ruby
{} of Int32 => Int32 # Hash(Int32, Int32).new と同じ
{}                   # シンタックスエラーになる
# rubyなら
for i in 0...5

end

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

end

  D言語

  • 動的配列
    • この書き方は忘れるわ…
int[] array = new int[](n);
int[][] dp = new int[][](h,w);

構造体

  Ruby

Node = Struct.new(:u, :k, :v, :w)

  Crystal

struct Node
  property :u, :k, :v, :w
  def initialize(@u,@k,@v,@w)
  end
end

C++マクロの置き換え

  Ruby

  • REP
#define REP(i,n) for(int i=0;i<n;i++)
for i in 0...n
end
お名前: コメント: