れんしゅうちょう。

■ [AtCoder]ARC007 02:01

http://arc007.contest.atcoder.jp/

52位	53:26	300pts(2)
問題	時間	得点(WA)
A	01:26	100
B	08:30	100(1)
C	23:26	100(1)
D	-	-(3)

以下ソースとか.テンプレ略.

A問題

ある文字cと文字列sが与えられて, sのうちc以外のやつを出力しろ的な.

x = gets.chomp
s = gets.chomp
s.to_a.each do |c|
  print c if c != x
end
puts

流石に全ケースチェックしたりする必要無いハズなのに, 提出まで時間書け過ぎな気がする.

B問題

なんか適当にスワップしてけ的な感じの.

n, m = getia
a = (0..n).to_a
a[0] = -1
x = 0
m.times do
  t = geti
  i = a.index(t)
  if i
    a[i] = x
    x = t
  end
end
puts a[1..-1] * "\n"

こっちは逆に全ケースちゃんとチェックすべきだった. 問題全部読むべきだった.

同じCD聞く事があるというのを見逃してて1WA.

C問題

bit列が与えられるので, それのrotateで全部1なやつを作れ. 但し使うの最小にしろ的な.

どうやってbit列持つかで迷走しすぎた. rotate以外は素直にintで持つのが楽なハズだとは思ったけれど, rotateで血迷った.

rotateも普通にbit演算でどうとでもなるのに('A`)

vvi A;
void all_pattern(vi &x){
    vi a;
    rep(i, x.size()){
        a.clear();
        rep(j, x.size()) a.pb(x[(i+j)%x.size()]);
        A.pb(a);
    }
}
int bitCount(long x){
    x = (x & 0x55555555) + (x >> 1 & 0x55555555);
    x = (x & 0x33333333) + (x >> 2 & 0x33333333);
    x = (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f);
    x = (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff);
    return (x & 0x0000ffff) + (x >>16 & 0x0000ffff);
}

void solve(){
    int sz = 0;
    int res = 999999;
    vi v;
    string s;
    cin >> s;
    for(int i=0; i<s.length(); ++i){
        v.pb(s[i] == 'o');
    }
    sz = v.size();
    all_pattern(v);
    for(int i=0; i<(1<<sz); ++i){
        vi x(sz, false);
        for(int j=0; j<sz; ++j){
            if((i>>j)&1){
                rep(k, sz) x[k] |= A[j][k];
            }
        }
        bool f = true;
        rep(j, sz){
            if(!x[j]) f = false;
        }
        if(f){
            res = min(bitCount(i), res);
            //return bitCount(i);
        }
    }
    cout << res << endl;
}

int main(){
    solve();
    return 0;
}

コメントんとこで1WA. アホ過ぎるミス. 人権無い.

D問題

等差数列を書いた, 区切り文字書いてない, 初項と末項の一部が無い, ありうる(初項, 項差)のうち辞書順最小を出力せよ的な.

初項が最小のやつという制約の強さを解っていなかった. 終了間際に気付いて, 50点解書いて終了9秒前に投げたけど, 途中のputsを消し忘れてWAった. それを自明な高速化したのが100点解.

a000...0みたいな入力の場合, どこで切っても2項目が0から始まるので, a00...0を初項にして, 項差1が最小.

a0...0b...zの場合, 初項が最小なのはa0...0である.(項差として(b...z0...0)-(a0...0)を取れる)

最初が0だった場合, なんか左に何かAを追加しなきゃいけなくて, 上の考察から, どうせAの後に連続する0をくっつけたのが初項になるから, A=1を与えられた文字列の最初にくっつけておけばいいという事が解る.

これで初項が解ったので, 最小の項差を求めれば良くて, これは2項目としてどこまでとるか→その2項目から求めた項差で, 文字列が条件を満たすかをチェックする.

どんなに取ってもダメな感じなら, 末尾に0を追加していく. 注意すべきは, 10010みたいな入力で100,1000ではなく100,101と解釈できるようにちょろっとコーナーケース対策書いておくという事.

def check(a, d, s)
  as = a.to_s
  ss = ""
  aa = a
  while ss.size < s.size + as.size + 10
    ss += aa.to_s
    aa += d
  end
  # a[0...i], a[i..-1]
  for i in 0...as.size
    return true if ss[i..-1].index(s) == 0
  end
  return false
end
s = gets.chomp
s = "1" + s if s[0] == '0'
n = s.size
a = 0

i = 1
i += 1 while s[i] == '0' && i < n
if i == n
  #a0...0
  a = s.to_i
  puts a.to_s + " 1"
  exit
else
  #a0...0x...x => 10...0, x...x
  a = s[0...i].to_i
end

for j in (i*2)..s.size
  b = s[i...j].to_i
  d = b - a
  if d > 0 && check(a, d, s)
    puts a.to_s + " " + d.to_s
    exit
  end
end
b = s[i..-1].to_i
f = false
until b >= a
  b *= 10
  f = true
end
if b == a
  if f
    b += 1
  else
    b *= 10
  end
end
puts a.to_s + " " + (b-a).to_s

ツイートする