れんしゅうちょう。

■ [AtCoder]AtCoder Regular Contest #001 11:40

残念な事に中止になってしまった.

一応解いたので書いておく.

A

受け取った文字列を読んで, '1','2','3','4'の数をそれぞれ数えて, その最大と最少を出力すればよい.

問題文が日本語なのが良い, 本当に.

n = gets.to_i
s = gets
puts (1..4).map{|i|s.count(i.to_s)}.minmax.reverse * " "

B

なんか適当にやる.

結局, aとbの差を±(1,5,10)を使って作れればよい.

xと-xは同じ回数で作れるのでabsとっても問題無い.

xがk回で作れるなら, x±1, x±5, x±10がk+1回で作れる.

普通のコインDP問題と違って, マイナスが使える事に注意.

適当ってレベルじゃないけど, 幅優先というか, DPの更新タイミングを弄った感じというイメージで書いた.

def geti;gets.to_i;end
def getia;gets.chomp.split(" ").map(&:to_i);end
a, b = *getia
x = (a-b).abs
pq = []
pq.push [0, x]
a = [-10, -5, -1, 1, 5, 10]
ls = {}
until pq.empty?
  time, t = *pq.shift
  if t.zero?
    puts time
    exit
  end
  a.each do |dt|
    pq.push [time+1, t+dt] unless ls[t+dt]
    ls[t+dt] = true
  end
end

C

THE☆TEKITOU

まぁ普通に深さ優先枝狩りとかすればいいんだろうけれど, まぁ8固定なので8!くらいかかっても無問題.

同じ行, 同じ列にQが入らないので, i行目のj_i列目にQが入るみたいのを(j_0, j_1, j_2, ..)みたいにして持つと, これは(0,..,7)の順列になる.

これから, 斜めが一致してないかチェックして, さらに問題の入力と合致してるかチェックすればよい.

昔数回書いた事があるので引っ張り出して来た.

rubyは魔術っぽい.

begin-end while falseとか, なにげに例外処理するのに楽.

みんなまねしていいですよ←

class Array
  def getbord
    self.map{|x|Array.new(self.size).fill(".").fill(x,1){"Q"}.join} * "\n"
  end
  def is_ok?
    self.each.with_index.to_a.combination(2).to_a.none?{|p,q|(p[0]-q[0]).abs==(p[1]-q[1]).abs}
  end
end

begin
  x = []
  break unless 8.times do
    s = gets.chomp
    break false if s.count("Q") > 1
    x << s.index("Q")
  end

  (0...8).to_a.permutation.to_a.select{|a|a.is_ok?}.each do|a|
    if a.zip(x).all?{|i,j| i == j || j.nil?}
      puts a.getbord
      exit
    end
  end
end while false
puts "No Answer"

D

直線で行けなくなったら, 行けなくなる原因の所にジャンプしてやり直す的な.

First ACだったっぽい. 嬉しい.

通ってしまったが想定誤解法だったらしい.

曲率半径でかい半円みたいなヤツで, 遠くからジャンプしてやり直すのを繰り返したら, 確かにヤバくなる.

rubyで書いたらTLEしたのでDに直したらTLEしたのでC++に直した.

良く見るとC++ですらなくCである...

まぁ, 通ったので正義という事でどうかひとつ.

#include <cstdio>
#include <cmath>

int inp[200010][2];
const double INF = 1E20;

#define dist(a,b) hypot(a[0]-b[0], a[1]-b[1])

int main(){
    int n, s, g;
    int now[2];
    double view[2] = {-INF, INF};
    scanf("%d", &n);
    scanf("%d %d", &s, &g);
    int memo[2][2] = {{0, s}, {0, s}};
    now[0] = 0;
    now[1] = s;
    double res = 0;
    for(int i=0; i<=n; ++i){
        scanf("%d %d", inp[i], inp[i]+1);
    }
    int i=1;
    inp[n][0] = inp[n][1] = g;
    while(i <= n){
        int l = inp[i][0], r = inp[i][1];
        if(view[0] < ((double)(l) - now[1]) / (i - now[0])){
            view[0] = ((double)(l) - now[1]) / (i - now[0]);
            memo[0][0] = i;
            memo[0][1] = l;
        }
        if(view[1] > ((double)(r) - now[1]) / (i - now[0])){
            view[1] = ((double)(r) - now[1]) / (i - now[0]);
            memo[1][0] = i;
            memo[1][1] = r;
        }
        if(view[0] > view[1]){
            if(memo[0][0] == i){
                res += dist(now, memo[1]);
                for(int j=0; j<2; ++j) now[j] = memo[1][j];
            }else{
                res += dist(now, memo[0]);
                for(int j=0; j<2; ++j) now[j] = memo[0][j];
            }
            view[0] = -INF;
            view[1] = INF;
            i = now[0];
        }
        i += 1;
    }
    printf("%.13f\n", res + hypot(now[0]-n, now[1]-g));
}

ツイートする