自分用メモ

プログラミングとかのメモを書きたいです

競プロ典型 90 問:044 - Shift and Swapping(★3)

問題

atcoder.jp

挑戦結果

  • 挑戦日:2021/10/17
  • 結果:解けた
  • 時間:10分

考えたこと

  • T1とT3はやるだけ。
  • T2は右シフトを愚直に実装するとTLEしそう。N=10^ 5, Q=10^ 5 なので、シフトに N、クエリ数がQだと 10^{10}でまずそう。
  • シフトの代わりに基準にする場所を持っておいて、T2のときに基準をずらせば良さそう。T1とT3はその基準からの相対位置でやる。

公式解説

https://twitter.com/e869120/status/1395148057730187265

解説を読んだふりかえり

  • 特に問題なかった

ソース

N,Q = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
# シフトは重いので、代わりに基準の場所を決めておく
d = 0
for _ in range(Q):
    T,x,y = [int(x) for x in input().split()]
    # 基準と0-indexの調整
    x = (x -1 + d) % N
    y = (y -1 + d) % N
    if T==1:
        # 入れ替える
        A[x], A[y] = A[y], A[x] 
    elif T==2:
        # シフトの代わりに基準をずらす
        d+=(N-1)
    elif T==3:
        print(A[x])

競プロ典型 90 問:043 - Maze Challenge with Lack of Sleep(★4)

問題

atcoder.jp

挑戦結果

  • 挑戦日:2021/10/17
  • 結果:解けなかった
  • 時間:1時間ぐらい

考えたこと

  • 方向を変えた数なので、単純な最短経路ではなさそう。
  • といっても、QueueをもってBFSをやって、方向転換した数が少ないものから展開していけば良さそう
  • なにか実装が悪いのか、WAしたりTLEしたり・・・。

公式解説

https://twitter.com/e869120/status/1394787605099601923/photo/1

解説を読んだふりかえり

  • 考え方は間違っていなさそうだけど、拡張BFSとかの概念は持っていなかった。
  • TLEとかWAが取れなくてずっと悩んでいて、別の正解例を見て気がついたけど、 pythonのdequeのpop()は、左からpopすることに気がついていなかった・・・。popleft()にしたらACした。

ソース

from collections import deque
H,W = [int(x) for x in input().split()]
rs, cs = [int(x)-1 for x in input().split()]
rt, ct = [int(x)-1 for x in input().split()]
S = [input() for _ in range(H)]

# A[r][c]は、(r,c)にたどり着くまでの曲がった回数
INF = float("inf")
A = [[INF] * W for _ in range(H)]

# 探索済(開始地点は-1にしておく)
A[rs][cs] = -1

# BFS用にこれから探索する場所をキューに入れる(
openpos = deque()
openpos.append((rs,cs))

# キューの頭から展開していく
while (len(openpos) != 0):
    p = openpos.popleft()
    r, c = p[0], p[1]
    cnt = A[r][c] + 1
    # 上下左右
    D = [(-1,0), (+1,0), (0,-1), (0,+1)]
    for d in D:
        rr = r
        cc = c
        while True:
            rr += d[0]
            cc += d[1]
            # 道であり、まだ未探索ならそこから探索できるようにキューに足す。
            if (0<=rr<H) and (0<=cc<W):
                if S[rr][cc] == "." and A[rr][cc]>A[r][c]:
                    A[rr][cc] = cnt
                    openpos.append((rr,cc))
                else:
                    break
            else:
                break

# 開始地点は0に戻しておく
A[rs][cs] = 0
print(A[rt][ct])

競プロ典型 90 問:042 - Multiple of 9(★4)

問題

atcoder.jp

挑戦結果

  • 挑戦日:2021/10/15
  • 結果:解けなかった
  • 時間:30分

考えたこと

  • DPっぽい
  • 一文字足して行く感じ

公式解説

https://twitter.com/e869120/status/1394423616805097477

解説を読んだふりかえり

メモ化再帰で書いてみた

  • 個人的にDPよりも再帰のほうがわかりやすいので、再帰で書いてみた
  • スルッとかけたけど、sys.setrecursionlimit(10**6) をつけ忘れて REが取れなかった。
  • Windows環境で実行すると、99999 とか5桁規模を入力すると、原因不明だけど無言で終了する。何も出力してくれないし、エラーにもならない。
  • AtCoder環境だと問題ないようで、AC。

ソース

import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)
K = int(input())
MOD = 10**9 + 7

# メモ化再帰
@lru_cache(maxsize=1000000)
def f(n):
    # 終了条件
    if n==0:
        return 1
    ret = 0
    # f(n-1), ... f(n-9)の合計
    for i in range(max(n-9,0), n):
        ret += f(i)
        ret %= MOD
    return ret

ans = f(K) if K%9==0 else 0
print(ans)

追記@20211017

DP版も書いてみた。

個人的には再帰のほうが理解しやすいな。。。 でも、DPのほうが速度が早いし、Python再帰数設定だとか無言で終了するような挙動もあるし、競プロでは重要スキルな気がしてる。DP力をつけねば。

K = int(input())
DP = [0] * (K+1)
DP[0] = 1
MOD = 10**9 + 7
for i in range(1,K+1):
    st = max(0, i-9)
    DP[i] = sum(DP[st:i])
    DP[i] %= MOD
print(DP[K] if K%9==0 else 0)

競プロ典型90問:038 - Large LCM(★3)

問題

atcoder.jp

挑戦結果

  • 挑戦日:2021/10/14
  • 結果:解けた
  • 時間:3分

考えたこと

  • pythonに最大公約数のライブラリは入っていて、そこから最小公倍数も求められる。
  • 最小公倍数のスニペットも以前作ったことあった気がするから、発掘。

公式解説

https://twitter.com/e869120/status/1392612322410057729

解説を読んだふりかえり

  • C言語とかだと、オーバーフロー対応が必要なもよう。Pythonでよかった。

ソース

import math
# 最小公倍数(least common multiple)
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A,B = [int(x) for x in input().split()]
ans = lcm(A,B)

print(ans if ans <= pow(10,18) else "Large")

競プロ典型90問:034 - There are few types of elements(★4)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_ah

挑戦結果

  • 挑戦日:2021/10/08
  • 結果:解けた
  • 時間:30分ぐらい

考えたこと

  • しゃくとり法のように構成すれば良さそう
  • 現在見ている左部分(l)と右部分(r)の座標を保持する。
  • 登場した数字の個数はdictでカウントする
    • 最初setで数字が登場したかだけで判定しておりWAだった。
  • 進め方
    • K個以下の場合:rを右にすすめる。(もっと増える可能性あり)
    • K個以上の場合:lをすすめる。

公式解説

解説を読んだふりかえり

  • 想定通りだったので、特に話。
  • 「最初に座標圧縮を行う場合」というのはなんのことかわからなかった。。。

ソース

N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

l = -1
r = -1

s = dict()
mm = 0
while l<N:
    if len(s)<=K and r<N:
        mm = max(mm, r-l)
        r+=1
        if r<N:
            s[A[r]] = s.get(A[r],0) + 1
    else:
        l+=1
        if l<N:
            s[A[l]] = s.get(A[l],0) - 1
            if s[A[l]] == 0:
                s.pop(A[l])

print(mm)

競プロ典型90問:033 - Not Too Bright(★2)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_ag

挑戦結果

  • 挑戦日:2021/10/08
  • 結果:解けなかった
  • 時間:20分

考えたこと

  • 左上原点としたら、各2x2のマスの左上を点灯させるだけ
  • 1行分を考えると$(W+1)//2$、1列分を考えると、$(H+1)//2$ で、これらをかければOK
  • 一瞬で解けたと思った。

公式解説

解説を読んだふりかえり

  • WAがでた。ケース名がcornerがWAなので、コーナーケースで間違ってる事はわかった。
  • コーナーケースが見つけられずに、解説をみた。★2なのに解けなかった・・・。解説のポイントが「コーナーケース」だったので、まんまとやられた。

ソース

H, W = [int(x) for x in input().split()]
a = (W + 1) //2
b = (H + 1) //2

if H==1 or W==1:
    print(max(H,W))
else:
    print(a*b)

競プロ典型90問:032 - AtCoder Ekiden(★3)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_af

挑戦結果

  • 挑戦日:2021/10/07
  • 結果:解けた
  • 時間:20分ぐらい

考えたこと

  • 全探索できそう。$10! = 3.6 * 106$
  • 順番の全列挙はpythonのライブラリにあったはず

公式解説

解説を読んだふりかえり

  • pythonで投げたらTLEした。pypy3でAC。
  • 方向性は問題なかった。
  • 読者への課題のN<=18でも解けるアルゴリズムってなんだろう・・・。

ソース

from itertools import permutations

N = int(input())
A = []
for i in range(N):
    a = [int(x) for x in input().split()]
    A.append(a)

M = int(input())
# 嫌い合ってるペアをセットで持つ
P = set()
for _ in range(M):
    x,y = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    P.add((x,y))
    P.add((y,x))

# 0~N-1 までの順番の全パターン
LL = permutations(range(N))

INF = float('inf')
ans = INF
# すべてのパターンから最短を探す
for L in LL:
    length = 0
    for i in range(N):
        if i+1<N and (L[i],L[i+1]) in P:
            length = INF
            break
        else:
            length += A[L[i]][i]
    ans = min(ans, length)

print(ans if ans < INF else -1)