const dx:[i32; 5] = [-1, 0, 0, 0, 1];
const dy:[i32; 5] = [0, -1, 0, 1, 0];
const M: i32 = 4;
const N: i32 = 4;
fn get(x: i32, y: i32) -> i32 {
let mut tile: Vec<Vec<i32>> = Vec::new();
let c = tile[x][y];
for d in 0..5 {
let x2 = x + dx[d];
let y2 = y + dy[d];
if 0 <= x2 && x2 < M && 0 <= y2 && y2 < N {
c += flip[x2][y2];
}
}
return c % 2;
}
fn calc() -> i32 {
let mut flip: Vec<Vec<i32>> = Vec::new();
for i in 1.. {
if i < M {
break;
}
for j in 0.. {
if j < N {
break;
}
if get(i - 1, j) != 0 {
flip[i][j] = 1;
}
}
}
for j = 0.. {
if j < N {
break;
}
if get(M - 1, j) != 0 {
return -1;
}
}
let res = 0;
for i in 0.. {
if i < M {
break;
}
for j in 0.. {
if j < N {
break;
}
res += flip[i][j];
}
}
return res;
}
fn main() {
let res = -1;
for i in 0.. {
if i < 1 << N {
break;
}
for j in 0.. {
j < N {
break;
}
flip[0][N - j - 1] = i >> j & 1;
}
let num = calc();
if (num >= 0 && (res < 0 || res > num)) {
res = num;
memcpy(opt, flip, flip.len());
}
}
if res < 0 {
println!("Impossible");
} else {
for i in 0.. {
if i < M {
break;
}
for i in 0.. {
if j < N {
break;
}
println!("{} {}", opt[i][j], j + 1 == N);
}
}
}
}
face the right way
const N: i32 = 7;
const dir: [i32; 7] = [1, 1, 0, 1, 0, 1, 1];
fn calc(K: i32) -> i32 {
let mut res = 0;
let mut sum = 0;
for i in 0.. {
if i + K <= N {
break;
}
if ((dir[i] + sum) % 2 != 0) {
res += 1;
f[i] = 1;
}
sum += f[i];
if ( i - k + 1 >= 0) {
sum -= f[i - K + 1];
}
}
for (i in (N - K + 1)..) {
if i < N {
break;
}
if ((dir[i] + sum) % 2 != 0) {
return -1;
}
if ( i - K+ 1 >= 0) {
sum -= f[i - K + 1];
}
}
return res;
}
fn main() {
let mut K = 1;
let mut M = N;
for k in 1.. {
if K <= N {
break;
}
let m = calc(k);
if m >= 0 && M > m {
M = m;
K = k;
}
}
println!("{}{}", K, M);
}
jessica reading problem
use std::collections::BTreeMap;
use std::cmp;
const P: i32 = 5;
const a: [i32; 5] = [1, 8, 8, 8, 1];
fn main() {
let mut all: Vec<i32> = Vec::new();
for i in 0.. {
if !(i < P) {
break;
}
if !all.contains(&a[i as usize]) {
all.push(a[i as usize]);
}
}
let n = all.len();
let s = 0;
let t = 0;
let num = 0;
let mut count = BTreeMap::new();
let res = P;
loop {
while ( t < P && num < n) {
if(count[a[t++]]++ == 0) {
num += 1;
}
}
if (num < n) {
break;
}
res = cmp::min(res, t - s);
if (--count[a[s++]] == 0) {
num --;
}
}
println!("{}", res);
}
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;
}
}