【4/13アプデ対応版】スペシャル増加量アップと減少量ダウンのおすすめの組み合わせを教えてくれるツールを作りました
(追記)4月13日のアプデに対応させました。
ついでにシャープマーカー以外の武器でもいい感じに計算してくれるようにしました。
『Splatoon(スプラトゥーン)』更新データ(Ver.2.7.0)の詳細内容
atolog.hatenablog.com
毎回計算するのも面倒だったので、以前書いた記事を元にスぺ増スぺ減の効率的な積み方をサクッと計算できるツールを作りました。
chromeでのみ動作確認しています。
CodeIQ「ステップ・アップ・サム問題」に挑戦したようです
■問題
自然数 n を、2つ以上の連続する自然数の和で表すことを考えましょう。 例えば、18 は 5 + 6 + 7 や 3 + 4 + 5 + 6 と表すことができます。 同様に、15 は 7 + 8 や 4 + 5 + 6 や 1 + 2 + 3 + 4 + 5 と表すことができます。 いずれもこれら以外の表し方は存在しません。 この表し方における最も小さな数(上で太字で記した数のことです)を、全ての表し方について和をとったものを F(n) と定義します。 例えば F(18) = 5 + 3 = 8、F(15) = 7 + 4 + 1 = 12 です。 同様に、F(105) = 139、F(256) = 0、F(945) = 1698 であることが確かめられます。 標準入力から、自然数 n(1 ≦ n ≦ 1010)が与えられます。 標準出力に F(n) の値を出力するプログラムを書いてください。
■コード
いつも通りrubyで。
def f(x) i = 2 res = 0 while i*(i+1) <= 2*x if (i%2 == 0) res += x/i-i/2+1 if (x%i == i/2) else res += x/i-i/2 if (x%i == 0) end i+=1 end res end while str = STDIN.gets puts f(str.to_i) end
今回は前回と比べて難易度低めだった。
■方針
nをi個の連続する自然数の和で表す事を考える。
iが奇数の時
例えばi=3の時、n=3mと表せるとする。以下のように変形すると
n=m+m+m=(m+1)+m+(m-1)
となり、nが3の倍数の時は連続する3つの自然数の和で表すことができる。
n=5,7,9,11...の時も同様に、5,7,9,11...個の自然数の和で表せる。
また、最小値はm-(i/2(小数切り捨て))となる。
iが偶数の時
例えばi=4の時、n=4mと表せるとする。以下のように変形すると、
n=m+m+m+m=(m+3/2)+(m+1/2)+(m-1/2)-(m-3/2)
となり、nが4の倍数の時はm+3/2,m+1/2,m-1/2,m-3/2が自然数となるならば、連続する4つの自然数の和で表すことができる。
つまり、mが整数+1/2であればよく、nをiで割った時の余りがi/2であればこれを満たす。
n=2,6,8,10,12...の時も同様。
最小値はm(小数切り捨て)-i/2+1となる。
nをi個の連続する自然数の和で表すとき、iが最大になるのは1から足していく場合なので、公式より
i*(i+1) <= 2*n
をiが満たす間繰り返し、最小値の合計を求めると答えが得られる。
CodeIQのプログラミングコンテストに挑戦しました
犬
【問題】 犬が出そうとしている手を読み取って、わざと負けてあげるように手を出してください。 グーを「G」、チョキを「C」、パーを「P」とすると、たとえば犬が「G」を出そうとしているときは「C」を出してあげてください。
コード
rubyで。
一切の思考を放棄して問題文通り書いた。
input = gets.chomp.strip if input == "G" puts "C" elsif input == "C" puts "P" else puts "G" end
雉
【問題】 てんびんが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までを上記パターンで表せる事が分かる。
よって、パターンの数は概ね程度以下に収まりそうだとあたりを付けて、条件を満たすようなiを1から探す事にしたところ、正解することができた。
厳密に正しいのか、i個の自然数に何を使えばいいのかまでは分からないが、正解できたので良しとした。
猿
【問題】 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"
単純に端から再帰を使って虱潰しに探した。特に高速化の工夫とかはしてないけど無事一回で全部のテストケースをクリアできた。
ぶっちゃけ雉のほうが難しかった
鬼
【問題】 4つのブロックを立方体と考えます。 一辺の長さをそれぞれa, b, c, dとして、 とするとき、X = Yを満たすX(=Y)の最大値を求めてください。(a,b,c,dにはそれぞれ別の数字が入るとします) たとえば、1辺の長さが1~20までのときは (1) (2) のような場合が考えられますが、 (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重ループで全通り調べて、条件に合う(を満たす)整数が存在するかを調べる。
最終問題なだけあって、単純に全パターンを探索すると、最大値が与えられたとき制限時間(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のペアだけでよかったかもしれない
CodeIQ「スロットマシン問題」に挑戦したようです
問題
n 個のリール(数字が描かれている部分です)を持つスロットマシンを回します。 各リールには、0 から 9 のいずれかの数字がランダムに出ます。 このとき、「最も多く出現した数字の出現回数」に等しいドルが賞金として得られます。 例えば n = 6 のスロットマシンを考えましょう。 各リールに、左から順に 7 7 5 1 0 7 という数字が出たとします。 このとき、7 の数字が最も多く 3 回出現していますので、賞金は 3 ドルです。 このスロットマシンを 1 回まわしたときの賞金の期待値を F(n) とします。 例えば F(1) = 1,F(2) = 1.1,F(3) = 1.29 となることが確かめられます。 ■ 第1問 (Normal) F(6) の値を求めて下さい(四捨五入は不要です)。 ■ 第2問 (Hard) F(12) の値を求めて下さい(四捨五入は不要です)。
提出したコード
def fact(n) result = 1 1.upto(n){|i| result *= i} result end def c(n, r) fact(n)/(fact(n-r)*fact(r)) end #配列の値を計算 def calcArray(arr, n) sum = 0 num = 10 r = n result = 1 count = Array.new(n+1, 0) #2つ以上ある要素を掛ける arr.each do |v| if v > 1 sum += v result *= num * c(r, v) count[v] += 1 num -= 1 r -= v end end #1つしかない要素を掛ける (sum+1).upto(n) do |i| result *= num num -= 1 end #重複の排除 count.each {|v| result /= fact(v)} result end #分割を列挙し、パターンごとに組み合わせの数を計算する def calcPartition(arr, n, p, index, sum) return 0 if arr.size <= index result = 0 arr[index] = 2 sum += 2 while arr[index] <= p && sum <= n result += calcArray(arr, n) result += calcPartition(arr, n, arr[index], index+1, sum) arr[index] += 1 (index+1).upto(arr.size-1){|i| arr[i] = 0} end result end #期待値を求める def f(n) i = 1 result = 0 while i <= n arr = Array.new(n, 0) arr[0] = i sum = calcArray(arr, n) sum += calcPartition(arr, n, i, 1, i) result += sum.to_f * i / 10 ** n i += 1 end result end p f(1) p f(2) p f(3) p f(6) p f(12)
rubyで。
方針
貰える賞金にはリールの数値や数値の位置は関係ないので、同じ数値が何回出てくるかのパターンを考える。
例えばn=4の時は1:すべて同じ、2:3つ同じ、3:2つ同じの組み合わせが2つ、4:2つだけ同じで残りがバラバラ、5:全て違う、の5通りある。
1桁を1文字で表すと以下のような感じ。
1:AAAA
2:AAAB
3:AABB
4:AABC
5:ABCD
各パターンを同じ数字の個数に注目して以下のように表すと、nを適当な正の整数の足し算で表すパターンの列挙になる。
こういうのを分割と言うらしい。
1:4
2:3+1
3:2+2
4:2+1+1
5:1+1+1+1
これらのパターンの列挙さえ出来れば、あとは単純に期待値を求める問題だけど、このパターン列挙が難しかった。
色々試したらnを分割する際の一番大きい数字(スロットを回した時の得点)をpとして、残りのn-pをp以下の数で分割するパターンを再帰的に探す方法で何とかうまくいった。
他の人の回答
togetter.com
そういえばrubyにはinjectとかそういった便利なメソッドがありましたね…。折角ruby使ってるのに全然使いこなせてないので頑張って使いこなしたい。
CodeIQ「カット・アンド・スクエア」問題に挑戦したようです
偶数 n に対して、先頭にゼロを持たない n 桁の整数で、次の条件を満たすものを考えましょう。 【条件】 この数を上 n/2 桁と下 n/2 桁とに分け、それぞれを 2 乗して和をとると、元の数に戻る。 ■ 第2問 (Hard) n = 10 の場合にこの条件を満たす全ての数の総和を求めてください。
提出したコード
rubyで。
def f(n) m = 10**(n/2) res = [] ad = n > 4 ? [10, 2, 8, 10, 8, 2, 10] : [2, 6, 2] i = m/10 k = 0 while i < m i2 = i*i im = i*m s = Math.sqrt(im - i2).ceil e = Math.sqrt(im+m-1 - i2).floor j = s while j <= e if i2+j*j == im+j res << im+j break end j += 1 end i += ad[k%ad.size] k += 1 end res end puts "N=4" puts f(4).join "\n" puts "N=6" puts f(6).join "\n" puts "N=10" puts f(10).join "\n" puts "SUM(N=10)" s = 0 f(10).map{|v| s += v} puts s
方針
N桁の数の上N/2桁から下N/2桁を決定する。
たとえばN=6の時、6桁の数をAAAxxxとおくと、求めるべきxxxは√(AAA000-AAA^2)~√(AAA999-AAA^2)の間に存在する。
AAAの値を100~999まで変えて、虱潰しに計算する。
また、AAAの値の候補は(全通り調べた結果)AAAの下2桁が00,10,12,20,30,38,40,50,60,62,70,80,88,90の数字なので、それだけ調べる。
何も考えずに問題通り回ループさせると何時間かかるか考えたくもないが、こうすればだいたい回のループで済む。
実行時間は0.2秒くらい。
本当は出来る限りNの値によらず高速に答えを求めたかったけど脳ミソが足りなかったから断念した。
他に挑戦された方の回答
こちらより。togetter.com
【スプラトゥーン】クイックボムと各メイン武器の確定数調整まとめ
リッター3Kのクイックボムに殴り殺されたイカは数知れず。
単体で使っても優秀だが、メイン武器と組み合わせることでさらに強くなる。
クイックボム直撃+メイン一発*1で倒すをコンセプトに、メインギアとクイックボムによる確定数調整についてまとめてみる。
クイックボムの基本性能
飛距離
他のボムと一緒。勿論サブ飛距離アップが乗る。
インク消費量
25%
満タンから4連続で投げることができる。
ダメージ
直撃 | 60.0 |
爆風 | 35.0 |
カス当たり | 20.0 |
直撃以外は殆どの場合35ダメージ。カス当たりは本当に端の方にかするように当たった場合。
ボム系はブラスターの爆風のように距離によって連続的にダメージが変化するのではなく、一定の範囲内は固定ダメージのようだ。
クイックボムをサブに持つ武器
武器 | メイン威力 | 最大威力 | 最大威力までのギア数(メイン.サブ) |
---|---|---|---|
シャープマーカー・ネオ | 26.0 | 33.3(推定) | 3.3以上 |
ジェットスイーパーカスタム | 31.0 | 33.3 | 0.3 |
スプラシューター | 36.0 | 49.9(推定) | 3.3以上 |
リッター3K・スコープ*2 | 40.0 | 上限値不明 | 3.3以上*3 |
カーボンローラー*4 | 25.0 | 上限値不明 | 3.3以上*5 |
本題からはそれるが、リッター3Kのノンチャージ時の確定数が攻撃力アップギアで上げれるのは意外だ。
ノンチャージだとそれなりの連射力なので、凸スナするなら攻撃力アップガン積みも有りかもしれない。
クイックボム直撃+メイン一発で倒すために必要な攻撃力アップギア
武器 | ギア数(メイン.サブ) | クイックボムダメージ | メインダメージ | 合計ダメージ |
シャープマーカー・ネオ | 2.0 | 69.9 | 30.3 | 100.2 |
ジェットスイーパーカスタム | 1.1 | 66.9 | 33.3 | 100.2 |
スプラシューター | 0.2 | 63.3 | 38.0 | 101.4*6 |
リッター3K・スコープ | 0.0 | 60.0 | 40.0 | 100.0 |
カーボンローラー | 2.1 | 71.0 | 29.6 | 100.7 |
まとめ
結論を先に言うと、今回のコンセプトを一番活かせるのはジェットスイーパーカスタムだ。
元々のメイン武器の連射力が低いため、確定数を調整することで相手を倒すスピードが格段に上がる。
シャープマーカー・ネオは必要なギアが少し多く元の連射速度もかなり早いためメリットが薄く感じるかもしれないが、やはり体感できるレベルで相手を倒しやすい。
スプラシューターは試してないけど多分同様。
こっちのほうが必要なギアがかなり少ないので余裕があるならつけておくといいと思う。
逆に、リッター3Kやカーボンローラーはメインの攻撃性能的にメリットが薄いかもしれない。