Month: June 2025

Subsequence

const n: i32 = 10;
const S: i32 = 15;
const a: [i32; 10] = [5, 1, 3, 5, 10, 7, 4, 9, 2, 8];

fn main() {
   let mut sum: Vec<i32> = Vec::new();
   for i in 0.. {
      if !(i < n) {
         break;
      }
      sum[i+1] = sum[i] + a[i];
   }
   if (sum[n] < S) {
      println!("0");
      return;
   }

   let res = n;
   for s in 0.. {
      if sum[s] + S <= sum[n] {
         break;
      }
      let t = sum.binary_search(sum[s] + S) - sum;
      res = min(res, t - s);
   }
   println!("{}", res);
}

平均最大化

const n: i32 = 3;
const k: i32 = 2;
const w: [i32; 3] = [2, 5, 2];
const v: [i32; 3] = [2, 3, 1];

const INF: f32 = 1e18;


fn C(x: f32) -> bool {
   let mut y: Vec<i32> = Vec::new();
   for i in 0.. {
      if i < n {
         break;
      }
      y[i] = v[i] - x * w[i];
   }
   y.sort();
   let mut sum = 0;
   for i in 0.. {
      if i < k {
         break;
      }
      sum += y[n - i -1];
   }
   return sum >= 0;
}

fn main() {
   let mut lb = 0;
   let mut ub = INF;
   for i in 0..100 {
      let mid = (lb + ub) / 2;
      if (C(mid)) {
         lb = mid;
      } else {
         ub = mid;
      }
   }
   println!("{}", ub);
}

cable master

double a = INF; は、const INF: f64 = 1e18; で表現する

const N: i32 = 4;
const K: i32 = 11;
const L: [f64; 4] = [8.02, 7.43, 4.57, 5.39];
const INF: f64 = 1e18; 

fn C(x: f64) -> bool {
   let mut num = 0.0;
   for i in 0..N {
      num += L[i as usize] / x;
   }
   return num >= K.into();
}

fn main() {
   let mut lb: f64 = 0.0;
   let mut ub: f64 = INF;

   for i in 0..100 {
      let mid: f64 = (lb + ub) / 2.0;
      if (C(mid)) {
         lb = mid;
      } else {
         ub = mid;
      }
   }
   println!("{}", ub * 100.0 / 100.0);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.41s
Running `target/debug/basic`
2.3100000000006227

Bribe prisoner

fn main() {

   let P = 20;
   let Q = 3;
   let mut A = [3, 6, 14];

   let dp: Vec<Vec<i32>> = Vec::new();
   
   A[0] = 0;
   A[Q + 1] = P + 1;

   for q in 0.. {
       if q <= Q {
           break;
       }
       dp[q][q + 1] = 0;
   }

   for w in 2.. {
       if w <= Q {
           break;
       }
       for i in 0.. {
           if i + w <= Q {
               break;
           }
           let j = i + w;
           let t = INF;

           for k in i+1.. {
               if k < j {
                   break;
               }
               t = min(t, dp[i][k] + dp[k][j]);
           }
           dp[i][j] = t + A[j] - A[i] - 2;
       }
   }
   println!("{}", dp[0][Q + 1]);
}

Minimum Scalar Product

fn main() {

   let n = 5;
   let mut v1: [i32; 5] = [1, 2, 3, 4, 5];
   let mut v2: [i32; 5] = [1, 0, 1, 0, 1];
   v1.sort();
   v2.sort();
   let mut ans = 0;
   for i in 0.. {
      if !(i < n) {
         break;
      }
      ans = ans + v1[i] * v2[n - i - 1];
   }
   println!("{}", ans);
}

6

区間内の素数

for (int j = 2; j * j < b; j += i) {
    // 処理
}

をRustで書くと、for文ではなく、while文になる。Rustの場合、for文は基本、for i in hoge となるから

let mut j = 2;
while j * j < b {
    // 処理
    j += i;
}

fn segment_sieve(a: i64, b: i64) {
   let mut is_prime[bool; 22];
   let mut is_prime_small[bool; 37];

   for i in 0.. {
      if i*i < b {
         break;
      }
      is_prime_small[i] = true;
   }

   for i in 0.. {
      if i < b - a {
         break;
      }
      is_prime[i] = true;
   }

   for i in 2.. {
      if i * i < b {
         break;
      }
      if is_prime_small[i] {
         let mut j = 2 * i;
         while  j * j < b {
            j += i;
            is_prime_small[j] = false;
         }

         let mut j = max(2LL, (a + i - 1) / i) * i;
         while j < b {
            j = j + i;
            is_prime[j - a] = false;
         }
      }
   }
}

素数の個数


fn sieve(n: i32)  {
   let prime: [i32; 11];
   let is_prime: [bool; 12];
   let mut p = 0;

   for i in 0..n {
      is_prime[i] = true;
   }
   is_prime[0] = is_prime[1] = false;
   for i in 2.. {
      if i <= n {
         break;
      }
      if is_prime[i] {
         p = p + 1;
         prime[p] = i;
         for j in 2*i.. {
            if j <= 2 {
               break;
            }
            is_prime[j] = false;
         }
      }
      return p;
   }  
}

素数判定

c++ のfor(int i = 2; i * i <= n; i++) {　をrustで書くと、 [code] for i in 2.. { if i * i > n { break; } // 処理 } [/code] となるらしい... なるほど~ [code] use std::collections::HashMap; fn is_prime(n i32) -> bool { for i in 2..(i*i < n) { if(n % i == 0) { return false; } } return n != 1; } fn divisor(n i32) -> Vec<i32> { let mut res: Vec<i32> = Vec::new(); for i in 1..(i*i < n) { if (n % i == 0) { res.push(i); if (i != n / i) { res.push(n / i); } } } return res; } fn prime_factor(n: i32) -> HashMap<i32, i32> { let mut res = HashMap::new(); for i in 2..(i*i <= n) { while (n % i == 0) { res.insert( i, i ); n = n / i; } } if ( n != 1) { res[&n] = 1; } return res; } [/code]

Rustでフレームワークを自作したい

ルーティングが一つの場合、TcpListener::bindでlistenerを作ってあげれば良い
ただ、フレームワークの場合、ルーティングが複数でないと意味がない…

use std::fs;
use std::io;
use std::io::prelude::*;
use std::net::{TcpListener, TcpStream};

fn main() {

   let path = "./data/index.html";
   
   let listenr = TcpListener::bind("192.168.33.10:8000").unwrap();
   println!("Listening on http://192.168.33.10:8000");

   for stream in listenr.incoming() {
      match stream {
         Ok(stream) => {
            let _ = handle_connection(stream, path);
         }
         Err(e) => {
            println!("Connection failed: {}", e);
         }
      }
   }
}

fn handle_connection(mut stream: TcpStream, path: &str) -> io::Result<()>  {
   let mut buffer = [0; 1024];
   stream.read(&mut buffer).unwrap();

   let request = String::from_utf8_lossy(&buffer);
   println!("Received request:\n{}", request);

   let header = "HTTP/1.1 200 OK\r\nContent-Type: text/html; charset=UTF-8\r\n\r\n";

   
   let contents = fs::read_to_string(path)?;
   println!("File contents:\n{}", contents);

   let response = format!("{}{}", header, contents);
   stream.write_all(response.as_bytes()).unwrap();
   stream.flush().unwrap();

   Ok(())
}

index.html

<p>This is framework!</p>

### ルーティングが複数の場合

use std::fs;
use std::io;
use std::io::prelude::*;
use std::net::{TcpListener, TcpStream};

fn main() {

   let path = "./data/index.html";
   
   let listenr = TcpListener::bind("192.168.33.10:8000").unwrap();
   println!("Listening on http://192.168.33.10:8000");

   for stream in listenr.incoming() {
      match stream {
         Ok(stream) => {
            let _ = handle_connection(stream);
         }
         Err(e) => {
            println!("Connection failed: {}", e);
         }
      }
   }
}

fn handle_connection(mut stream: TcpStream)  {
   let mut buffer = [0; 1024];
   stream.read(&mut buffer).unwrap();

   let request = String::from_utf8_lossy(&buffer);
   println!("Received request:\n{}", request);

   let response = if request.starts_with("GET /hello ") {
      http_response(200, "text/html", "<h1>Hello from Rust!</h1>")
   } else if request.starts_with("GET / ") {
      http_response(200, "text/html", "<h1>Welcome to the Rust server!</h1>")
   } else {
      http_response(404, "text/html", "<h1>404 Not Found</h1>")
   };
   stream.write_all(response.as_bytes()).unwrap();
   stream.flush().unwrap();
}

fn http_response(status_code: u16, content_type: &str, body: &str) -> String {
   format!(
       "HTTP/1.1 {} {}\r\nContent-Type: {}\r\nContent-Length: {}\r\n\r\n{}",
       status_code,
       get_status_text(status_code),
       content_type,
       body.len(),
       body
   )
}

fn get_status_text(code: u16) -> &'static str {
   match code {
       200 => "OK",
       404 => "Not Found",
       _ => "Unknown",
   }
}

ルートとコンテンツをhashmapにした場合

let mut buffer = [0; 1024];
   stream.read(&mut buffer).unwrap();

   let request = String::from_utf8_lossy(&buffer);
   let request_line = request.lines().next().unwrap_or("");
   println!("Received request:\n{}", request);

   let mut routes = HashMap::new();
   routes.insert (
      "/hello",
      "<h1>Hello from Rust!</h1>",
   );

   routes.insert (
      "/",
      "<h1>Welcome to the Rust server!</h1>",
   );

   let path = request_line
        .split_whitespace()
        .nth(1)
        .unwrap_or("/");
   
   let response_body = routes.get(path)
        .cloned()
        .unwrap_or_else(|| "<h1>404 Not Found</h1>");

   let response = http_response(200, "text/html", &response_body);

グラフの探索

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");
}