0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

はじめに

2完どまりになってしまった。厳しい。

成績:AB2完(250)

A

1と0のセットがn個あって最後に1がついていると解釈する。

A
n = int(input())
print("10"*n + "1")

B

問題を理解するのに時間がかかってしまった。
n-1番目がなくなるまでn番目に変換し、n-1番目がなくなったらn-2番目にさかのぼって補充して……と考えていたが提出してみるとTLEだった(WAも2個あったし)

B-TLE
n = int(input())
A = list(map(int, input().split()))
ex = []
for i in range(n-1):
    s,t = map(int,input().split())
    ex.append([s,t])
while A[0] >= ex[0][0]:
    for i in range(n-2,-1,-1):
        if A[i] >= ex[i][0]:
            A[i] -= ex[i][0]
            A[i+1] += ex[i][1]
            break
print(A[-1])

じゃあどうすんねん!と一瞬思ったが、前から変換できるだけ変換していけばいいことにすぐ気づいた。

B-AC
n = int(input())
A = list(map(int, input().split()))
ex = []
for i in range(n-1):
    s,t = map(int,input().split())
    ex.append([s,t])
for i in range(n-1):
    sho = A[i]//ex[i][0]
    A[i+1] += ex[i][1]*sho
print(A[-1])

前回のBは言われたとおりにやればできたのでその感じでやってしまった(なんで前回のBが200点でこれ150点なんだよ)。
これで30分かけたのが敗因1。

C

問題を見たときの印象は「全探索しかなさそうだけど間に合わなさそ~~」だった。計算量が$O(HWN)$で、最大$1.25\times10^8$なので無理だろうと考えてしまった。
しかし高速化の方法が全然思いつかない(端のマスを探索しないとかあるが焼け石に水だろうし)のでとりあえず全探索で実装しようとしたが、ミスを連発して心が折れてしまい時間切れに。

正解は全探索だったので終了後実装してみた。

C
h, w, n = map(int, input().split()) 
t = input()
route = [[0,0]]
for i in t:
    if i == "L":
        route.append([-1,0])
    if i == "U":
        route.append([0,-1])
    if i == "R":
        route.append([1,0])
    if i == "D":
        route.append([0,1])
grid = []
for i in range(h):
    grid.append(input())
cnt = 0
for i in range(w): #スタート地点のx座標を0からw-1まで動かす。
    for j in range(h): #スタート地点のy座標を0からh-1まで動かす。
        x = i
        y = j
        for k in range(len(route)):
            x += route[k][0]
            y += route[k][1]
            if w-1 >= x >= 0 and h-1 >= y >= 0 and grid[y][x] == ".":
                pass
            else:
                break
        else:
            cnt += 1
print(cnt)

とりあえず入力例1と2が合ったのでどんなもんかなと投げてみたら860 msでACでした。結構余裕あんのかい!!
$10^8$くらいでも全然通るんですね。勉強になりました。というか全探索だと思ったならとりあえずやってみればいいわけで、こういうのをスッと実装して投げてみるというのを速くできないと今後きつそう。

前回は新しいアルゴリズムを身に着けたいな~とか思っていたが、まず実装を速くできるようにしていくのが先決に思えてきた。少しずつでもやっていきましょう。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?