おじい研究所

主にプログラミングの話題です

256【解説】

本稿はCodeIQで2016年7月12日~2018年4月25日に出題された 【実力判定:Cランク】256 という問題の解答例と簡単な解説です。

  • 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」とか、「他の言語で書いてみたよ!」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

256【解説】

入力サイズが小さいので、素直に二重ループでよいでしょう。数値のリストから同じ要素を2回選ばないように注意してください。

# python3
# O(n^2)

n = int(input())
v = [int(s) for s in input().split()]

for i in range(n-1):
    for j in range(i+1, n):
        if v[i] + v[j] == 256:
            print("yes")
            exit() # 見つかったらおしまい

# 見つからなければココに到達する
print("no")

「2人組作って!」【解説】

本稿はCodeIQで2014年9月4日~2014年9月16日に出題された プログラミング言語★総選挙 予備選挙「2人組作って!」 という問題の解答例と簡単な解説です。

  • 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」とか、「他の言語で書いてみたよ!」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

「2人組作って!」【解説】

◆解説

欠席者が最大1という制約でペアを作る問題でした。欠席者が0か1であれば、次のようなルールで判別することができます。

f:id:Ozy:20180507150100p:plain

生徒の位置によって、ABのグループに分けると、Aのグループの人数とBのグループの人数が等しくなった場合にペアを作ることができます。

f:id:Ozy:20180507150139p:plain f:id:Ozy:20180507150158p:plain

の場合はAもBも4ずつになり、うまくペアを作ることができますが、

f:id:Ozy:20180507150211p:plain

の場合はAが5でBが3となり、数が等しくなくなりますので、ペアを作ることができません。 この性質を利用すれば、単純に出席者をグループ毎に数えるだけで済みます。

# python3
import sys

# index[x, y]について、x+yが偶数ならa、奇数ならbを増やす
a = b = 0

for i, s in enumerate(sys.stdin):
    for j, c in enumerate(list(s)): # 1文字ずつ処理
        if c == 'O': # 出席者
            if i+j & 1 == 0: # indexの偶奇を調べる
                a += 1
            else:
                b += 1

print("yes" if a == b else "no")

最大の攻撃を繰り出せ!【解説】

  • 本稿はCodeIQで出題された 第1回プロコン:【鬼】最大値をたたき出す攻撃を繰り出して鬼を倒そう という問題の解答例と簡単な解説です。

  • 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」とか、「他の言語で書いてみたよ!」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

最大の攻撃を繰り出せ!【解説】

◆解説

a3 + b3 = c3 + d3…(1)を満たすa, b, c, dについてすべての場合を総当たりで解こうとすると、入力の最大値が1000ですので大雑把に計算量を見積もると、約1000の4重ループで10004近い計算を行うことになります。このままでは制限時間を超えてしまいますので、ループ回数をもう少し抑える工夫をしてみます。 x3 + y3 = k (ただしx < y)とすると、この等式を満たすx, yが2通り以上あれば、(1)を満たすa, b, c, dが存在すると言えます。そこでkをキーとしたハッシュマップを用いて、取り得るkの値をすべて記録していきます。ハッシュマップをhとすると、xとyの組み合わせに重複が無いように列挙すれば、あるx, yについて、h[k]が存在しなければh[k]を登録し、もしすでに存在していれば、それはx, yの組み合わせが少なくとも2種類は存在するという意味になります。この時のkの値の中から最大のものを見つけることで解が得られます。

◆解答例

#!ruby

n = STDIN.gets.to_i
h = Hash.new
m = 0
(1..n-1).each{|x|
  (x+1..n).each{|y|
    k = x*x*x + y*y*y
    if h[k]
      m = k if k > m
    else
      h[k] = true
    end
  }
}
puts m

「MENMA」を探そう【解説】

  • 本稿はCodeIQで出題された 第1回プロコン:【猿】偏食の猿の好き嫌いを見極めよう という問題の解答例と簡単な解説です。

  • 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」とか、「他の言語で書いてみたよ!」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

「MENMA」を探そう【解説】

◆解説

これは検索文字列"MENMA"の文字数を深さの最大とした深さ優先探索を素直に実装するだけの問題です。テストケースは大きくありませんので、特別な工夫を行う必要はありません。落ち着いてコーディングしましょう。

◆解答例

#!ruby

$w = "MENMA"
$v = STDIN.readlines.map{|s|s.strip.split''}

def dfs(d, cx, cy, ox, oy)
  
  return $w[d] == $v[cx][cy] if d+1==$w.size
  
  return false if $w[d] != $v[cx][cy]
  
  [ [-1,0], [1,0], [0,-1], [0,1] ].each{|u|
    nx, ny = [cx,cy].zip(u).map{|t|t.inject(&:+)}
    next if [nx,ny] == [ox,oy]
    next if nx<0 || ny<0 || nx>=$v.size || ny>=$v.size
    
    return true if dfs(d+1, nx, ny, cx, cy)
  }
  
  return false
end

n = $v.size
n.times{|i|
  n.times{|j|
    if dfs(0, i, j, i, j)
      puts"yes"
      exit
    end
  }
}

puts"no"

少ない重りで重さを量ろう【解説】

  • 本稿はCodeIQで出題された 第1回プロコン:【雉】くそ生意気な雉を黙らせよう という問題の解答例と簡単な解説です。

  • 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」とか、「他の言語で書いてみたよ!」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

少ない重りで重さを量ろう【解説】

◆解説

1つひとつの分銅には、「左に置く」「右に置く」「置かない」という3つの選択があります。つまりn個の分銅を用いると、3n通りの置き方があります。ただし、1つの分銅を左に置く場合と右に置く場合で量ることのできる重量は変わりませんから、左右の違いは1つのペアと考えなければなりません。
たとえば、AとBの2つの分銅を使って、左にA・右にBを乗せる場合と、左にB・右にAを乗せる場合とでは、量ることのできる重量は同じです。左にAB・右はナシの場合と左はナシ・右にABの場合も同じ重量です。唯一ペアにならない(ペアが存在しない)のは、おもりを1つも乗せない場合です(左に乗せないや右に乗せないとは言いませんね)。 以上から、n個の分銅を用いて表すことのできる0以上の連続する整数値は、最大で(3n – 1) / 2と表すことができます。

◆解答例

#!ruby
n = STDIN.gets.to_i
m = 1

while (3**m-1)/2 < n
  m += 1
end

puts m

◆補足

本問の解答には必要ありませんが、n個の分銅の質量は、3n-1グラムにします。たとえば、分銅を2つ用意する場合、1グラム(A)と3グラム(B)にすると、

  • 乗せない…0グラム
  • Aだけ乗せる…1グラム
  • 一方にA、もう一方にBを乗せると…3-1=2グラム
  • Bだけを乗せる…3グラム
  • 一方にAB両方を乗せる…3+1=4グラム

のように4グラムまで表すことができ、(32 - 1) / 2の値と一致します。分銅を3つ用意する場合、1グラム(A)、3グラム(B)、9グラム(C)にすると、先程の0~4グラムに加えて、

  • 一方にC、もう一方にAB…5グラム
  • 一方にC、もう一方にB…6グラム
  • 一方にAC、もう一方にB…7グラム
  • 一方にC、もう一方にA…8グラム
  • 一方にだけC…9グラム
  • 一方にだけAC…10グラム
  • 一方にBC、もう一方にA…11グラム
  • 一方にだけBC…12グラム
  • 一方にだけABC…13グラム

のように、13グラムまで表すことができ、(33 - 1) / 2の値と一致します。

接待じゃんけん【解説】

  • 本稿はCodeIQで出題された 第1回プロコン:【犬】自信を無くした犬に自信を取り戻させよう という問題の解答例と簡単な解説です。

  • 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」とか、「他の言語で書いてみたよ!」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

接待じゃんけん【解説】

この問題は、プロコン初参加の人のために標準入出力の扱いを体験してもらう目的で用意しました。正解・不正解のみの評価ですので、コードの読みやすさとか丁寧さはあまり気にせず、好きなように書けば良いでしょう。

◆解答例

#!ruby
puts( { 'G'=>'C', 'C'=>'P', 'P'=>'G' }[STDIN.getc] )

CodeIQ過去問集40:欲張り団子

本稿はCodeIQで出題予定だったものの事情があって出題できなかった 【実力判定:Sランク】欲張り団子 という問題です。 Sランクとありますがだいぶヌルいです。

欲張り団子

【問題】

正方形のマス目があります。
マス目のいくつかには団子があります。
この団子に、タテ・ヨコ・ナナメ(水平方向から±45度)の方向から串を刺して団子を取ります。
このとき、できるだけ少ない本数の串ですべての団子を取る方法を考え、串の本数の最小値を答えてください。

f:id:Ozy:20180502203807p:plain

たとえばこのような配置の場合、次のように2本の串ですべての団子を取ることができます。

f:id:Ozy:20180502203818p:plain

【入力】

標準入力から、次の値が与えらえます。
1行目には、正方形の一辺のサイズN(8以下の正の整数)、
2行目以降のN行分は長さNの文字列で、団子がある場所を示す「o」、団子がない場所を示す「x」のいずれかになっています。

【出力】

すべての団子を取るのに必要な串の本数の最小値(値のみ)を出力してください。

【入出力サンプル】

Input

3
ooo
xox
oxx

Output

2

【解答方法】

yokubari_dango.zipをダウンロードし、展開してください。中には以下のフォルダが含まれています。

  • input: テストデータです
  • output: 解答データです

テストデータを入力として、解答データと一致する出力になるようなプログラムを書いてください。

[【解答例】]


こっちは古い版