SoundHound 2018 予選 D - Saving Snuuk
続きです。
ダイクストラな問題みたい。普通にわからんかったが。
editorial.pdfを見て実装してみる。
最後の出力が になってここがボトルネックになってTLEになっている。editorialにもここの処理書いてないやん。適当に検索したら、逆からやれば良いらしい。つよい。
""" 「sからiに円による支払いで移動する際の最小の金額」円と、「iからtにスヌークによる支払いで移動する際の最小金額」スヌークになる。これを最小化すれば良い。 """ from collections import defaultdict G1 = defaultdict(list); G2 = defaultdict(list) N, M, S, T = map(int, input().split()) S-=1; T-=1 for i in range(M): f, t , v1, v2 = map(int, input().split()) G1[f-1].append((t-1, v1)) G1[t-1].append((f-1, v1)) G2[f-1].append((t-1, v2)) G2[t-1].append((f-1, v2)) import queue push = queue.heappush pop = queue.heappop INF = 10**16 d1 = [INF]*N; d2 = [INF]*N def dijkstra(s, G, d): q = [] d[s] = 0 push(q, (0, s)) while q: cost, v = pop(q) # print(f'd[{v}] = {cost}') # 既に q から取り出したものの方が低い if d[v] < cost: continue for to, tmpcost in G[v]: if d[to] > d[v] + tmpcost: d[to] = d[v] + tmpcost push(q, (d[to], to)) dijkstra(S, G1, d1) dijkstra(T, G2, d2) """ for i in range(N): ans = 0 for j in range(i, N): ans = max(ans, 10**15-d1[j]-d2[j]) print(ans) """ anses = [0]*N ans = 10**15 for i in range(N): ans = min(ans, d1[N-1-i]+d2[N-1-i]) anses[N-1-i]=10**15-ans for i in range(N): print(anses[i])
すげ〜。今日もACした。 今日は週の始まりですね。今週も頑張りましょう！！！
単一始点最短路探索アルゴリズム(1)
こんにちは、えぬわいです(普通)
ダイクストラ法の復習です。
import queue push = queue.heappush pop = queue.heappop INF = 10000 from collections import defaultdict G = defaultdict(list) N, M, S, GOAL = map(int, input().split()) V = N d = [] for i in range(M): f, t, c = map(int, input().split()) G[f-1].append((t-1, c)) G[t-1].append((f-1, c)) def dijkstra(s): global d q = [] d = [INF] * V d[s] = 0 push(q, (0, s)) while q: cost, v = pop(q) print(f'd[{v}] = {cost}') if d[v] < cost: continue for to, tmpcost in G[v]: if d[to] > d[v] + tmpcost: d[to] = d[v] + tmpcost push(q, (d[to], to)) dijkstra(S-1) print(d[GOAL-1])
蟻本を参考にして書くとこんな感じ。 queueを使えるところっていうのがよくわかった。他の自分で考えたものでも使えそうな予感。 テストケース
8 10 1 8 1 2 2 1 3 5 2 3 4 2 4 6 3 4 2 4 7 1 2 6 10 6 7 3 6 8 5 7 8 9
% python dijkstra.py < testcase.txt d[0] = 0 d[1] = 2 d[2] = 5 d[3] = 7 d[3] = 8 d[6] = 8 d[5] = 11 d[5] = 12 d[7] = 16 d[7] = 17 16
おお〜。感慨深い。
ARC 041 D 辺彩色(2)
自分の中で、けものみちが熱いです。
続き。
難しいなぁと思いながら、解説は理解できたが、実装がわかんなかったので、実装例を見てみた。
お世話になってる kmjp さん！！！かっけー
pythonで書き直し。
from sys import exit, setrecursionlimit setrecursionlimit(100000) from collections import defaultdict E = defaultdict(list) # 辺の正しい色: C[i] == True なら C[i] は 'r' C = [0 for i in range(2020)] a = [0 for i in range(2020)] b = [0 for i in range(2020)] tar = [[0 for i in range(2020)] for j in range(2020)] # vis は辺の番号 vis = [0 for i in range(2020)] length = [0 for i in range(2020)] # 辺 N, M = map(int, input().split()) for i in range(M): *tmp, s = input().split() a[i], b[i] = map(int, tmp) a[i] -= 1; b[i] -= 1 # 辺の入力 E[a[i]].append(b[i]) E[b[i]].append(a[i]) # tar には、その辺が、何番目の辺であるかを入れておく tar[a[i]][b[i]] = i tar[b[i]][a[i]] = i C[i] = s == 'r' def dfs(pos, color, l): global vis, length # pos に訪れていないか 訪れていなかったら、 if length[pos] < 0: length[pos] = l # すでに訪れたことがある、つまり、閉路であり、その長さが奇数だったら elif abs(l-length[pos])%2: print('Yes') exit() # 現在の頂点から伸びてる辺でイテレーション for to in E[pos]: # 辺の番号の取得 num = tar[pos][to] if vis[num]: continue # 正しい辺の色と塗る色が同じだった場合のみ、続ける if C[num] == color: vis[num] += 1 dfs(to, color^1, l+1) # 始点と色で全探索 for i in range(N): for j in range(2): # vis の初期化 for k in range(M): vis[k] = 0 # length はすべて負にしておく for k in range(N): length[k] = -1 # 始点 i, 色 j, 長さ 0 でスタート dfs(i, j, 0) if all([m != 0 for m in vis[:M]]): print('Yes') exit() else: print('No')
TLEった... だけど、テストケース見てみると、TLE以外はACしてる。まぁ、一応実装は、理解できたということで...(自分に甘い)
自分的ポイントとしては、
- 再帰関数内で、辺の番号を取得する || 辺の色にアクセスのために、入力の時に、あらかじめメモしておく。
- 閉路の長さは、再帰の最初の部分で、判定する。また、その初期化処理。
- 0, 1 反転(排他的論理和)
- 辺彩色のやり方
わかんない問題ほど、勉強になりますね
今のpythonの書き方は、ほぼ自己流なので、ちゃんと競プロのために、速度的に早い書き方を調べないとなと思ったえぬわいでした。
閉路探索
前回の記事で、解説みると、奇数長の閉路を探索する必要があることがわかった。 閉路の検出ってどうやるんだっけなぁって思って調べた。
わかりやすい。擬似コードも載ってる。確認する。
from collections import defaultdict G = defaultdict(list) N, M = map(int, input().split()) ACTIVE, NEW, FINISHED = (-1, 0, 1) state = [NEW for i in range(N)] for i in range(M): fr, to = map(int, input().split()) G[fr].append(to) # G[to].append(fr) def has_cyclic(pos): global state state[pos] = ACTIVE for to in G[pos]: if state[to] == ACTIVE: return True elif state[to] == NEW: if has_cyclic(to): return True state[pos] = FINISHED return False print(has_cyclic(0))
頂点 0 からの閉路を見ているけど、結合じゃなければ、頂点の状態がNEWのものを探索すればよい。全部探索してるから、O(|N|+|M|)になる。引数に長さを足せば、長さを求めることができる。
ARC 041 D 辺彩色(1)
続きをやっている。
普通にわかんなかったが？(半ギレ)
解答見る。
考察で、逆順に辿ると、上書きする機能がなくなる←天才か？
始点と最初の色で全探索。それプラス、奇数サイクルのことを考えるものらしい。
辺彩色のコードわからんとなってそれっぽいものを書いた。とりあえず、奇数サイクルを考えないもの。当然WAだが。初歩として。明日は、ACする。
import sys sys.setrecursionlimit(100000) from collections import defaultdict N, M = map(int, input().split()) G = defaultdict(list) C = [[0 for i in range(N)] for j in range(N)] T = [[0 for i in range(N)] for j in range(N)] E = [] for i in range(M): t, f, c = input().split() t = int(t) - 1 f = int(f) - 1 G[t].append(f); G[f].append(t) if c == 'r': T[f][t] = 1 T[t][f] = 1 else: T[f][t] = -1 T[t][f] = -1 E.append([t, f]) def rec(pos, c): global C ret = True for to in G[pos]: if C[pos][to] == 0: C[pos][to] = c C[to][pos] = c if C[pos][to] != T[pos][to]: return False ret &= rec(to, -c) return ret # 逆に辿っていく ans = False for i in range(N): for j in [1, -1]: for t, f in E: C[t][f] = 0 C[f][t] = 0 ans |= rec(i, j) print('Yes' if ans else 'No')
Nuxtでデータフェッチする
Nuxtで自前でapiサーバー建てつつ、コンポーネントのasyncDataでデータをフェッチするっていうのがやりたかった。
はじめに、プロジェクトディレクトリ直下に、apiというディレクトリを用意して、json用のルーティングを用意する。
// project/api/index.js const express = require('express'); // パッケージからのインポート const app = express(); app.get("/json", (req, res) => { res.json({ message: "Hello World!" }) }) module.exports = { path: '/api', handler: app }
フェッチするコンポーネント。
<template> <p>message: {{ message }}</p> </template> <script> export default { async asyncData ({ $axios }) { const data = await $axios.$get(`http://localhost:3000/api/json`) return data } } </script>
$getでURLにアクセスする。asyncDataでは、戻り値がthisに統合されるので注意する。
で、やっていけばいいかも。バックエンドの光が見えてきたかな？
Maximum-Cup 2018 C 嘘つきな天使たち
最近努力が足りていないえぬわいです。
続きです。
2 部グラフで解けた。塗った時の数を記録していけば、おk。連結であることが保証されていないので、その点は気をつけた。自分で考えてACできるとちょーきもちー。
from collections import defaultdict G = defaultdict(list) N = int(input()) for i in range(N): to = int(input()) G[i].append(to-1) G[to-1].append(i) C = [0 for i in range(N)] tmp = dict() tmp[1] = 0; tmp[-1] = 0 def rec(pos, color): global C C[pos] = color tmp[color] += 1 ans = True for to in G[pos]: if color == C[to]: return False elif C[to] == 0: ans &= rec(to, -color) return ans ans = 0 for i in range(N): tmp[1] = 0; tmp[-1] = 0 if C[i] == 0: if not rec(i, 1): print('-1') break ans += max(tmp[1], tmp[-1]) else: print(ans)
再帰の回数の設定忘れてたけど通った。
