「 競技プログラミング 」一覧

Google Code Jam 2019 Qualification Round

Foregone Solution

問題

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

解法

与えられた整数Nを2つの整数(A+B)に分割する。この時、AとBのどの桁にも4が含まれ無いように分割するという問題。

Nの各桁を順次見ていき、4の場合は2と2、それ以外は0と元の数、のようにAとBに割り振る。

なお、答えを出力する際に、先頭の0は削除する必要がある点に注意する。

実装

N=gets.to_i
N.times do |i|
  n=gets.chomp.split("")
  a=[]
  b=[]
  n.each do |v|
    if v == '4'
      a << '2'
      b << '2'
    else
      a << '0'
      b << v
    end
  end
  printf("Case #%d: %s %s\n", i+1, a.join.gsub(/^0*/, ""), b.join)
end

You Can Go Your Own Way

問題

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

解法

NxNのマス目を北西から南東に移動する。移動は南(S)、東(E)の組み合わせのみで後戻りは無し。

テストケースで与えられた移動方法に対して、経路が重ならないような移動方法を1通り出力するという問題。

これは、与えられた移動方法(SとEの並び)に対して対象な移動方法(SならE、EならS)を作れば良いです。

例えば、SEEESSESならESSSEESE。

このようにすると、移動経路はマス目の北西から南東への対角線に対して対象な移動経路になるので、絶対に重なりません。

実装

T=gets.to_i
T.times do |i|
  n=gets
  s = []
  gets.chomp.split("").each do |v|
    s << (v == 'E' ? 'S' : 'E')
  end
  printf("Case #%d: %s\n", i+1, s.join)
end

Cryptopangrams

問題

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

解法

テストケースとして与えられる整数列は、元の文字列が対応する素数の積になっています。

例えばテストケースの整数列をEi、元の文字列の対応する素数をPiとすると、E0はP0xP1、E1はP1xP2です。

よって、E0とE1の最大公約数をとればP1が求まり、それでE0とE1を割ることでP0とP2も求めることが出来ます。

ここで注意点ですが、E0とE1が等しい場合、つまり、P0〜P2が同じ素数(=文字)の場合はこの方法では求めることが出来ません。(これに気づかずに最初WAをくらいました。。。)

よって、整数列を前から見ていき、隣り合う整数が最初に異なる場所に上記の方法を適用し、そこから前方、後方を見ていくことで全ての素数を求めることが出来ます。

素数が全て求まったらソートして小さい方からアルファベットを割り当てていき、元の文字列に戻すことが出来ます。

実装

def gcd(a,b)
  return a if b == 0
  gcd(b,a%b)
end

T=gets.to_i
T.times do |i|
  n,l=gets.chomp.split.map(&:to_i)

  enc = gets.chomp.split.map(&:to_i)
  pn=Hash.new(0)
  dec = Array.new(l+1)
  pos = 0
  0.upto(l-2) do |j|
    if enc[j] != enc[j+1]
      dec[j+1] = gcd(enc[j],enc[j+1])
      pn[dec[j+1]] += 1
      pos=j+1
      break
    end
  end

  (pos-1).downto(0) do |j|
    dec[j] = enc[j] / dec[j+1]
    pn[dec[j]] += 1
  end

  (pos+1).upto(l) do |j|
    dec[j] = enc[j-1] / dec[j-1]
    pn[dec[j]] += 1
  end

  m = {}
  pn.keys.sort.each_with_index do |v, i|
    m[v] = ('A'.ord+i).chr
  end
  ans=[]
  dec.each do |v|
    ans << m[v]
  end

  printf("Case #%d: %s\n",i+1,ans.join)
end

Dat Bae

問題

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

解法

N台のコンピュータのうちB台が壊れている。N個のビット列を与えたとき、壊れたコンピュータのビットは返ってこない。F回までビット列を投げることが出来る場合に、何台目のコンピュータが壊れているかを特定する方法を考えるという問題。

TestSet1のF=10の場合は結構簡単。というのも、Nの最大値が1024(=2^10)なので、0〜1023までの数字を各コンピュータに割り当てて、1回目の問い合わせは1ビット目、2回目の問い合わせは2ビット目、・・・というように10ビット目まで投げてやる。その結果、返ってきた回答を繋げて10進数に戻してやった場合に、欠けている数字が壊れているコンピュータの位置になります。

TestSet2のF=5の場合は少し工夫が必要です。2^5=32なので、5回の問い合わせで作れるビット列は0〜31になります。例えば、N=1024の場合、0台目から順にサイクリックに0〜31を割り当てます。すると、0〜31、0〜31、・・・、0〜31が32回繰り返されることになります。問題の制約として、壊れているコンピュータは最大15台までなので、抜けている数字の位置によってどのコンピュータが壊れているか一意に特定することが出来ます。

より厳密にはBが最大31までであれば大丈夫だと思います。32以上になると、例えば連続する0〜31が抜けていた場合に何番目の0〜31が抜けているのかが特定できない、ということになります。

実装

T=gets.to_i

def solve
  n,b,f=gets.chomp.split.map(&:to_i)

  r = Array.new(n-b).map { Array.new }
  f.times do |i|
    q = []

    j = 0
    n.times do
      t = j >> i
      q << (t & 1)
      j += 1
      j = 0 if j == 16
    end
    puts q.join
    STDOUT.flush

    gets.chomp.split("").each_with_index do |v, i|
      r[i] << v
    end
  end

  i = 0
  j = 0
  ans = []
  r.each do |v|
    if i == v.reverse.join.to_i(2)
    else
      while(i != v.reverse.join.to_i(2))
        ans << j
        j += 1
        i += 1
        i = 0 if i == 16
      end
    end
    i += 1
    i = 0 if i == 16
    j += 1
  end

  while(j != n)
    ans << j
    j += 1
  end
  puts ans.join(" ")
  STDOUT.flush
  gets.to_i
end

T.times do
  solve
end

AtCoder: ABC122

A – Double Helix

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

入力に対応する塩基を出力するだけ。

実装

とりあえずcaseで実装。

case gets.chomp
when 'A'
  puts 'T'
when 'T'
  puts 'A'
when 'G'
  puts 'C'
when 'C'
  puts 'G'
end

B – ATCoder

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

文字を一文字ずつ読み込み、ATGCのいずれかであれば部分文字列の長さを1増やし、それ以外であれば部分文字列の長さを0にもどす。各部分文字列の最大値を記憶・更新しておいて、最後に出力すれば良い。

実装

S=gets.chomp.split("")
ans = 0
tmp = 0
S.each do |c|
  if "ATGC".include?(c)
    tmp += 1
  else
    ans = [tmp,ans].max
    tmp = 0
  end
end
ans = [tmp,ans].max

C – GeT AC

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

累積和の変形問題という感じ。

最初に1文字目からn文字目までの’AC’の出現回数の数列を用意しておく(Cnとする)
そして、各l、rについては、C[r]-C[l]を計算すれば定数時間で計算可能。

実装

N,Q=gets.chomp.split.map(&:to_i)
S=gets.chomp
csum = [0,0]
0.upto(N-2) do |i|
  if S[i,2] == 'AC'
    csum[i+2] = csum[i+1] + 1
  else
    csum[i+2] = csum[i+1]
  end
end

Q.times do
  l,r=gets.chomp.split.map(&:to_i)
  puts csum[r]-csum[l]
end

D – We Like AGC

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

DPで解ける。

DP[直前の3文字][n]: 文字列の長さがnでの直前の3文字毎の文字列の数

とすると、nが3の場合が初期値となり、以下の通りとなる。

DP[‘AGC’][3] = 0
DP[‘GAC’][3] = 0 (1文字目と2文字目を入れ替えるとAGCになるので)
DP[‘ACG’][3] = 0 (2文字目と3文字目を入れ替えるとAGCになるので)
DP[上記以外][3] = 1

4文字目以降については、直前の4文字に着目して条件に一致する場合だけ数え上げて行けば良い。

実装

N=gets.to_i
ACGT=['A','C','G','T']
MOD=10**9+7
dp = {}
ACGT.each do |c1|
  ACGT.each do |c2|
    ACGT.each do |c3|
      c = c1+c2+c3
      dp = [0]*102
      if c == 'AGC' || c == 'ACG' || c == 'GAC'
      else
        dp[3] = 1
      end
    end
  end
end
4.upto(N) do |i|
  ACGT.each do |c1|
    ACGT.each do |c2|
      ACGT.each do |c3|
        ACGT.each do |c4|
          c = c1+c2+c3+c4
          if c.match(/AGC/) || c.match(/GAC/) || c.match(/ACG/) || c.match(/A.GC/) || c.match(/AG.C/)
          else
            dp[c2+c3+c4][i] += dp[c1+c2+c3][i-1]
            dp[c2+c3+c4][i] %= MOD
          end
        end
      end
    end
  end
end
ans = 0
dp.each_key do |k|
  ans += dp[k][N]
end
puts ans%MOD

AtCoder: ACB125

A – Biscuit Generator

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

A秒ごとにB枚のビスケットが生産されるの、T+0.5秒後なら(T/A)xB枚

実装

a,b,t=gets.chomp.split.map(&:to_i)
puts (t/a)*b

B – Resale

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

手に入れた宝石の価値の合計から支払ったコストの合計を引いた値が最大になるような宝石の選び方を考えれば良い。

宝石はいくつ選んでも良いので、各宝石の「価値−コスト」が正になるものは全て選んで良いことになる。

よって、「価値−コスト」が正になるものを加算していけばよい。

実装

N=gets.to_i
v=gets.chomp.split.map(&:to_i)
c=gets.chomp.split.map(&:to_i)
ans=0
N.times do |i|
  ans += v[i]-c[i] if v[i]-c[i] > 0
end
puts ans

C – GCD on Blackboard

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

N個の整数のうち1つだけ好きな整数に書き換えた後の最大公約数をなるべく大きくするためには、1つの整数を他の整数のうち一つと同じにすればよい。これは、その整数を取り除くのと同じ意味になる。

つまり、N個のうち1つを取り除いた残りのN-1個の最大公約数の最大値を求めれば良い。

2つの数の最大公約数はlogAで求まるので、N-1個の最大公約数はO(NlogA)となり、これをN通り試すと間に合わない。

そこで以下のような工夫をする。

Aiを取り除いた場合の最大公約数は、A1〜Ai-1の最大公約数とAi+1〜ANの最大公約数になる。

よって、あらかじめA1〜A2、A1〜A3・・・のように左から順番に整数を追加した最大公約数とAN-1〜AN、AN-2〜AN・・・のように右から順番に整数を追加した最大公約数を求めておくことで、i番目を取り除いた場合の最大公約数をlogAで求めることが出来る。

こうすれば、全体の計算量はO(NlogA)で収まるので間に合う。

実装

def gcd(a,b)
  return a if b == 0
  gcd(b,a%b)
end

N=gets.to_i
a=gets.chomp.split.map(&:to_i)
l=[0]
r=[0]
a.each_with_index do |v|
  l << gcd(v,l[-1])
end

a.reverse.each_with_index do |v|
  r << gcd(v,r[-1])
end

ans=0
0.upto(N) do |i|
  tmp = gcd(l[i],r[N-1-i])
  ans = tmp if ans < tmp
end
puts ans

D – Handstand

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

整数列のうち、隣り合う任意の2枚の正負を反転させることが何回でも出来る。
操作後の整数列の総和の最大はいくつになるか、という問題。

これは、以下のルールに気づけばすぐに解ける。

AiとAj(i<j)の正負を反転させたい場合、「iとi+1」、「i+1とi+2」、「i+2とi+3」・・・・「j-1とj」のように隣り合う2つを順次反転させていけば良い。
→ 任意の2個の正負を反転させることが可能
→ 偶数個であれば好きなように正負を反転させることが可能(奇数は不可)

よって、整数列の初期状態において、負が偶数個であれば全て正にすることが出来る。つまり絶対値の総和をとれば良い。

負が奇数個の場合、(初期状態が正のものも含めて)絶対値が最も小さいものを最終的に負としてそれ以外を正にすれば良い。

実装

N=gets.to_i
A=gets.chomp.split.map(&:to_i)
m_cnt=0
sum=0
min=Float::INFINITY
A.each do |a|
  if a < 0
    m_cnt += 1
  end
  if min > a.abs
    min = a.abs
  end
  sum+=a.abs
end
if m_cnt.even?
  puts sum
else
  puts sum - 2 * min
end

AtCoder: ABC124

A – Buttons

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

2個のボタンのサイズが等しい時は、A+Bが解。
等しくないときは、大きい方 x 2 – 1 が解。

実装

入力を読み取る際にソートして、B >= A にしておく。

A,B=gets.chomp.split.map(&:to_i).sort
puts A==B ? 2*B : 2*B-1

B – Great Ocean View

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

海が見えるのは、「自分より西側の山の高さが全て自分以下の時」なので、その時点の最大の高さを保持しながら西の山から順に見ていき、

・これまでの最大の高さ以上の時:解を1増やす&最大の高さを更新する
・これまでの最大の高さ未満の時:何もしない

というループをまわせば良い。

実装

N=gets.to_i
H=gets.chomp.split.map(&:to_i)
min=0
ans=0
H.each do |h|
  if h >= min
    ans += 1
    min = h
  end
end
puts ans

C – Coloring Colorfully

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

黒白2色しなかいので、隣り合うタイルが異なる色となるタイルの並べ方は以下の2通りしかない。

黒白黒白黒白黒白・・・・
白黒白黒白黒白黒・・・・

よって、両方のケースについて何枚塗り替える必要があるかをそれぞれカウントし、小さい方が解となる。

実装

S=gets.chomp.split("")
ans1,ans2=0,0
S.each_with_index do |s,i|
  if i.even? && s=='0' || i.odd? && s=='1'
    ans1+=1
  end
  if i.odd? && s=='0' || i.even? && s=='1'
    ans2+=1
  end
end
puts [ans1,ans2].min

D – Handstand

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

ある一定の区間の0、1を反転させることを繰り返し、連続する1をどれだけ長く出来るか、という問題です。

基本的に1を反転させる意味は無いので、出来るだけ長い1の連続を作るには、1回の操作で連続する0の区間を反転させていけば良いことが分かります。

ここで、連続する0の区間がK個以下であれば、全てを1に出来るので解はNになります。

問題となるのは、連続する0の区間の数がKより多い場合です。

仮に連続する0の区間がL個だとすると、K個からL個選ぶことになるので、全探索だと間に合いそうに無いです。

そこで、次のように考えます。

なるべく1の連続を長くするには、反転させる連続する0の区間は連続していた方が良いです。

例えば、以下のような並びについてK=3で考えた場合、連続する0の区間は5カ所ですが、選び方は3通りしかありません。

よって、しゃくとり法などを使って前から順に見ていけば、O(N)で解くことが出来ます。

実装

N,K=gets.chomp.split.map(&:to_i)
S=gets.chomp.split("")
prev=S[0]
ss = []
ss << 0 if prev=='0'

cnt = 1
1.upto(N-1) do |i|
  if prev == S[i]
    cnt += 1
  else
    ss << cnt
    prev = S[i]
    cnt = 1
  end
end
ss << cnt
ss << 0 if S[-1] == '0'

if ss.size/2 <= K
  puts N
  exit
end

tmp = 0
0.step(2*K) do |i|
  tmp += ss[i]
end
ans = tmp
(2*K+1).step(ss.size-2,2) do |i|
  tmp = tmp + ss[i] + ss[i+1] - ss[i-2*K-1] - ss[i-2*K]
  ans = tmp if tmp > ans
end
puts ans

AtCoder: ABC123

A – Five Antennas

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

「直接 通信ができないアンテナの組が存在するかどうか」は距離が最も離れているアンテナの組の距離がk以下であれば存在しないと言えます。
よって、最も距離が離れるaとeの距離を比較すればよいです。

実装

a=[]
5.times do
  a << gets.to_i
end
k=gets.to_i
puts a[4]-a[0]<=k ? "Yay!" : ":("

B – Five Dishes

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

各料理が10の倍数の時刻にしか注文できないということは、ある料理の調理時間がA分だとすると、次の料理を注文できるまでの時間は、「A以上の10の倍数」となります。

次に「最後の料理が届く最も早く」するには、最後の料理をどの料理にするかがポイントです。

調理時間が10で割り切れない料理が存在する場合、10で割った余りが最小の料理を最後に注文すれば、全体の時間が最短になります。

実装

ans=0
min=10
5.times do
  a=gets.to_i
  ans += (a+9)/10*10
  min = a%10 if a%10!=0 && min > a%10
end
if min==10
  puts ans
else
  puts ans - 10 + min
end

C – Five Transportations

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

最も運べる人数が少ない交通機関がボトルネックになるので、全ての交通機関の運べる人数を最少のものにそろえても結果は同じになります。

実装

N=gets.to_i
a=[]
5.times{ a << gets.to_i}
a.sort!
puts (N-1)/a[0]+5

D – Cake 123

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

全てのケーキの組み合わせを求めてから上位K個を求めると、組み合わせが109となり間に合いません。

そこで次のような工夫をします。

  • 上位K個に入るものは、各キャンドルのケーキのうち美味しさが上位K個以内に入っているものの組み合わせに必ずなる
  • 「1のキャンドルの上位K個」と「2のキャンドルの上位K個」の組み合わせを全て求めてそのうち上位K個と「3のキャンドルの上位K個」の組み合わせを求めてから上位K個を求める

このようにすれば、組み合わせはK2のオーダーに抑えることが出来るので十分間に合います。

実装

X,Y,Z,K=gets.chomp.split.map(&:to_i)
a=gets.chomp.split.map(&:to_i)
b=gets.chomp.split.map(&:to_i)
c=gets.chomp.split.map(&:to_i)

ab = []
a.each_with_index do |m, i|
  next if i >= K
  b.each_with_index do |n, j|
    next if j >= K
    ab << m+n
  end
end

ab.sort!.reverse!

abc = []
ab.each_with_index do |m, i|
  next if i >= K
  c.each_with_index do |n, j|
    next if j >= K
    abc << m+n
  end
end

abc.sort!.reverse!

0.upto(K-1) do |i|
  puts abc[i]
end

AtCoder: ABC121

A – White Cells

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

高さH、幅Wの長方形から高さh、幅wだけ除いた残りなので、(H-h)x(W-w)になります。

実装

H,W=gets.chomp.split.map(&:to_i)
h,w=gets.chomp.split.map(&:to_i)
puts (H-h)*(W-w)

B – Can you solve this?

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

各ソースコードiについて、それぞれ条件を満たすかどうかを判定してカウントしていくだけです。

実装

N,M,C=gets.chomp.split.map(&:to_i)
B=gets.chomp.split.map(&:to_i)
ans = 0
N.times do
  a=gets.chomp.split.map(&:to_i)
  t=0
  a.each_with_index do |v,i|
    t += v * B[i]
  end
  ans +=1 if t + C > 0
end
puts ans

C – Energy Drink Collector

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

「最小で何円あればM本の栄養ドリンクを買い集めることができるでしょうか。」ということなので、安い栄養ドリンクを優先的に買っていき、M本

実装

求めるのは買うのに必要な金額なのでどの店舗でいくらの栄養ドリンクを何本買うかは特に考慮する必要はありません。

なので、

  • 各値段の栄養ドリンクが何本存在するかをまとめる(値段のリストは配列、各値段毎の本数はハッシュで管理する)
  • 安い値段の栄養ドリンクから優先的に買っていき、M本に到達したらその時点の金額が解となる

という流れで実装します。

n,m=gets.chomp.split.map(&:to_i)
a=[]
b=Hash.new(0)
n.times do
  aa,bb=gets.chomp.split.map(&:to_i)
  a << aa
  b[aa] += bb
end
a.sort!
a.uniq!
ans = 0
a.each do |v|
  if m <= b[v]
    ans += m * v
    puts ans
    exit
  end
  ans += v * b[v]
  m -= b[v]
end
puts ans
 

D – XOR World

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

A、Bの範囲が最大で1012なので、実際に全ての数字を列挙してXORをとるのは時間的に間に合いません。

この問題の考え方として、1bitに着目した場合のXORの特徴として以下の点を知っているかがポイントになります。

  • 1の数が偶数の場合に0
  • 奇数の場合に1
  • 0の数は無関係

つまり、2進数で考えた場合の桁毎の1の数がいくつになるかを考えればよいです。

次のポイントは以下の式に気づくかどうかだと思います。

$$ f(A,B) = f(0,B) \oplus f(0,A-1) $$

図にするとわかりやすいと思いますが、以下のように0〜A-1の部分のビットは同じなので、XORをとると互いに打ち消し合って0になります。よって、A〜BのXORだけが残ります。

次にf(0,A)の求め方です。これが定数時間で求めることが出来れば問題は解決です。

「任意の偶数とその次の奇数のXORは必ず1になる」という性質に着目します。これは偶数とその次の奇数を2進数で表した場合に、1bit目だけが異なることから明らかです。

よって、Aを4で割った余りが

  • 0の時:f(0,A)はN
  • 1の時:f(0,A)は1
  • 2の時:f(0,A)はN^1
  • 3の時:f(0,A)は0

となります。

実装

A,B=gets.chomp.split.map(&:to_i)
 
def f(n)
  case n%4
  when 0
    n
  when 1
    1 
  when 2
    n^1
  when 3
    0
  end
end
 
puts f(B) ^ f(A-1)

ABC114

A – 753

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

入力Xが7, 5, 3かどうかをチェックするだけです

実装

x=gets.to_i
puts (x==7 || x==5 || x==3)  ? "YES" : "NO"

B – 754

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

文字列の長さが最大で10なので、前から順番に3文字ずつ選んで整数に変換し、753との差の絶対値をとっていき、その最小値を解とすればよいです。

実装

s=gets.chomp
ans=Float::INFINITY
0.upto(s.length-3) do |i|
    ans = (s[i,3].to_i - 753).abs if ans > (s[i,3].to_i - 753).abs
end

C – 755

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

300点にしては意外と難しかったです。

Nは最大で999999999なので、全ての整数をチェックしていくのは現実的では無いです。

ここで、Nが999999999の時に各桁が7, 5, 3のみからなる数字がどれくらいあるか考えます。

この場合、39なので19,683個しかありません。(なお、七五三数は 7, 5, 3がそれぞれ1回以上現れる必要があるので、これより少なくなります)

よって、全ての七五三数を探索してN以下のものを数え上げればよいです。

実装

「7, 5, 3がそれぞれ1回以上」というのがちょっと面倒です。

ここでは、とりあえず7, 5, 3からなる整数を作っておき、後で各数字が1回以上あるかどうかを判定しています。

N=gets.to_i

l = N.to_s.length
n = ['3','5','7']
m = ['3','5','7']
2.upto(l) do |i|
    tmp = []
    m.each do |j|
        n.each do |k|
            if k.length == i-1
                tmp << k + j
            end
        end
    end
    n += tmp
end

ans = 0
n.each do |v|
    if v.include?('3') && v.include?('5') && v.include?('7')
        if v.to_i <= N
            ans += 1
        end
    end
end
puts ans

D – 756

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

七五数の条件である、「約数をちょうど75個持つ正の整数」について最初に考えます。

これは素因数分解すると以下の形で表すことができます。
– p74
– p24q2
– p14q4
– p4q4r2

そこで、N!の素因数分解を行い、N!の約数のうち上記のパターンで表せるものを数えていきます。

なお、N!の素因数分解は、1〜Nをそれぞれ素因数分解し、各指数部分を加算していけば求めることが出来ます。

実装

Rubyのpermutationメソッドを使って組み合わせを列挙し、計算結果がN!の約数かどうかをチェックして数え上げていきます。

require 'prime'
N=gets.to_i
h = Hash.new(0)
1.upto(N) do |i|
    i.prime_division.each do |a,b|
        h[a] += b
    end
end

nn = 1
1.upto(N) do |i|
    nn *= i
end
ans = []
h.keys.permutation(3) do |a,b,c|
    tmp = a**4 * b**4 * c**2
    if nn % tmp == 0
        ans << tmp
    end
end
h.keys.permutation(2) do |a,b|
    tmp = a**24 * b**2
    if nn % tmp == 0
        ans << tmp
    end
    tmp = a**14 * b**4
    if nn % tmp == 0
        ans << tmp
    end
end


h.each do |k,v|
    ans << k ** 74 if v >= 74
end

p ans.uniq.size

ABC088

A – Infinite Coins

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

1円玉には制限があり、500円玉は無制限。
なので、500円玉で払える分は最大限支払い、残りを持っている1円で払えるかを判断すればよいです。

よって、Nを500で割った余りが1円の所持枚数A以下であればYes、そうでなければNoとなります。

実装

N=gets.to_i
puts N % 500 <= gets.to_i ? "Yes" : "No"

B – Card Game for Two

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

  • AliceとBobは交互にカードを選ぶ
  • それぞれ自分の得点を最大化するように最適な戦略を取る

ということは、AliceもBobも残っているカードのうち大きい数字からとっていくことになります。

よって、カードを降順にソートすれば、(0インデックスで)偶数番目をAlice、奇数番目をBobが選ぶことになります。

実装

Aliceの点数 – Bobの点数なので、解としては偶数番目は加算、奇数番目は減算すればよいです。

gets
a=gets.chomp.split.map(&:to_i).sort.reverse
ans=0
a.each_with_index do |v, i|
  ans += i.even? ? v : -v
end
puts ans

C – March

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

300点にしてはちょっと難しかったです。

cとa、bの関係を表すと以下のようになります。

$$
\begin{pmatrix} c_{1,1} & c_{1,2} & c_{1,3} \\
c_{2,1} & c_{2,2} & c_{2,3} \\
c_{3,1} & c_{3,2} & c_{3,3} \end{pmatrix} =
\begin{pmatrix} a_1+b_1 & a_1+b_2 & a_1+b_3 \\
a_2+b_1 & a_2+b_2 & a_2+b_3 \\
a_3+b_1 & a_3+b_2 & a_3+b_3 \end{pmatrix}
$$

ここで、条件を満たす (a1,a2,a3,b1,b2,b3)が存在すると仮定すると、aにxを足したものとbからxを引いたものも、つまり、(a1+x,a2+x,a3+x,b1-x,b2-x,b3-x)も条件を満たすことがわかります。(上の式に当てはめてみるとわかります)

よって、xを調整すれば、a1が0のパターンもあり得ることになります。

よって、a1を0としたときの残りのを求めることができます。

求まった数について、求めるのに使った式以外の式を満たすかどうか判定し、矛盾すればNo、問題無ければYesとなります。

実装

c=[]
3.times { c<< gets.chomp.split.map(&:to_i) }
a = [0]
b = c[0]
1.upto(2) {|i| a[i] = c[i][0] - b[0]}

1.upto(2) do |i|
  1.upto(2) do |j|
    if c[i][j] != a[i] + b[j]
      puts "No"
      exit
    end
  end
end

puts "Yes"

D – Grid Repainting

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

迷路の探索問題の応用でとけます。

まず最初に(1,1)から(H,W)までの最短経路を深さ優先探索などで解きます。

そして、最短経路以外の白マスは黒に変えてしまって良いので、(最初の白マスの数 – 最短経路のマス数)を求めれば良いです。

実装

実装のポイントとして、マスの境界値の判断ロジックをシンプルにするために、事前に外枠を黒マスで囲んでおきます。

H,W=gets.chomp.split.map(&:to_i)
s = []
s << ['#'] * (W+2)
H.times { s << ['#'] + gets.chomp.split("") + ['#']}
s << ['#'] * (W+2)

d = Array.new(H+2).map{Array.new(W+2,Float::INFINITY)}

def dfs(s, d, i, j, c)
  return if s[i][j] == '#'
  return if d[i][j] <= c

  d[i][j] = c
  dfs(s,d,i,j+1,c+1)
  dfs(s,d,i,j-1,c+1)
  dfs(s,d,i+1,j,c+1)
  dfs(s,d,i-1,j,c+1)
end

dfs(s, d, 1, 1, 1)

if d[H][W] == Float::INFINITY
  puts -1
else
  ans = 0
  s.each {|ss| ans += ss.count('.')}
  puts ans - d[H][W]
end

ABC089

A – Grouping 2

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

「3人以上のグループを出来るだけ多く作る」なので、解は\(\lfloor N/3 \rfloor\)になる。

実装

puts gets.to_i/3

B – Grouping 2

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

「桃色、白色、緑色の3種類」or「桃色、白色、緑色、黄色の4種類」なので、黄色(Y)が1つでもあれば4種類、そうでなければ3種類となる。

実装

gets
a=gets.chomp.split(" ")
puts a.include?('Y') ? "Four" : "Three"

C – March

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

組み合わせの条件は以下の2つです。

  • 全ての人の名前が M,A,R,C,H のどれかから始まっている
  • 同じ文字から始まる名前を持つ人が複数いない

1つ目の条件より、入力のうちM,A,R,C,Hで始まらないものは無視して良いことがわかります。

2つ目の条件より、3人の組み合わせとして有効なのは、

(Mで始まる人、Aで始まる人、Rで始まる人)
(Mで始まる人、Aで始まる人、Cで始まる人)
  :
のような組み合わせになります。

ここで、例えば(Mで始まる人、Aで始まる人、Rで始まる人)の組み合わせの数は、

Mで始まる人の人数 x Aで始まる人の人数 x Rで始まる人の人数

で求めることが出来ます。

よって、最初に以下の5つの数を計算しておき、そこから3つを取り出した時の組み合わせ毎にその積をとって、その総和を出せば解になります。

  • Mで始まる人の人数
  • Aで始まる人の人数
  • Rで始まる人の人数
  • Cで始まる人の人数
  • Hで始まる人の人数

実装

rubyで組み合わせを求める場合、配列のcombinationを使うと簡単です。

N=gets.to_i
h=Hash.new(0)
N.times do
  s = gets.chomp
  h[s[0]] += 1 if s[0] == 'M' || s[0] == 'A' || s[0] == 'R' || s[0] == 'C' || s[0] == 'H'
end

ans = 0
h.values.combination(3) do |l,m,n|
  ans += l*m*n
end
puts ans

D – Practical Skill Test

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

LからRへDずつ移動した際の距離の総和を求める問題です。

L、Rは最大9万なので、距離を求めるのが1回であれば、Dずつ移動しながら移動距離の総和を出せば良いです。

しかしながら、与えられるL、Rの組み合わせの数Qは最大105なので、都度Dずつ移動しながら距離を計算するのは時間がかかりすぎます。

よって、L、Rが与えられた時に定数時間で移動距離を出す方法を考える必要があります。

考え方のポイントとしては、Dは常に一定である、という点です。

例えば入力例1のように、Aが1〜9でDが2である場合、移動パターンは以下の2種類しかありません。

  • 1 → 3 → 5 → 7 → 9
  • 2 → 4 → 6 → 8

よって、奇数の場合は1からの累積距離、偶数の場合は2からの累積距離、を事前に求めておくことで、任意の点間の移動距離を定数時間で求めることが出来ます。

例えば、例1の4から8の場合は、(2から8の累積距離)-(2から4の累積距離) を計算すれば、4から8への移動距離を求めることが出来ます。

実装

H,W,D=gets.chomp.split.map(&:to_i)
p = Array.new(H*W+1)
H.times do |i|
  gets.chomp.split.map(&:to_i).each_with_index do |v,j|
    p[v] = [i,j]
  end
end

d = [0] * (D+1)
(D+1).upto(H*W) do |i|
  d[i] = d[i-D] + (p[i][0] - p[i-D][0]).abs + (p[i][1] - p[i-D][1]).abs
end

Q=gets.to_i
Q.times do
  l,r = gets.chomp.split.map(&:to_i)
  puts d[r] - d[l]
end

AtCoder BC074 D: Restoring Road Network

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

ワーシャルフロイド法をベースにしてその考え方を応用することで解けます。

問題を「道路の構造が存在するかどうか」と「存在する道路の長さの和が最小となるようなもの」の二つに分けて考えます。

  • 道路の構造が存在するかどうか

表Aが「都市間の道路に沿った最短距離を表した表」なので、表Aに対してワーシャルフロイド法を適用し、表内の値が更新されることがあった場合に表Aは矛盾することになります。

例えば、(iからjへの距離)> (iからkへの距離)+(kからjへの距離)のような場合に、表Aはそもそも矛盾することになります。

よってそのような組み合わせが一つでもあれば、’-1’を出力して終了すれば良いです。

  • 存在する道路の長さの和が最小となるようなもの

どのような場合に道路が存在しないといけないかを考えます。

表Aは各都市間の最短経路を表しているので、iからjへの経路を考える場合、

(iからjへの距離)= (iからkへの距離)+(kからjへの距離)

のようなkが存在した場合、k経由で迂回しても距離は変わらないので、iからjへの道路は不要ということになります。

よって、表のサイズと同じ表を用意しておき、道路が必要か不要かをtrue/falseなどで記憶しておき、最後にtrueな経路の距離だけ加算すればよいです。

実装

#include<iostream>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;

typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;

    cin >> N;

    ll a[N][N];
    bool f[N][N];

    REP(i,N)REP(j,N)cin >> a[i][j];
    REP(i,N)REP(j,N)f[i][j] = true;

    REP(k,N)REP(i,N)REP(j,N){
        if(a[i][k] + a[k][j] < a[i][j]){
            cout << -1 << endl;
            return 0;
        }else if(a[i][k] + a[k][j] == a[i][j] && i != k && k != j){
            f[i][j] = false;
        }
    }

    ll ans = 0;
    REP(i,N)REP(j,N){
        if(f[i][j])ans+=a[i][j];
    }

    cout << ans / 2 << endl;
}