2018-05-03

「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"

2018-05-03

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

本稿はCodeIQで出題された 第1回プロコン：【雉】くそ生意気な雉を黙らせよう という問題の解答例と簡単な解説です。
本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ！」とか、「こう書いた方がわかりやすいよ！」とか、「他の言語で書いてみたよ！」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

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

◆解説

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

◆解答例

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

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

puts m

◆補足

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

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

のように4グラムまで表すことができ、(3² - 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グラムまで表すことができ、(3³ - 1) / 2の値と一致します。

2018-05-03

接待じゃんけん【解説】

本稿はCodeIQで出題された 第1回プロコン：【犬】自信を無くした犬に自信を取り戻させよう という問題の解答例と簡単な解説です。
本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ！」とか、「こう書いた方がわかりやすいよ！」とか、「他の言語で書いてみたよ！」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

接待じゃんけん【解説】

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

◆解答例

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

2018-05-02

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

CodeIQ過去問集

本稿は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

【解答方法】

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

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

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

[【解答例】]

2018-05-02

CodeIQ過去問集39：てんびんビーン

CodeIQ過去問集

本稿はCodeIQで出題予定だったものの事情があって出題できなかった 【実力判定：Aランク】てんびんビーン という問題です。 Aランクとありますがだいぶヌルいです。

てんびんビーン

【問題】

てんびんと、重さの異なるマメがいくつかあります。
すべてのマメを使って、てんびんが釣り合う乗せ方があるかどうかを判定してください。

たとえば{110mg, 120mg, 230mg}の3つのマメがある場合、
{110mg, 120mg} と {230mg}に分ければてんびんは釣り合いますが、
{110mg, 120mg, 200mg}の3つのマメの場合はどのように分けても釣り合いません。

【入力】

標準入力から、次の値が与えらえます。
1行目には、マメの個数N（20以下の正の整数）、
2行目はN個の整数値（10000より小さい正の整数）が半角スペースで区切られています。

【出力】

同じ重さに分けることができる場合は「yes」、できない場合は「no」と（いずれの場合も小文字で）出力してください。

【入出力サンプル】

Input

3
110 120 230

Output

yes

【解答方法】

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

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

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

[【解答例】]

2018-05-02

CodeIQ過去問集38：パインスイーパ

CodeIQ過去問集

本稿はCodeIQで出題された 【実力判定：Bランク】パインスイーパ という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。

パインスイーパ

【注意】

どう見てもマインスイーパです。本当にありがとうございました。

【問題】

正方形のマス目があります。

マス目のいくつかにはパイナップルが置かれています。このとき、パイナップルが置かれているマス目以外のすべてのマス目について、周囲にあるパイナップルの数を数えてください。

f:id:Ozy:20180502174344j:plain

たとえばこのような配置の場合、空いているマス目ごとに周囲8マスのパイナップルの数を数えると、

f:id:Ozy:20180502174402j:plain

のようになります。

【入力】

標準入力から、次の値が与えらえます。 1行目には、正方形の一辺のサイズN（20以下の正の整数）、2行目以降のN行分は長さNの文字列で、空白を表す「.」かパイナップルを表す「P」のいずれかになっています。

【出力】

力文字列の「.」の部分をパイナップル数に置き換えた文字列を出力してください。

【入出力サンプル】

Input

4
.P.P
....
..P.
....

Output

【解答方法】

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

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

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

[【解答例】]

2018-05-02

CodeIQ過去問集37：ぴったりビット

CodeIQ過去問集

本稿はCodeIQで出題された 【実力判定：Cランク】ぴったりビット という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。

ぴったりビット

【問題】

2進表現で

10011101
01100010

のように、各桁に対して片方のビットが1のとき、もう片方のビットが0になっている場合、「ぴったりビット」であるとします。 2つの非負整数が10進数として与えられたとき、2数がぴったりビットである場合は"yes"、そうでない場合は"no"と出力してください。

【入力】

標準入力から、整数値が与えられます。 1行目は整数値N（Nは20以下の非負整数）、2行目以降のN行は2つの整数値（いずれも255以下の非負整数）の組が半角スペースで区切られています。

【出力】

各組に対して、ぴったりビットである場合は"yes"、そうでない場合は"no"と、標準出力に出力してください。

【入出力サンプル】

Input

2
157 98
28 98

Output

yes
no

【解答方法】

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

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

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

[【解答例】]