最大の攻撃を繰り出せ!【解説】
本稿は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度)の方向から串を刺して団子を取ります。
このとき、できるだけ少ない本数の串ですべての団子を取る方法を考え、串の本数の最小値を答えてください。
たとえばこのような配置の場合、次のように2本の串ですべての団子を取ることができます。
【入力】
標準入力から、次の値が与えらえます。
1行目には、正方形の一辺のサイズN(8以下の正の整数)、
2行目以降のN行分は長さNの文字列で、団子がある場所を示す「o」、団子がない場所を示す「x」のいずれかになっています。
【出力】
すべての団子を取るのに必要な串の本数の最小値(値のみ)を出力してください。
【入出力サンプル】
Input
3 ooo xox oxx
Output
2
【解答方法】
yokubari_dango.zipをダウンロードし、展開してください。中には以下のフォルダが含まれています。
- input: テストデータです
- output: 解答データです
テストデータを入力として、解答データと一致する出力になるようなプログラムを書いてください。
[【解答例】]
CodeIQ過去問集39:てんびんビーン
本稿は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: 解答データです
テストデータを入力として、解答データと一致する出力になるようなプログラムを書いてください。
[【解答例】]
CodeIQ過去問集38:パインスイーパ
本稿はCodeIQで出題された 【実力判定:Bランク】パインスイーパ という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。
パインスイーパ
【注意】
どう見てもマインスイーパです。本当にありがとうございました。
【問題】
正方形のマス目があります。
マス目のいくつかにはパイナップルが置かれています。 このとき、パイナップルが置かれているマス目以外のすべてのマス目について、周囲にあるパイナップルの数を数えてください。
たとえばこのような配置の場合、空いているマス目ごとに周囲8マスのパイナップルの数を数えると、
のようになります。
【入力】
標準入力から、次の値が与えらえます。 1行目には、正方形の一辺のサイズN(20以下の正の整数)、2行目以降のN行分は長さNの文字列で、空白を表す「.」かパイナップルを表す「P」のいずれかになっています。
【出力】
力文字列の「.」の部分をパイナップル数に置き換えた文字列を出力してください。
【入出力サンプル】
Input
4 .P.P .... ..P. ....
Output
1P2P 1232 01P1 0111
【解答方法】
pinesweeper.zipをダウンロードし、展開してください。中には以下のフォルダが含まれています。
- input: テストデータです
- output: 解答データです
テストデータを入力として、解答データと一致する出力になるようなプログラムを書いてください。
[【解答例】]