れんしゅうちょう。

52位	23pt	50:51
問題	Small	Large
A	10:31	10:59
B	42:51 誤答2回	-
C	-	-
D	誤答1回	-
E	-	-

Tシャツ圏内なものの、まぁ非常に反省点の多い感じでした。

以下ソースとか。

A→B→D→B-LargeとD解こうと頑張る

まずA。

問題文読むのが面倒だった。

絵でも入れてくれれば解りやすいのにとか思ったけれど、考えてみれば日本語なだけ相当マシ。

問題文さえ読めれば、明らかにabsin(∠ACB)みたいなアレ使うのは目に見えてるし、全部角度が同じなので、隣り合う棒の長さの積の和を最大化しろ見たいな感じ。

まぁ感覚的に、長いのの隣に長いの持ってきた方がいいので、

531246みたいな感じの並びになる。

k = geti
es = getia
es.sort!.reverse!
a = [es[0]]
es.shift
f = true#front
res = 0
until es.empty?
    x = es.shift
    if f
        f = false
        res += a[0] * x
        a.unshift x
    else
        f = true
        res += a[-1]*x
        a.push x
    end
end
res += a[0]*a[-1]
res*Math.sin(2*3.14159365/k)/2

わざわざ列を作り直す必要があったのかとか、色々疑問だけど、まぁ解りやすいというかバグ入らないようにと。

最初360.0/kにしてたり、/2忘れてたり、res+=a[0]*a[-1]忘れてたりしたので、解法思い付いてから提出するまでの時間が酷かったように思う。

それでも一瞬2位になれて、テンション上がった。

次にB

Bに来た時に他の問題にも目をちらっと通して、C解らん、Dはsmallなら実装ゲー、E解らんという所まで確認しておいた。

A**A%m==powMod(A,A,m)

(A**A)**(A**A)==powMod(powMod(A,A,m),powMod(A,A,m),m)

だと思ったら、sampleの最後通らなかった。

sampleがおかしいのかと思って提出したら爆死。もう一回提出して爆死。

原因がわかって死にたいとか思いながらLarge考えていたら、

a**Φ(m)==1(mod m)みたいなのを思い出すけど、gcd(a,m)=1の時しか成り立たないのも思い出して、Large無理ゲーじゃないかと思う。

しょうがないのでsmallをｶｶｯとゴリ押してDへ。

a,b,c = getia
b.times do |i|
    if i == b-1
        a = modpow(a, a, c)
    else
        a = a**a
    end
end
a%c

Dは、smallはただ探索で行けて、Largeは列ごとに考えるんだろうなーとは解っていたものの、Largeの列ごとを出来る気はしなかったので、とりあえずsmallを通すべく頑張る。

sampleは合ったものの、small通らず死亡。こうなると、間違えてる場所が全然解らない。BとDを行ったり来たりしながら唸ってた。

def inRange(x, y, maxx, maxy)
    0<=x&&x<maxx&&0<=y&&y<maxy
end
def can_go?(arr)
    x=arr.size
    y=arr[0].size
    dx = [-1, 0 , 1, 0]
    dy = [0, -1,  0, 1]
    loop do
        tmp = arr.dcopy
        for i in 0...arr.size
            for j in 0...arr[0].size
                if arr[i][j] == 'D'
                    for dir in 0...4
                        nx = i + dx[dir]
                        ny = j + dy[dir]
                        if inRange(nx,ny,x,y) && (arr[nx][ny]=='.'||arr[nx][ny]=='c')
                            arr[nx][ny]='D'
                        end
                    end
                end
            end
        end
        if tmp == arr
            break
        end
    end
    for i in 0...arr.size
        for j in 0...arr[0].size
            if arr[i][j] == 'c'
                return false
            end
        end
    end
    return true
end
def aki?(arr, x, y)
    arr[x][y]=='.'
end
def akidoor(arr, x, y)
    arr[x][y]=='.'||arr[x][y]=='c'||arr[x][y]=='D'
end
def can_set(arr, x, y, dir)
    if dir == 0 || dir == 3
        return false unless inRange(x,y,arr.length, arr[0].length)&&aki?(arr,x,y)
    else
        return false unless inRange(x,y,arr.length, arr[0].length)&&akidoor(arr,x,y)
    end
    if dir == 0
        if inRange(x,y+1,arr.length, arr[0].length)&&aki?(arr,x,y+1) &&inRange(x+1,y,arr.length, arr[0].length)&&akidoor(arr,x+1,y)
            return true
        else
            return false
        end
    elsif dir == 1
        if inRange(x+1,y-1,arr.length, arr[0].length)&&aki?(arr,x+1,y-1) &&inRange(x+1,y,arr.length, arr[0].length)&&aki?(arr,x+1,y)
            return true
        else
            return false
        end
    elsif dir == 2
        if inRange(x,y+1,arr.length, arr[0].length)&&aki?(arr,x,y+1) &&inRange(x+1,y+1,arr.length, arr[0].length)&&aki?(arr,x+1,y+1)
            return true
        else
            return false
        end
    elsif dir == 3
        if inRange(x+1,y,arr.length, arr[0].length)&&aki?(arr,x+1,y) &&inRange(x+1,y+1,arr.length, arr[0].length)&&akidoor(arr,x+1,y+1)
            return true
        else
            return false
        end
    end
end

def set(arr, x, y, dir)
    if dir == 0
        arr[x][y] = 'C'
        arr[x][y+1] = 'C'
        arr[x+1][y] = 'c' unless arr[x+1][y] == 'D'
    elsif dir == 1
        arr[x][y] = 'c' unless arr[x][y] == 'D'
        arr[x+1][y-1] = 'C'
        arr[x+1][y] = 'C'
    elsif dir == 2
        arr[x][y] = 'c' unless arr[x][y] == 'D'
        arr[x][y+1] = 'C'
        arr[x+1][y+1] = 'C'
    elsif dir == 3
        arr[x][y] = 'C'
        arr[x+1][y] = 'C'
        arr[x+1][y+1] = 'c' unless arr[x+1][y+1] == 'D'
    end
    arr
end
def search(arr, x, y, now)
    y += 1
    unless inRange(x,y,arr.length,arr[0].length)
        y = 0
        x += 1
        unless inRange(x,y,arr.length,arr[0].length)
            return now
        end
    end
    res = search(arr.dcopy, x, y, now)
    for dir in 0...4
        if can_set(arr, x, y, dir)
            nextarr = set(arr.dcopy, x, y, dir)
            if can_go?(nextarr.dcopy)
                res = [search(nextarr, x, y, now+1), res].max
            end
        end
    end
    res
end

    h,w = getia
    arr = []
    h.times do
        arr << gets.chomp
    end
    search(arr, 0, -1, 0)

終わってから、通ってる人のソース使った出力とdiff取ってみると原因が解った。

最適解で

....
..XC
.CCC
....

が出てくるケースで、両方ともXの場所を基準にして置いているので、これを作れなくなっていた。

def search(arr, x, y, now, flg=true)
    if flg
        y += 1
        unless inRange(x,y,arr.length,arr[0].length)
            y = 0
            x += 1
            unless inRange(x,y,arr.length,arr[0].length)
                return now
            end
        end
    end
    res = search(arr.dcopy, x, y, now)
    for dir in 0...4
        if can_set(arr, x, y, dir)
            nextarr = set(arr.dcopy, x, y, dir)
            if can_go?(nextarr.dcopy)
                res = [search(nextarr, x, y, now+1, false), res].max
            end
        end
    end
    res
end

としたら通った。

つまり、置ける→次の探索で場所を変更しない。

当然考えなければならない事だったハズなのに、全く思い付かなかった。

猛省すべき。

あと、C-smallも思い付いて良かったハズ。

ちゃんと取り組まなかったのは良くない。

うなったりTwitter見てる暇あったら考えろという。

ツイートする