8/26夏休み基礎力強化プロジェクト14日目

[idekazuki]

from collections import OrderedDict についてhttps://note.nkmk.me/python-collections-ordereddict/ 簡単に言うと順番を保持する辞書型。dictのサブクラス。

https://github.com/TwentyBN/GulpIO/blob/master/src/main/python/gulpio/fileio.py starter kitの解析 xxx.gulp_dir.merged_meta_dict[id]で [offset, padding, length]を返してくれる。offsetは先頭からのバイト数を表し、lengthはgulpチャンク内のjpegの長さを表す。paddingはよくわからんかった。

optical flowに関しては、u,vに分離して動画表示を行う関数が定義されていた。uは水平方向のoptical flowで、vは垂直方向のoptical flowを表している。

def grey_to_rgb(frames):
    """
    Convert frame(s) from gray (2D array) to RGB (3D array)
    """
    n_channels = 3
    return np.repeat(np.array(frames)[..., np.newaxis], n_channels, axis=-1)

def stitch_flow_uv_frames(uv_frames, width_axis=2):
    """
    Destack (u, v) frames and concatenate them side by side for display purposes
    """
    u_frames = np.array(uv_frames[::2])
    v_frames = np.array(uv_frames[1::2])
    stacked_frames = np.concatenate((u_frames, v_frames), axis=width_axis)
    return stacked_frames

def clipify_flow(frames, fps=30):
    """
    Destack flow frames, join them side by side and then create an ImageSequenceClip
    for display
    """
    frames = grey_to_rgb(stitch_flow_uv_frames(list(map(np.array, frames))))
    segment_clip = ImageSequenceClip(list(frames), fps=fps)
    return segment_clip

example_segment = flow_train.video_segments[10]
# Note you can also pass an iterable of frame indices to extract, this is useful for
# methods like TSN which only need a few frames
example_flow_frames =  flow_train.load_frames(example_segment, range(0, example_segment.num_frames))
clipify_flow(example_flow_frames).ipython_display()

[idekazuki]

B - Kleene Inversion 今回はめちゃくちゃ時間を取られた。 アルゴリズム自体はすぐに分かったが、計算量が大きいので途中でoverflowを起こしたとかんがえられる。 適宜 % 10**9 + 7を挟めるところで挟むことで数が大きくなりすぎるのを抑えることが必要だった。

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
MOD = 10**9 + 7

bl1 = A[:,None] > A[None,:]
bl2 = np.arange(N,dtype=np.int64)[:,None]
bl3 = np.arange(N,dtype=np.int64)[None,:]
mask = bl2[None] < bl3[None]
mask = bl1 & mask
ans1 = (mask*1).astype(np.int64).sum() % MOD
ans1 = ans1 * K % MOD

ans2 = (bl1 * 1).astype(np.int64).sum() % MOD
coe =int(K * (K - 1) // 2) % MOD
ans2 = ans2 * coe % MOD

print((ans1 + ans2) % MOD)

[idekazuki]

AizuOnlineJudge コイン問題 最初は記憶するための配列を用意していた。

N, M = map(int, input().split())
A = list(map(int, input().split()))
memory = [10**6 for _ in range(N + 1)]
flg = [False for _ in range(N + 1)]
memory[0] = 0
flg[0] = True
for a in A:
  m = 0
  while m < len(memory) and m + a < len(memory):
    if flg:
      memory[m + a] = min(memory[m] + 1, memory[m + a])
      flg[m + a] = True
    m += 1
print(memory[-1])

rate上位の人のコードはかなりスッキリしている

import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

#------------------------------------------#

BIG_NUM = 2000000000
HUGE_NUM = 9999999999999999
MOD = 1000000007
EPS = 0.000000001

#------------------------------------------#

W,N = map(int,input().split())

table = [BIG_NUM]*(W+1)

table[0] = 0

coin_list = list(map(int,input().split()))

for coin in coin_list:
    for i in range(coin,W+1):
        table[i] = min(table[i],table[i-coin]+1)

print("%d"%(table[W]))

[idekazuki]

0-1 ナップザック問題 ループを逆から回すことでメモリのコピーをする必要がなくなる。

N, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(W + 1)]

for a in A:
  for j in range(W, a[1] - 1, -1):
    dp[j] = max(dp[j], dp[j - a[1]] + a[0])
print(max(dp))

[idekazuki]

最長増加部分列 numpyでmaskを作成して計算を行った。

import numpy as np
N = int(input())
A = np.array([int(input()) for _ in range(N)])

mask1 = A[:, None] < A[None, :]
mask2 = np.arange(N)[:, None] >= np.arange(N)[None, :]
ans = ((mask1 | mask2) * 1).astype(np.int64)
ans = ((ans.sum(axis=1) == N) * 1).astype(np.int64)
print(ans.sum())

numpy をAOJで使用することができなかったので別の手法で実装。 問題は時間がかかること。二分探索にすることで計算時間を抑えた。

N = int(input())
A = [int(input()) for _ in range(N)]
INF = 10**10
memory = [INF for _ in range(N)]
ans = 0
def search(x):
  l = 0
  r = len(memory) - 1
  cp = (l + r) // 2
  while r - l >= 0:
    cp = (l + r) // 2
    if memory[cp] >= x:
      r = cp - 1
    else:
      l = cp + 1
  return l
ans = 0 
for a in A:
  point = search(a)
  memory[point] = a
  ans = max(ans, point)

print(ans + 1)

実装した後に気づいたが、numpyの使用はできないが、 from bisect import bisect_left as bl は使用可能であった。二分探索は実装する必要がなかった。

[idekazuki]

編集距離 これはアルゴリズムがわかっていないときつい https://takuti.me/note/levenshtein-distance/ 表を作成して現在地の値を上、左、左上の値をもとに計算。それぞれ削除、追加、置換の操作の編集距離を計算できる。

S1 = input()
S2 = input()
arr1 = [i for i in range(len(S1) + 1)]
arr2 = [1 for _ in range(len(S1) + 1)]

for i, s2 in enumerate(S2):
  arr2[0] = arr1[0] + 1
  for j in range(1, len(S1) + 1):
    if s2 == S1[j - 1]:
      cost = 0
    else:
      cost = 1

    arr2[j] = min(arr2[j - 1] + 1,
                  arr1[j] + 1,
                  arr1[j - 1] + cost)
  arr1, arr2 = arr2, arr1

print(arr1[-1])