const V: i32; fn dfs(v: i32, c: i32) -> bool { let color: Vec<i32> = Vec::new(); color[v] = c; for i in 0..G.len() { if color[G[v][i]] == c { return false; } if color[G[v][i]] == 0 && !dfs(G[v][i], -c) { return false; } } return true; } fn main() { for i in 0..V { if color[i] == 0 { if !dfs(i, 1) { println!("No"); } } } println!("Yes"); }
簡易的なデバッカー(python)
import sys def trace_calls(frame, event, arg): if event != 'call': return code = frame.f_code func_name = code.co_name print(f"\n 呼び出し: {func_name}() at line {frame.f_lineno} in {code.co_filename}") return trace_lines def trace_lines(frame, event, arg): if event != 'line': return lineno = frame.f_lineno filename = frame.f_code.co_filename local_vars = frame.f_locals print(f"- 実行中: line {lineno} in {filename}") print("変数:", local_vars) input("Enterキーで次の行へ...") return trace_lines sys.settrace(trace_calls) def test(): x = 5 y = 10 z = x + y print("結果:", z) test() sys.settrace(None)
$ python3 debugger.py
呼び出し: test() at line 24 in /home/vagrant/dev/algorithm/basic/python/debugger.py
– 実行中: line 25 in /home/vagrant/dev/algorithm/basic/python/debugger.py
変数: {}
Enterキーで次の行へ…
– 実行中: line 26 in /home/vagrant/dev/algorithm/basic/python/debugger.py
変数: {‘x’: 5}
Enterキーで次の行へ…
– 実行中: line 27 in /home/vagrant/dev/algorithm/basic/python/debugger.py
変数: {‘x’: 5, ‘y’: 10}
Enterキーで次の行へ…
– 実行中: line 28 in /home/vagrant/dev/algorithm/basic/python/debugger.py
変数: {‘x’: 5, ‘y’: 10, ‘z’: 15}
Enterキーで次の行へ…
結果: 15
rustでは実行時フックがない
use std::io::{self, Write}; fn pause() { print!("Enterキーで次のステップへ..."); io::stdout().flush().unwrap(); let _ = io::stdin().read_line(&mut String::new()); } fn main() { println!("📍 デバッグ開始"); let x = 5; println!("🔍 x = {}", x); pause(); let y = 10; println!("🔍 y = {}", y); pause(); let z = x + y; println!("🔍 z = x + y = {}", z); pause(); println!("✅ 結果: {}", z); }
グラフのDFS(深さ優先探索)
use std::collections::HashMap; use std::collections::VecDeque; fn dfs(graph: HashMap<&str, Vec<&str>>, start: &str) { let mut visited: Vec<&str> = Vec::new(); visited.push(start); for neighbor in graph.clone().get(start).unwrap() { if !visited.contains(&neighbor) { dfs(graph.clone(), neighbor); } } } fn main() { let mut graph: HashMap<&str, Vec<&str>> = HashMap::new(); graph.insert("A", vec!["B", "C"]); graph.insert("B", vec!["A", "D", "E"]); graph.insert("C", vec!["A", "F"]); graph.insert("D", vec!["B"]); graph.insert("E", vec!["B", "F"]); graph.insert("F", vec!["C", "E"]); println!("{:?}", graph); // bfs(graph, "A"); }
グラフのBFS(幅優先探索)
use std::collections::HashMap; use std::collections::VecDeque; fn bfs(graph: HashMap<&str, Vec<&str>>, start: &str) { let mut deque: VecDeque<&str> = VecDeque::new(); let mut visited: Vec<&str> = Vec::new(); deque.push_back(start); while !deque.is_empty() { let vertex = deque.pop_front().unwrap(); if !visited.contains(&vertex) { visited.push(vertex); if graph.get(vertex) != None { let vs = graph.get(vertex).unwrap(); for v in vs { // println!("{}", v); deque.push_back(v); } } } } } fn main() { let mut graph: HashMap<&str, Vec<&str>> = HashMap::new(); graph.insert("A", vec!["B", "C"]); graph.insert("B", vec!["A", "D", "E"]); graph.insert("C", vec!["A", "F"]); graph.insert("D", vec!["B"]); graph.insert("E", vec!["B", "F"]); graph.insert("F", vec!["C", "E"]); println!("{:?}", graph); bfs(graph, "A"); }
グラフ
#[derive(Debug)] struct Edge { to: i32, cost: i32, } fn main() { let V = 3; let E = 3; let matrix = [[0,1], [0,2], [1,2]]; let mut edges: Vec<Edge> = Vec::new(); for i in 0..E { let ed = Edge { to: matrix[i][0], cost: matrix[i][1]}; edges.push(ed); } println!("{:?}", edges); }
Expedition 2431
fn main() { let mut N = 4; // gas station num let P = 10; // initial gas let L = 25; // distance let mut A: Vec<i32> = vec![10, 14, 20, 21]; // gas station distance let mut B: Vec<i32> = vec![10, 5, 2, 4]; // gas volume supply A.push(L); B.push(0); N += 1; let que; // manage gas station let mut ans = 0; // num of gas supply let mut pos = 0; // position let mut tank = P; // gas volume for i in 0..N { let d = A[i] - pos; // distance while (tank - d < 0) { if que.empty() { que.push(-1); return; } tank += que.top(); que.pop(); ans += 1; } tank -= d; pos = A[i]; que.push(B[i]); } println!("{}", ans); }
priority queはstackで大きい順に値を入れていく。
heapのpushとpop
fn push(x: i32) { let mut heap = [1, 2, 3, 4, 5, 6, 7, 8]; let sz = 0; let mut i = sz + 1; while(i > 0) { let p = (i -1) / 2; if heap[p] <= x { break; } heap[i] = heap[p]; i = p; } heap[i] = x; } fn pop() { let mut heap = [1, 2, 3, 4, 5, 6, 7, 8]; let sz = 0; let ret = heap[0]; let x = heap[heap.len() -1]; let mut i = 0; while(i * 2 + 1 < sz) { let mut a = i * 2 + 1; let mut b = i * 2 + 2; if (b < sz && heap[b] < heap[a]) { a = b; } if (heap[a] >= x) { break; } heap[i] = heap[a]; i = a; } heap[i] = x; }
dynamic programing
use std::collections::HashMap; fn rec (i: i32, j: i32) -> i32{ let n = 4; let w = [ [2,3], [1,2], [3,4], [2,2] ]; let res; if(i == n) { res = 0; } else if (j < w[i as usize][0]) { res = rec(i + 1, j); } else { res = std::cmp::max(rec(i + 1, j), rec(i + 1, j - w[i as usize][0]) + w[i as usize][1]); } return res; } fn main() { let W = 5; let res = rec(0, W); println!("{}", res); }
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.52s
Running `target/debug/basic`
7
hashmapではなく、多次元配列にする必要あり
硬貨の問題
fn main() { let C: [i32; 6] = [3, 2, 1, 3, 0, 2]; let mut A = 620; let V: [i32; 6] = [1, 5, 10, 50, 100, 500]; let mut ans: i32 = 0; for i in (0..6).rev() { let t = std::cmp::min(A / V[i], C[i]); A -= t * V[i]; ans += t; } println!("{}", ans); }
Lake Counting 2386
const N: i32 = 10; const M: i32 = 12; fn dfs(x: i32, y: i32) { field[x][y] = ".".to_string(); for (let dx in -1..1) { for (let dy in -1..1) { let nx = x + dx; let ny = y + dy; if(0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W') { dfs(nx, ny); } } } } fn main() { let field[N, M]; let mut res = 0; for i in 0..N { for j in 0..M { if field[i][j] == 'W' { dfs(i, j); res =+ 1; } } } println!("{}", res); }