AtCoder ABC4か月目参戦日記

AtCoder

2022.10.302023.01.10

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

C – Counting Squares

問題

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

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))