水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

AGC004 参加記録

久々にコンテスト出たけど全然ダメ。1完。

AtCoder Grand Contest 004 - AtCoder Grand Contest 004 | AtCoder




A問題

A: Divide a Cuboid - AtCoder Grand Contest 004 | AtCoder

立方体を切って綺麗に整数値の立方体ができるということは、縦横高さの2つを固定した状態で固定してない面を半分に切れば良い。ただし半分に綺麗に切れるとは限らないので、片方は切り上げ、片方は切り捨てて計算する。この差分をとったものが答えになる。なお、一つでも偶数の値があれば綺麗に2等分できるため、答えは0になるが、まあチェックがめんどくさかったのでやってません。

import math

def solve():
    a, b, c = map(int, input().split())
    mindiff = 10 ** 27
    mindiff = min(mindiff, math.ceil(a/2) * b * c - math.floor(a/2) * b * c)
    mindiff = min(mindiff, math.ceil(b/2) * a * c - math.floor(b/2) * a * c)
    mindiff = min(mindiff, math.ceil(c/2) * b * a - math.floor(c/2) * b * a)
    print(mindiff)

if __name__=="__main__":
    solve()

Code: Python3
Submission #865637 - AtCoder Grand Contest 004 | AtCoder

この問題に15分かけているようではいつまでも初心者って感じですね… せいぜい10分くらいで解きたい。(最初方針を間違えて3重ループくらい回して首を傾げていたのが良くない)

B問題

B: Colorful Slimes - AtCoder Grand Contest 004 | AtCoder

進化回数を固定して、どんどん最小値の合計を更新していけば良い。進化回数を固定する方針を間違え、最小値の決定を1度しか行わなかった結果、WAが無限に取れなかった。多分、実装より考察フェーズのほうが難しい問題。

def solve():
    n, x = map(int, input().split())
    al = [int(i) for i in input().split()]
    bi = [i for i in al]
    ans = sum(al)
    for k in range(1, n):
        bi = [min(bi[i-1], al[i]) for i in range(n)]
        ans = min(ans, k * x + sum(bi))
    print(ans)

if __name__=="__main__":
    solve()

Code: Python3
Submission #870429 - AtCoder Grand Contest 004 | AtCoder


間違っている方針をここまでやったからきっとあっているだろうという理論は時に失敗を生むんだなあ(値を更新する方針は思いついたのにAC出来なかったため反省)


コンテストに出なさすぎて感が鈍っている感じがすごいので、参加したコンテストについては振り返りと解けなかった問題1問を解くように習慣づけていきたいと思います。


この前のCodeForcesの振り返りもしなきゃ