今日の精進(20200112)

一応昨日のARCにも参加したんですが1ACだし早く解いただけなので記事にはしない。ちなみに今日のABCは3完2WAとかでした。典型ができないのだめすぎるな…
今日は深さ優先をメインでやった

Big Array

aをソートして、前から順番にbiだけKを減らしていく。bi >= Kとなったらそのaiを出力する。

# coding: utf-8  
n, k = map(int, input().split())  
l = []  
ll = []  
for i in range(n):  
    a, b = map(int, input().split())  
    l.append(b)  
    ll.append([a, b])  
ll.sort(key=lambda x: x[0])  
for i in range(n):  
    if k <= ll[i][1]:  
        print(ll[i][0])  
        break  
    k -= ll[i][1]  

4/N

制約的に$N^3$は、間に合わない。そこで、hとnを決めればwも決まるので、これによって$N^2$となり十分間に合う。そのまま等式を突っ込むとやたら時間がかかったので式は多少変形した。

# coding: utf-8  
N = int(input())  
for h in range(1, 3501)[::-1]:  
    for n in range(1, 3501)[::-1]:  
        if 4*h*n-N*(h+n) == 0:  
            continue  
        w = (N*(h*n)) / (4*h*n-N*(h+n))  
        if w != int(w) or w <= 0:  
            continue  
        w = int(w)  
        if 4/N == (n*w+h*w+h*n)/(h*n*w):# and 1 <= h <= 3500 and 1 <= n <= 3500 and 1 <= w <= 3500:  
            print(h, n, w)  
            exit()  

埋め立て

深さ優先でやっていくのだが、制約が10*10と小さいので、仮にどこか1つのマスも島になっていた
…を全部やり、どこかで渡り切れる場合はYES、そうでない場合はNO。自分で考えてうまくいったDFSは初めてなのでうれしい。sys.setrecursionlimitでREになるのを避ける。

# coding: utf-8  
import sys  
sys.setrecursionlimit(10**8)  
TF = [[False for _ in range(10)] for _ in range(10)]  
M = []  
for i in range(10):  
    tmp = list(input())  
    tmp = [0 if tmp[j]=="x" else 1 for j in range(10) ]  
    M.append(tmp[:])  

# print(*M, sep="\n")  
islands = sum([sum(M[i]) for i in range(10)]) + 1  
visited = [[False for _ in range(10)] for _ in range(10)]  
def dfs(i, j):  
    if sum([sum(visited[k]) for k in range(10)]) == sum([sum(M[k]) for k in range(10)]):  
        print("YES")  
        exit()  
    if i < 0 or j < 0 or i >= 10 or j >= 10 or visited[i][j] or M[i][j] == 0:  
        return  

    visited[i][j] = True  
    dfs(i+1, j)  
    dfs(i-1, j)  
    dfs(i, j+1)  
    dfs(i, j-1)  

for x in range(10):  
    for y in range(10):  
        if M[x][y] == 1:  
            continue  
        visited = [[False for _ in range(10)] for _ in range(10)]  
        M[x][y] = 1  
        dfs(x, y)  
        M[x][y] = 0  
print("NO")