ATO's blog

メモとか日記とか

CodeIQのプログラミングコンテストに挑戦しました

codeiq.jp

犬

codeiq.jp

【問題】

犬が出そうとしている手を読み取って、わざと負けてあげるように手を出してください。

グーを「G」、チョキを「C」、パーを「P」とすると、たとえば犬が「G」を出そうとしているときは「C」を出してあげてください。

コード

rubyで。
一切の思考を放棄して問題文通り書いた。

input = gets.chomp.strip

if input == "G"
  puts "C"
elsif input == "C"
  puts "P"
else
  puts "G"
end

雉

codeiq.jp

【問題】

てんびんが1つあります。

1グラムからnグラムまで、1グラム刻みの重さn通りすべてを、

それぞれてんびんを1回使うことで量ることができるようにします。

使用するおもりの個数をできるだけ少なくなるようにすると、おもりは最低いくつ必要になるかを計算するプログラムを書いてください。

コード

犬が想像以上に簡単だったから舐め切ってたら突然の難易度急上昇でびっくりした。
かなり時間をかけて書いたけど考え方を間違えてたせいでワンミス。
2回目の提出でクリア。
以下正解したコード。

N = gets.chomp.strip.to_i
i = 1
while 3**i/2 < N
  i+=1
end
p i

方針

N以下の自然数を、i個以下の整数の加減算で表すパターンの数を考える。
例えばi=2のとき、任意の整数A,Bの加減算(とAおよびB)で表せるパターンは、分かりやすく全て加算で表し係数(1,0,-1)を明示すると

0*A+0*B
0*A+1*B
0*A+(-1)*B
1*A+0*B
1*A+1*B
1*A+(-1)*B
(1-)*A+0*B
(-1)*A+1*B
(-1)*A+(1-)*B

の9通り。
A>Bとすると、このうち結果が正になるのは

0*A+1*B
1*A+0*B
1*A+1*B
1*A+(-1)*B

の4通りになるので、A、Bの値をうまく調整すれば1から4までを2つの整数とその加減算で表すことができる。
実際、A=3、B=1とすると1から4までを上記パターンで表せる事が分かる。
よって、パターンの数は概ね3^i/2程度以下に収まりそうだとあたりを付けて、条件を満たすようなiを1から探す事にしたところ、正解することができた。
厳密に正しいのか、i個の自然数に何を使えばいいのかまでは分からないが、正解できたので良しとした。

猿

codeiq.jp

【問題】

n×n(5≦n≦100)の文字列の中から、「MENMA」と連続する部分があるかどうかを判定してください。

MENME
NMENM
ENMEN
MENMA
NMENM

のように一直線に並んでいる場合だけでなく、
途中で折れ曲がっていても構いません。

コード

menma = ["M", "E", "N", "M", "A"]

noodle = []
noodle << gets.chomp.split("")

N = noodle[0].size
2.upto(N) do |i|
  noodle << gets.chomp.split("")
end

def check(n, mnm, i0, j0, i, j, m)
  if n[i][j] == mnm[m-1]
    if mnm.size == m
      puts "yes"
      exit
    end
    
    i1 = i + 1
    j1 = j
    check(n, mnm, i, j, i1, j1, m+1) if i1 < N && j1 < N && (i1 != i0 || j1 != j0)
    
    i1 = i
    j1 = j + 1
    check(n, mnm, i, j, i1, j1, m+1) if i1 < N && j1 < N && (i1 != i0 || j1 != j0)
    
    i1 = i - 1
    j1 = j
    check(n, mnm, i, j, i1, j1, m+1) if i1 >= 0 && j1 >= 0 && (i1 != i0 || j1 != j0)
    
    i1 = i
    j1 = j - 1
    check(n, mnm, i, j, i1, j1, m+1) if i1 >= 0 && j1 >= 0 && (i1 != i0 || j1 != j0)
    
  end
end

i = 0

while i < N
  j = 0
  while j < N
    check(noodle, menma, i, j, i, j, 1)
    j += 1
  end
  i += 1
end

puts "no"

単純に端から再帰を使って虱潰しに探した。特に高速化の工夫とかはしてないけど無事一回で全部のテストケースをクリアできた。
ぶっちゃけ雉のほうが難しかった

鬼

codeiq.jp

【問題】

4つのブロックを立方体と考えます。

一辺の長さをそれぞれa, b, c, dとして、


　X = a^3 + b^3

　Y = c^3 + d^3


とするとき、X = Yを満たすX(=Y)の最大値を求めてください。（a,b,c,dにはそれぞれ別の数字が入るとします）

たとえば、1辺の長さが1～20までのときは

　(1) 1^3 + 12^3 = 9^3 + 10^3

　(2) 2^3 + 16^3 = 9^3 + 15^3

のような場合が考えられますが、

(1)を計算すると1729、(2)を計算すると4104となりますので、4104が条件を満たす最大値となります。

【入力】

標準入力から、一辺の長さの最大値として整数値（20～1000）が与えられます。


【出力】

標準出力に、解となる整数値のみ出力してください。

出力後の改行の有無は問いません。

例の(1)なんかはラマヌジャンの逸話として割と有名だけど、調べてもいい解法がよく分からなかったからマシンパワーでゴリ押しする事にした。

コード

N = gets.chomp.to_i
cube = {}

N.times do |n|
  c = (n+1)**3
  cube[c] = n+1
end

max = 0
res = 0
cnt1 = 0
cnt2 = -1
a = N
while a > 0 && cnt1 != cnt2
  cnt2 = cnt1
  c = a-1
  while c > 0
    d = c-1
    while d > 0 && a+d-1+c+d > max
      y = c*c*c+d*d*d
      b = cube[y - a*a*a]
      cnt1 += 1
      if b
        if res < y
          max = a+b+c+d
          res = y 
        end
      end
      d -= 1
    end  
    c -= 1
  end
  a -= 1
end
puts res

a,b,c,dの4つの変数のうち3つを3重ループで全通り調べて、条件に合う(a^3+b^3=c^3+d^3を満たす)整数が存在するかを調べる。
最終問題なだけあって、単純に全パターンを探索すると、最大値が与えられたとき制限時間(1秒)に引っかかる。
制限時間を超えないよう、適当な所で探索を打ち切るようにした。
具体的には、条件を満たす数が見つかった時のa,b,c,dの値を合算して保持し、a,b,c,dの値の候補の最大値の合計がその数より少なくなった時点で探索を打ち切った。*1
自分のPCスペックが足りないせいで、入力値が1000の時最後まで1秒を切る事が出来ず絶望してたけど、
「CodeIQ実行くん」でためしたら0.8秒くらいで動いたからそのまま提出した。
結果は始め適当に書いた奴が間違っててワンミス。ただ、何故かそのワンミスがシステムにカウントされてなくて一発クリアした扱いになってた。

最終ランキング

codeiq.jp
ランキング：　現在106位（ 639人中）
総合得点：　400点
総挑戦回数：　5回
合計解答時間：　3:46:50

こんな感じだった。惜しくも100位以内に入れずランキング圏外。
でも雉や鬼で1回目の提出で間違えた後、再挑戦するまでに考えた時間は合計時間に含まれてないし、そもそも鬼の時のワンミスがカウントされてなくて数秒で一発クリアした扱いになってるからランキングはかなりガバガバなのであくまで参考程度。
何はともあれ、割と楽しめたので次回コンテストがあるならまたチャレンジしたい。

*1:この記事を書いていて思ったけどa,b,c,d全部保持しなくてもa,bまたはc,dのペアだけでよかったかもしれない