AtCoder ABC4か月目参戦日記

スポンサーリンク
ブログ
スポンサーリンク

AtCoderに初めて参加したのが6月25日なので約4カ月経ちました。今回の『AtCoder Beginner Contest 275』は時間内にはA問題とB問題の2問しか解けませんでしたが、答えを見て、あらためて自力でC問題とD問題を解きなおしてみます。

C – Counting Squares

問題

[考察]
平面図形にできる正方形の数を数える問題。辺が斜めのものもあり、パターンを考えたが、多すぎてコードに落とし込むことができなかった。kyopro_friendsさんの解説を見て、左上と右上の2点が決まれば、他の2点が決まることを利用しました。for文でネストして左上を決めて、そのあと、右上を同じように探索して、2点を決めた後、左下と右下の2点が9×9の座標からはみ出さないことを確認してから、左下と右下の2点に相当する座標にポーンがあるか確認し、あればカウンターを+1して、全部の正方形をカウントしました。4重ループは不格好だけど。。。

from sys import stdin
input = stdin.readline

s = [""]*9
for i in range(9):
    s[i] = input().rstrip()

cnt = 0
for x in range(8):
    for y in range(8):
        if s[x][y] == "#":
            for x1 in range(x,9):
                for y1 in range(y+1,9):
                    if s[x1][y1] == "#":
                        dx = x1-x
                        dy = y1-y
                        if (y-dx >= 0) & (x+dy+dx <= 8):
                            if (s[x+dy][y-dx] == "#") & (s[x1+dy][y1-dx] == "#"):
                                cnt += 1
print(cnt)

D – Yet Another Recursive Function

問題

[考察]
普通に再帰関数で書いたら、当たり前のようにTLE!解説を見たら「メモ化再帰」と聞いたことがない用語があり、知識問題か~とぼやいたのですが、よくよく考えたら、メモ化再帰のライブラリを知らなくてもメモ化を自分で実装してやればいいだけなんですね。辞書型に計算結果を入れてやって、再利用できるようにしてやると、何と2208msのTLEが、たったの24msとは!辞書型の処理の速さのポテンシャルを目の当たりにした問題でした。※メモ化再帰はAtCoderには基礎的な要素みたいなので、そちらはそちらで勉強しておきます。。。

from sys import stdin

input = stdin.readline

n = int(input())
memo_dic = {0:1}

def func(i):
    if i in memo_dic:
        return memo_dic[i]
    else:
        memo_dic[i] = func(i//2)+func(i//3)
        return memo_dic[i]

print(func(n))

終わりに

AtCoderも参加して4カ月。緑色に上がることを目標にやっています。とはいえ、最近、勉強が出てきおらず成績も伸び悩んでいます。毎週参加して、直しをするだけは難しそうなので、しっかり4完できるように基礎も固めて、年末に向けて、Ratingを向上させたいものです。

ブログ
スポンサーリンク
鷹の目週末プログラマー

コメント