Subscribed unsubscribe Subscribe Subscribe

~/.taglibro

プロコンとか趣味プログラムとかです

Google Code Jam 2016 - Qualification Round

GCJ 2016 予選

解法

  • A: シミュレーション
  • B: 数える
  • C: 力技 (乱択)
  • D: 読んでない

A. Counting Sheep

0がINSOMNIAなのは自明. 1-2000で手元で実験. どれも最大 75step で終了するので、2000より大きな数字もみんなそんな感じで、短いステップで終了すると信じてシミュレーションする.

gets.to_i.times {|cx|
  n = gets.to_i
  if n == 0
    puts "Case ##{cx+1}: INSOMNIA"
  else
    memo = [false] * 10
    k=0
    i=1
    while k < 10 do
      (n*i).to_s.chars.each{|s|
        kc = s.ord - '0'.ord
        if memo[kc] == false
          memo[kc] = true
          k += 1
        end
      }
      if k == 10
        puts "Case ##{cx+1}: #{n*i}"
      end
      i += 1
    end
  end
}

B. Revenge of the Pancakes

連続した +- をひと塊に扱って良い. 例えば -+++--+- と同様に扱え、こちらだけを考える. ボトムが - で長さが n...-+-end_with_minus(n) ボトムが + で長さが n...+-+end_with_plus(n) と呼ぶ.

問題が求めるものを f とする.

でまあ、なんか適当に考察すると

  • f(end_with_plus(n)) = n-1
  • f(end_with_minus(n)) = n

である.

  • f(end_with_plus(n)) = f(end_with_minus(n-1))
    • ..-+ \rightarrow^* ..++
  • f(end_with_minus(n)) = f(end_with_plus(n-2)) + 2
    • ..-+- \rightarrow^* ..++- \rightarrow ..--- \rightarrow ..+++

みたいな感じ.

def nub(xs)
  ys = []
  if !xs.empty?
    for x in xs do
      ys << x if ys[-1] != x
    end
  end
  ys
end

gets.to_i.times {|cx|
  xs = nub gets.chomp.chars.map{|s| s == '+'}
  ans = xs.length
  ans -= 1 if xs[-1]
  puts "Case ##{cx+1}: #{ans}"
}

C. Coin Jam

smallは32桁、largeは64桁の二進数であって、最上位ビットと最下位ビットが1のものを、ランダムに生成して、素数かどうかをチェックした.

次は実際に用いた、1個の数を生成して、jam coin なら、求められる出力をするだけのものだけど、本当はよくない.

require 'prime'

N = 64

def powmod(a,k,m)
  return 1 if k == 0
  t = powmod(a,k/2,m)
  t = (t * t) % m
  t = (t * a) % m if k%2==1
  t
end

def test(n)
  return false if n<2
  return true if n<4
  return false if n%2==0
  d = n-1
  while d%2 == 0
    d /= 2
  end
  100.times {
    a = rand(n-1) + 1
    y = powmod(a, d, n)
    t = d
    while t != n-1 && y!=1 && y!=n-1
      y = (y * y) % n
      t *= 2
    end
    return false if y!=n-1 && (t%2==0)
  }
  true
end

def factor(x)
  i = 2
  while i * i <= x
    return i if x % i == 0
    i += 1
  end
  return 1
end

s = "1#{(1..(N-2)).map{|_|rand(2)==0?'0':'1'} * ''}1"
ok = true
evi = []
(2..10).each{|b|
  x = s.to_i(b)
  if test(x)
    ok = false
    exit 0
  end
  evi << factor(x)
}
if ok
  puts "#{s} #{evi * ' '}"
end

素数の判定はミラーラビン法を用いてるのに、因数を求めるのに、試し割りを行っているので、たまに、なかなか終わらないことがある. 上のコードをを main.rb として次を実行する.

: > out
for _ in `seq 500`; do
  timeout 2s ruby main.rb >> out
done

重複がないかをチェックして正しく欲しい個数が得られたのを確認したら、頭に Case #1: を付けて提出.

2-100 くらいで試し割りして、割り切れなかったら素数であると保守的に判定する. 合成数のときは因数も得られる.

smallで作った32bitを並べればいい. 因数もsmallでのそれを使える.

D. Fractiles

読んでない

No.355 数当てゲーム(2) - yukicoder

No.355 数当てゲーム(2) - yukicoder プロコン

Sat Apr 2 00:01:45 JST 2016

No.355 数当てゲーム(2) - yukicoder

いわゆるヒットアンドブローのAIを書くもの インタラクティブに結果を受け取るタイプの問題

この問題の註意すべき細かい点としては、

  1. 4桁は全て異なる
  2. 結果として返ってくる2つの数値は重ならない (たいていそうだけど)

難しくない解法

100回以内のトライで正答したい 私の解法は大きく2つのフェーズからなる

  1. 使われてる4文字をあてる
  2. 並び替える

並び替えが 24通りなので、4文字を当てるのを76回以内でやればok. ただ貪欲法でやればいい. 大雑把に言えば、各桁が10通りで、 4 \times 10 通り (4桁が全て異なる場合だけを使うこと) 試す. 詳細に言うと、返ってくる2つの値の和が「使われてる文字」の数なので、これについての貪欲法を行う.

4文字を当てられたら、もう24通り全部試すだけ

yukicoderのインタラクティブ系統は、ゲームが終わったらそれ以降にだらだら出力せずにさっさと終了しないとREだかTLEだかを食らう.

http://yukicoder.me/submissions/84671

def torai(a) # try
  puts a*' '
  STDOUT.flush
  gets.split.map(&:to_i)
end

a = [0,1,2,3]
n,m = torai(a)
exit 0 if n == 4
k = n+m

for i in 0..3 do
  for x in 0..9 do
    if not a.include?(x)
      b = a.clone
      b[i] = x
      n,m = torai(b)
      if n==4
        exit 0
      end
      if k < (n+m)
        k = n+m
        a = b
        break
      end
      if k > (n+m)
        break
      end
    end
  end
end

a.permutation(4) {|a,b,c,d|
  puts [a,b,c,d]*' '
  STDOUT.flush
  n,m=gets.split.map(&:to_i)
  if n==4
    exit 0
  end
}

D問題: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder

プロコン

Sun Mar 27 00:37:32 JST 2016

ABC 035 - D問題

問題

枝に時間コストのある有向グラフが与えられる. ノードは 1 から N まであって、N は 1e5程度. ノード 1 からちょうど時間  T を掛けて枝を巡ってノード1に戻ってくることをする. ただし任意のノードでは0秒以上自由に滞在してよい. また各ノード i には 1 以上の滞在ポイント A_i があって、ノード i に時間 t だけ滞在したとき、滞在ポイントが t \times A_i だけ溜まって加算される. これの合計を最大化したい.

解法

いつも滞在時間をゼロにするなら、ただのパスを巡るだけの問題である. 二箇所以上に滞在するのは無駄だと分かる. それは例えば異なる二箇所に注目して

 A_i t_i + A_j t_j \leq \max(A_i,A_j) \cdot (t_i + t_j)

ということ. もちろんゼロ箇所に滞在するというのはおかしい. スタート地点でずっと滞在すれば少なくとも 1 より大きな滞在ポイントが得られるから.

以上から滞在箇所はちょうど 1 つである. ノード u だとする.

1 \rightarrow uu \rightarrow 1 を巡る最短時間を計算して、残り時間を一杯、ノード u で滞在したときの滞在ポイントを P_u とする. もちろん巡るだけで時間が足りない場合もあるのでそこは適当に処理. で、 \max_u P_u が答え.

一頂点から全頂点まで (1 \rightarrow u) の最短時間は、ダイクストラ法による. 一番素朴なダイクストラ { O(V^{2}) } で、これだと、今は遅い. 優先度付きキュー (あるいは二分ヒープ) を使うことで、O((E+V) \log V) になる. 問題の制約をよく見ると、E のサイズも 1e5 程度と制限されてるので、こちらで行けるのだと想定が出来る.

帰り際の時間を計算するために、「全頂点から一頂点」(u \rightarrow 1) の最短時間が必要であるが、本当に全頂点からダイクストラをすると頂点の自乗以上の時間が必要なので遅い. しかしゴールは決まってるのだから、逆辺を辿るダイクストラだと思えば良いだけ.

参考になるであろうリンク

解答

本質的でない所

入力を受け取る部分を自前で書いてたんだけど、それがおっそくて、 バッファなんてキューにすべきだと前から分かってたはずなのに調べるのを忘れててただのベクターにしてた (pop O(n) かけてた) のが原因でずっとTLEしてた. Vec の確保が遅いのか?と悩んでたけど、これは普通にヒープに領域確保するので遅くない.

都営・メトロ分類器

都営・メトロ分類器

あらまし

東京に住み着いてもうすぐちょうど6年になるが、今だに地下鉄に乗ってて 「あれ? 私が今乗ってるのって、都営だっけ?メトロだっけ?」ってなる

一応言っておくと、東京に走ってるのはJRかさもなくば地下鉄で、地下鉄は都営地下鉄東京メトロの二社があり. 都営とメトロとの間の乗り換えは、社を跨ぐので、ほんの少し、乗車賃が上乗せされる.

簡単に、今乗っている「〇〇線」が都営であるかメトロであるかを分類するモデルを書きましょう

あらましその2

2つの語の類似度を測る、なかなか直観的な方法として、 語を並べて某大手検索エンジンに投げたときのヒット数を見るというのがある. 例えば、3つの語 A B C があったときに、「A B」と「A C」でそれぞれ検索してヒット数を比較することで、 B と C、どちらがより A に近いかを見ることが出来る.

この手段は自然言語処理界隈でしばしば見られる. 手頃な論文無いかなあと探そうとした矢先に こんな (Googleなどでのヒット数は言語研究の証拠となるか?|Colorless Green Ideas) 記事を見つけた. 要するに、ヒット数なんてかなり信用できないぞ、ということ.

(一時的に極端にヒット数が変動するなんて初めて知った)

ちなみに言うと、自然言語処理界隈で使われるのはコレ (Normalized Google distance - Wikipedia, the free encyclopedia) みたいなやつです.

でまあ問題点は在るんだけど、 「都営 〇〇線」 「メトロ 〇〇線」 でそれぞれ検索してヒット数の大小を見てみようという発想.

ソースコード

検索エンジンとして

  1. Google
  2. Bing
  3. ニコニコ動画

日本の鉄道だし、ニコニコで調べてもね、きっと上手くいくかもしれないよね? 本当は単にさっき偶然、ニコニコにもAPIが公開されているという事実を知ったから使ってみただけ.

Google

Google と Bing に関しては、礼儀がなっていないが真面目にAPI叩かない. つまり実際にブラウザで検索することを自動化するだけに留める. Ruby で言うところの mechanize. CUI で言うところの w3m -dump (?).

ちなみにこれをやりまくると、GoogleはすぐにBANするので註意 (are you machine? みたいな表示と共にCAPTCHAが表示される).

#!/bin/bash

L=$1
for C in 都営 メトロ; do
  N=$( w3m -dump "http://google.co.jp/search?q=$C $L" | grep '約.*[0-9].*件' | head -1 | tr -cd '[:digit:]' )
  echo $N $C
done

grep ... | head -1 のところはすごく、その人の環境に依存するところ.

三田線について調べてみる:

   ./google.sh 三田線
11500000 都営
7920000 メトロ

三田線は都営である.

Bing

#!/bin/bash

L=$1
for C in 都営 メトロ; do
  N=$( w3m -dump "http://www.bing.com/search?q=$C $L" | grep '[0-9].*results' | head -1 | tr -cd '[:digit:]' )
  echo $N $C
done

Bing に関してはこんなことしても全然BANされない (経験上).

   ./bing.sh 三田線
2020000 都営
2300000 メトロ

三田線はメトロです.

ニコニコ動画

これは API があるので丁寧に叩く. 返ってくるのが json なので jq でヒット数だけ抜き出す.

#!/bin/bash

L=$1
for C in 都営 メトロ; do
  URL=http://api.search.nicovideo.jp/api/snapshot/
  DATA=$( echo '{"query":"' $C ' ' $L '","service":["video"],"search":["title","description","tags"],"join":["cmsid"],"sort_by":"view_counter","issuer":"/c/"}')
  N=$( curl -s -X POST -d "$DATA" $URL | jq '.values[]?.total' | grep -o '[0-9]*' | head -1 )
  echo $N $C
done
   ./nico.sh 三田線
187 都営
32 メトロ

三田線は都営.

三田線は都営であるのが正しい

実験

てゆうか、東京の地下鉄の線なんて有限本しかないので全部試せば良い.

   cat toe-list
三田線
大江戸線
浅草線
新宿線

  cat metro-list
南北線
東西線
銀座線
副都心線
丸の内線
日比谷線
千代田線
有楽町線

Google

   for L in `cat toe-list`;do echo $L; ./google.sh $L; done
三田線
11500000 都営
7920000 メトロ
大江戸線
15800000 都営
11900000 メトロ
浅草線
11400000 都営
8200000 メトロ
新宿線
15500000 都営
13100000 メトロ

都営のほうが数字が大きいのが正しい. というわけで都営は全部OK.

   for L in `cat metro-list`;do echo $L; ./google.sh $L; done
南北線
7770000 都営
9140000 メトロ
東西線
10400000 都営
13800000 メトロ
銀座線
8410000 都営
12300000 メトロ
副都心線
348000 都営
8320000 メトロ
丸の内線
552000 都営
489000 メトロ
日比谷線
4300000 都営
13100000 メトロ
千代田線
7930000 都営
10400000 メトロ
有楽町線
1680000 都営
13300000 メトロ

今度はメトロだけ大きいのが正しい. よく見ると丸ノ内線だけ誤っている.

(実験が終わるまでにBANされなくてよかった)

Bing

   for L in `cat toe-list`;do echo $L; ./bing.sh $L; done
三田線
2020000 都営
2300000 メトロ
大江戸線
2380000 都営
2400000 メトロ
浅草線
2430000 都営
2810000 メトロ
新宿線
3170000 都営
5750000 メトロ

   for L in `cat metro-list`;do echo $L; ./bing.sh $L; done
南北線
1520000 都営
2300000 メトロ
東西線
1660000 都営
2790000 メトロ
銀座線
2500000 都営
4160000 メトロ
副都心線
985000 都営
1710000 メトロ
丸の内線
2140000 都営
2990000 メトロ
日比谷線
2030000 都営
2570000 メトロ
千代田線
2300000 都営
3000000 メトロ
有楽町線
2060000 都営
2780000 メトロ

ぜーんぶメトロ!

ニコニコ動画

   for L in `cat toe-list`;do echo $L; ./nico.sh $L; done
三田線
187 都営
32 メトロ
大江戸線
179 都営
43 メトロ
浅草線
341 都営
25 メトロ
新宿線
235 都営
43 メトロ

   for L in `cat metro-list`;do echo $L; ./nico.sh $L; done
南北線
32 都営
110 メトロ
東西線
36 都営
480 メトロ
銀座線
26 都営
232 メトロ
副都心線
18 都営
445 メトロ
丸の内線
20 都営
169 メトロ
日比谷線
28 都営
139 メトロ
千代田線
21 都営
327 メトロ
有楽町線
13 都営
205 メトロ

まとめ

Google はさすが (1件だけ誤り).

Bing は全然ダメ. そもそも性質が違うのかなって感じ. 「都営」、「メトロ」単体で検索したときのヒット数で正規化するとかしたら良い. 一応、都営の数字をほんのちょっと増やす (1.1倍にするとか) と多少、正解率が上がるが、それでも所詮って感じ.

ニコニコは全部正解した. 検索対象の性質としてノイズと成るものが少ないんだろう. 他が一つのwebページなのに対して、謂わばそれの要約になっている (タイトル+説明文+タグ) からだ、とか主張できそう.

マヂレスすると都営の路線は4本しかないんだから覚えろって話

その他

二値分類なので、都営でもメトロでもない線について調べてもしょうがない. ところで、でも、違う呼び名というものがある. 例えば「東京メトロ副都心線」は「地下鉄13号線」である. 「都営浅草線」は「地下鉄1号線」である. 都営かメトロに関係なく勝手にナンバリングされてる. 「都営地下鉄大江戸線」という路線名が決まるまでに「東京環状線」という名称が候補にあった.

   cat phantom-list
地下鉄1号線
地下鉄13号線
東京環状線

順に、都営、メトロ、都営 が正しい.

   for L in `cat phantom-list`;do echo $L; ./google.sh $L; done
地下鉄1号線
131000 都営
372000 メトロ
地下鉄13号線
273000 都営
409000 メトロ
東京環状線
469000 都営
508000 メトロ

   for L in `cat phantom-list`;do echo $L; ./bing.sh $L; done
地下鉄1号線
2450000 都営
5990000 メトロ
地下鉄13号線
2790000 都営
16700000 メトロ
東京環状線
265000 都営
1080000 メトロ

   for L in `cat phantom-list`;do echo $L; ./nico.sh $L; done
地下鉄1号線
0 都営
1 メトロ
地下鉄13号線
0 都営
0 メトロ
東京環状線
1 都営
0 メトロ

全滅.

チワワ文字列 - yukicoder

プロコン

チワワ文字列 - yukicoder

No.345 最小チワワ問題 - yukicoder

文字列の長さが 100 以下であるので、両端を全通り試した部分文字列全てについて、 チワワ列であるか判定して、最短のものを見つければ良い

s=gets.chomp.chars
a=1e9
(0...s.size).each{|i|
  (i...s.size).each{|j|
    k=['w','w','c']
    s[i..j].each{|c| k.pop if k[-1]==c }
    a=[a,s[i..j].size].min if k.empty?
  }
}
p a>1e8?-1:a

チワワ列の判定が若干、技巧的で、正規表現使えば一発じゃん、と気付いて

s=gets.chomp
a=(0..n=s.size).map{|i|
  (0..n).map{|j|
    s[i...i+j].match(/c.*w.*w/)?j:1e5
  }.min
}.min
p a>1e4?-1:a

angel_p_57 さんの解答を見るともっと鮮やかで (#79137 No.345 最小チワワ問題 - yukicoder) gets.scan(/(?=(c.*?w.*?w))/) で、マッチする部分文字列全てを列挙してしまってる (知らない文法だ).

No.346 チワワ数え上げ問題 - yukicoder

文字 c を見つけたら、それより右方を見て、w を2つ選べば良い. 1つ以下しかなかったら、チワワ列は作れないし、2つ以上あったら、そこから2つ選べるので、  \binom{n}{2} 通りのチワワ列が作れる. 毎回 w の数を数えていると、今回は文字列の長さが { 10^{5} } 程度あって間に合わないので、 初めに全ての w の数を数え上げて、 文字列を舐めながら w の数を更新していけばよい.

すなわち、w の数の総計を W とするとき、 左から文字列をナメていって、 w が出現したら、W をデクリメントし、 c が出現したら、そのときの W を用いて、 \binom{W}{2} を計算して加算すればよい.

s=gets.chomp.chars
w=s.count{|c|c=='w'}
a=0
s.map{|c|
  w-=1 if c=='w'
  a+=w*(w-1)/2 if c=='c'
}
p a

京都大学 2016 文系 数学問題[2]

数学

Thu Feb 25 22:49:59 JST 2016

京都大学 2016 文系 数学問題[2]

https://twitter.com/yuya_lz/status/702767994053615616/photo/1

問題: 素数  p, q によって表される数  p^{q} + q^{p} 素数であるような  (p,q) の組み合わせを求めよ.

実際に実験をすると予想が立ってしまう:

require 'prime'

N=100
Prime.each(N) {|q1|
  Prime.each(N) {|q2|
    r = q1**q2 + q2**q1
    if r.prime?
      p [q1,q2]
    end
  }
}

 p,q が共に奇数、即ち 3 以上の素数である場合、 p^{q}+q^{p} が偶数だし、2 よりは大きそうだからダメだとすぐに分かる. 従ってどちらか一方は 2 で、 p=2 とする.  p^{q} + q^{p} = 2^{q} + q^{2} .

でまあ、これも、実験して分かったことなんだけど、  q が 3 の倍数ではない素数のとき、  2^{q} + q^{2} は 3 の倍数である.

 2^{q} の3の剰余というのは、  q=1,2,3,4,5, \ldots について、  2^{q} \bmod 3 = 2,1,2,1,\ldots であること、  q を奇数に限ると  2^{q} \bmod 3=2,2,2,\ldots であることはすぐ分かる.

q=3n+1

 q 3n+1 で表せる素数のとき、  q^{q} \bmod 3 = 2 である.

 { \displaystyle
(2^{q} + q^{2}) \bmod 3 = (2 + (3n+1)^{2}) \bmod 3 = 0.
}

であるので、q がそういう素数ならば、アレは 3 の倍数であるので、素数ではない (もちろん3でないことも言わないといけないけど).

q=3n+2

q=3n+2 の形の素数のとき、2^{q} \bmod 3 = 2 であって云々で、やっぱりアレは 3 の倍数である (3 でないことは自明).

q=3n

q3n で表される素数であるならば、q=3 である. 実際に計算することで、2^{q}+q^{2}素数であることが言える.

N言っちゃダメゲーム - yukicoder

プロコン

Mon Feb 22 23:01:59 JST 2016

No.8 N言っちゃダメゲーム - yukicoder

http://yukicoder.me/submissions/77454

石取りゲーム風に言い換えると、 "N 個の石があって 1 個から K 個の範囲で石を取る. 最後の 1 つを取ったら負け". いわゆる Nim の逆形.

後攻必勝の時に限り 0 になるようにグランディ数を決める. 局面の状態を山に残ってる石の数とする.

K=3 のとき:

 P | 1 2 3 4 5 6 7 ... 
 g | 0 1 2 3 0 1 2 ... 

(Markdownの表記表、ブレすぎてて嫌い)

 g(P)=(P-1) \bmod (K+1) って予想が付いた.  g(P) \ne 0 \iff 先手必勝

No.249 N言っちゃダメゲーム (2) - yukicoder

http://yukicoder.me/submissions/77473

かなり悩んだ. 何かのDPをするのかと思った. 負けた人は次のゲームで自由に先攻後攻を選べる、の意味は、勝ち負けを自由に選べるというだけの意味だった. 選ぶ側としてはわざわざ負ける理由が無いので結局、互いに勝ちを取り合って、公平にゲーム数を分け合うだけ.