名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

Saiko~ No Contesuto #03（かみぺコン3）に参加した

HackerRank Python Ruby C++ bash 競技プログラミング

かみぺさんのコンテストでした．3完．

www.hackerrank.com

解説はこの辺りにあるそうです．



Zig-Zag Step

問題

https://www.hackerrank.com/contests/camypapercon03/challenges/zig-zag-step

回答

本番のC++
https://www.hackerrank.com/contests/camypapercon03/challenges/zig-zag-step/submissions/code/4265169
短く書こうとして失敗したbash
https://www.hackerrank.com/contests/camypapercon03/challenges/zig-zag-step/submissions/code/4265902
140文字以内に入れようとして完全勝利したruby
Programming Problems and Competitions :: HackerRank


解説いわく，||X|-|Y||<=1 になるようなときPossible になるみたいですね．
本番は|x+y|<=1と|x-y|<=1 のどちらかになればOKと見ていました．一応カバーできている範囲は同じはずですが，解説読んだ時に少し不安になりました（数学忘れかけているので，範囲カバーで来てるかどうかがとっさに理解できなかった）

とりあえず解説読んだ後に書いたrubyのコードを以下には貼っておきます…．

gets.to_i.times do
    x,y=gets.split(" ").map(&:to_i)
    d=(x.abs-y.abs).abs
    puts (d<2)?"Possible":"Impossible"
end

Adventure Calendar Contesuto

問題

https://www.hackerrank.com/contests/camypapercon03/challenges/adventure-calendar-contesuto

回答

本番で書いたC++
https://www.hackerrank.com/contests/camypapercon03/challenges/adventure-calendar-contesuto/submissions/code/4265268
Ruby
https://www.hackerrank.com/contests/camypapercon03/challenges/adventure-calendar-contesuto/submissions/code/4266129
1行にしてツイートに利用したruby
https://www.hackerrank.com/contests/camypapercon03/challenges/adventure-calendar-contesuto/submissions/code/4266136

本番では一旦，配列に出てくる最大の値を，最大値にして，条件を満たしているかどうかをシミュレーションしつつ，二分探索で探しました．

結局，1からnまで max( ((a1+..+ai)/i).ceil ) で計算してこれの最大値を求めるだけで良いみたいです．二分探索自身がなかったから，こっちの回答のほうが良かったなと解説を見て思いました．ちょっと考察不足だったかも．

n=gets.to_i
a=gets.split(" ").map(&:to_i)
res,sum=0,0.0
for i in 0...n do
    sum+=a[i]
    res=[res, (sum/(i+1)).ceil].max
end
puts res

歯車と箱

問題

https://www.hackerrank.com/contests/camypapercon03/challenges/gear-and-box

回答

https://www.hackerrank.com/contests/camypapercon03/challenges/gear-and-box/submissions/code/4265438

屑は素因数分解をサボって多倍長で殴った．通った．ごめんなさい．

多倍長で殴る前の考察はあってた．
分子に大きい方半分，分母に小さい方半分固める．
で，本来の回答であれば，素因数分解した結果を記録しておき，最後に計算して戻す…

ということでしたが，結局大きめの素数だらけになってくると計算できねえなこれと思い，（逐次MOD取ればいいだけだと思うんですけど（名推理））結局多倍長で殴る方針へ．

通ってしまった… oh....

MOD = 1000000007

def gcd(a, b):
    if a < b:
        a,b = b,a
    while b > 0:
        r = a % b
        a,b = b,r
    return a

n = int(input())
arr = [int(i) for i in input().split()]
arr.sort()
numer = 1
denom = 1
for i in range(n//2):
    numer *= arr[i]
    denom *= arr[n-1-i]

divnum = gcd(numer, denom)
numer //= divnum;
numer %= MOD;
denom //= divnum;
denom %= MOD;
print(int(denom), int(numer))

ぐるぐるツアー

問題

https://www.hackerrank.com/contests/camypapercon03/challenges/guruguru-tour

とりあえず自分の実力では手も足も出ず．
近いところ行って，次に近いところを求めて… という感じでなんとかならないかなあと思ったものの，結局そこから改善ができませんでした．
そもそもの巡回セールスマン問題とか，ダイクストラとかの考え方を余り知らないので，勉強不足を実感したのでした．まる．



結構問題解けたので楽しかったです．
3問目の考察を結果的にサボる形になってしまったのは，申し訳なかったです…．