2024-05-03

ABC135 E - Golf 解説

リンク

atcoder.jp

問題

無限に広がる二次元格子状の原点 $(0, 0)$ に居ます。
マンハッタン距離が $K$ となるような格子点への移動を繰り返して $(X, Y)$ に移動することができますか。
可能な場合は移動の最小回数とその移動経路を出力してください。

制約

$1 \leqq K \leqq 10^{9}$
$-10^{5} \leqq X, Y \leqq 10^{5}$
$(X, Y) \neq (0, 0)$

解説

最初に $X, Y$ が負の場合、符号を反転させることで $(X, Y)$ が原点から右上にあるケースのみ考えるだけで済むようにします。
以降は $0 \leqq X, Y \leqq 10^{5}$ として扱います。

次に $(X, Y)$ へ移動可能か、可能な場合は最小回数も求めます、これは以下のように求めることができます。
原点から座標 $(x, y)$ へのユークリッド距離を $d$ とすると、
1. $K \bmod 2 = 0$ かつ $d \bmod 2 = 1$ の時、達成不可能
2. $d = K$ の時、$1$ 回
3. $d \leqq 2K$ の時、$2$ 回
4. それ以外の場合、$\lceil \frac{d}{K} \rceil$ 回
5. ただし、$K \bmod 2 = 1$ かつ上で求めた移動回数と $d$ の偶奇が異なる場合はさらに $1$ 回移動する

移動回数を求めるフェーズはABC198 C - Compass Walkingと似ています。 atcoder.jp
ケース 2 は明らかです。
ケース 3 が成り立つとすると、ケース 4 は $(X, Y)$ までの距離が $d \le 2K$ になるまで $(x+K, y)$ または $(x, y+K)$ への移動を繰り返せば毎回距離が $K$ 縮まるのでケース 3 の状態に帰着します。
ケース 3 は各ユークリッド距離 $K$ の座標から移動できる斜めの正方形で $2K$ の範囲をほとんどカバーできます。

さらに細かい違いを見ていきます。

$K$ が偶数の場合、常に $d \bmod 2 = 0$ になります(偶数 + 偶数 = 偶数)。
そのため、$d \bmod 2 = 0$ には一切移動ができません、ケース 1 がこれに当たります。

$K$ が奇数の場合、$d \bmod 2 = 0, 1, 0, 1 \dots$ とパリティを交互に繰り返します(偶数 + 奇数 = 奇数 → 奇数 + 奇数 = 偶数)。
$(X, Y)$ への距離が $2K$ 以下になるまで $n$ 回移動したとします、この時 $n \bmod 2$ のパリティに居ることになります。
ケース 3 で $2K$ 以下まで詰めると $2$ 回で移動可能なことが分かりましたが、$n \bmod 2 = n + 2 \bmod 2$ の為、$n \bmod 2 \neq d \bmod 2$ となるパリティの合わないケースだとたどり着けないことが分かります。
そのため、$(X, Y)$ への距離が $2K$ 以下となる範囲で適当に $1$ 回移動し、パリティを合わせた後で $2$ 回移動するとたどり着けます、ケース 5 がこれに当たります。

最小の移動回数をまとめるとこのようになります。

ここからは移動回数 $n$ 回で座標 $(X, Y)$ を目指すことを考えます。

ケース 1 は達成不可能なので -1、ケース 2 は $(X, Y)$ を出力すればよいです。
ケース 4 の場合は距離が $2K$ 以下になるよう適切に $(x+K, y)$ か $(x, y+K)$ へ移動するとケース 3 に帰着します。
ケース 5 の場合は $2K$ 以下になった時点で残り $3$ 打になるので、距離が $2K$ 以下の座標 $(x+K, y)$ などに適当に移動しておきます。

ケース 3 の場合に移動する座標は実は簡単に求めることができます。
$2$ 回移動したときのパリティは一致することが分かっているので、$d$ は偶数です。
そこで、$1$ 回目の移動で $(X, Y)$ に $\frac{d}{2}$ 座標近づいた後、$(X, Y)$ から $K - \frac{d}{2}$ 座標離れれば、$2$ 回目の移動で同じだけ移動することになり目標が達成できます。

最初に符号を反転させている場合は、求めた座標の符号を反転させることを忘れないでください。

ACコード

use proconio::input;
use proconio::fastout;

#[fastout]
#[allow(non_snake_case)]
fn main() {
    input! {
        K: isize,
        (mut X, mut Y): (isize, isize),
    }
    // ケース 1
    if K % 2 == 0 && (X + Y).abs() % 2 == 1 {
        println!("-1");
        return;
    }
    // ケース 2
    if X.abs() + Y.abs() == K {
        println!("1");
        println!("{} {}", X, Y);
        return;
    }
    // 符号の反転
    let mut flg = 0;
    if X < 0 {
        X = -X;
        flg += 1;
    }
    if Y < 0 {
        Y = -Y;
        flg += 2;
    }
    // 最小移動回数を求める
    let mut n =
    // ケース 3
    if X + Y <= 2 * K {
        2
    }
    // ケース 4
    else {
        (X + Y + K - 1) / K
    };
    // ケース 5 (余分に 1 回移動する)
    if K % 2 == 1 && n % 2 != (X + Y) % 2 {
        n += 1;
    }
    // 移動座標を求める
    let mut ans = Vec::new();
    let (mut x, mut y) = (0, 0);
    // y に移動できるだけ移動する
    while Y - y >= K && (X - x) + (Y - y) > 2 * K {
        y += K;
        ans.push((x, y));
        n -= 1;
    }
    // x に移動できるだけ移動する
    while X - x >= K && (X - x) + (Y - y) > 2 * K {
        x += K;
        ans.push((x, y));
        n -= 1;
    }
    // パリティを合わせる為に x に余分に移動する
    if n == 3 {
        x += K;
        ans.push((x, y));
    }
    // (X, Y) に近づく距離
    let mah = ((X - x).abs() + (Y - y).abs()) / 2;
    // (X, Y) から離れる距離
    let sub = K - mah;
    // (x, y) の位置関係で移動先を場合分け
    if x < X {
        if X - x < mah {
            x -= sub;
            y += mah;
        }
        else {
            x += mah;
            y -= sub;
        }
    }
    else {
        if x - X < mah {
            x += sub;
            y += mah;
        }
        else {
            x -= mah;
            y -= sub;
        }
    }
    ans.push((x, y));
    ans.push((X, Y));
    let n = ans.len();
    // 符号の反転
    if flg & 1 > 0 {
        for i in 0..n {
            ans[i] = (-ans[i].0, ans[i].1);
        }
    }
    if flg & 2 > 0 {
        for i in 0..n {
            ans[i] = (ans[i].0, -ans[i].1);
        }
    }
    println!("{}", n);
    for i in 0..n {
        println!("{} {}", ans[i].0, ans[i].1);
    }
}

2023-04-08

Rustで競プロがやりたい(8)

灰色を全て解き終わり茶色に進むとなると、UnionFindなどのデータ構造がそろそろ出てくる。なので、そのあたりを整える為のlibrary checkerを使う。

judge.yosupo.jp

しかしlibrary checker、広く言えばAtCoder以外の競プロサイトはproconioが対応していない。 proconioをサイトからソースを引っ張ってきて貼り付けても、proconioに使われているlazy staticも対応していなかったりで、上手くいかない。他のコンテストサイトはともかくlibrary checkerまで使えないと確認ができなくて不便である。そこら辺うまく書いて対応しろという話ではあるが、今回はローカル環境でlibrary checkerのテストを行う方針を取る。

library checkerはソースコードがgithubで公開されている。

github.com

READMEに書かれているが、PythonとC++を予め使えるようにしておかないといけない模様。

環境構築が済んでいたので、まずはgitでclone。

git clone https://github.com/yosupo06/library-checker-problems.git

cloneしたフォルダに移動する。

cd path/library-checker-problems

初回は以下のコマンドも必要か

pip3 install -r requirements.txt

その後、実際にテストケースを作成する。

python ./generate.py -p (問題フォルダ名)

問題フォルダ名にはテストケースが欲しい問題のフォルダ名を入れる。 cloneしたフォルダにはdatastructureやmathなどグループ分けがされており、その中に問題のフォルダが格納されている。

ベルヌーイ数のテストケースが欲しい場合、以下の通りになる。

python ./generate.py -p bernoulli_number

こうすると、bernoulli_numberのフォルダの中にinとoutのフォルダが作られ、その中にテストケースが格納されている。

ところで、テストケースを作れない場合があった。 Rustのwarningのようなものが発生してて、実行はできるけど終了するみたいな感じで。その場合、下のコマンドで実行できるようにしておく。

set CXXFLAGS=-Wno-error

さて、テストケースはできたが、いちいち手動でコピペしてテストケースを実行するのは面倒。そこで、online judge toolsを使う。

github.com

pythonのライブラリになるのか、コマンドだけで導入可能。

pip3 install online-judge-tools

参照しているパスにtestというフォルダを作り、テストケースを入れる。 inとoutフォルダで分けるのではなく、中身のファイルを直接入れる。

その後、テストコマンドを実行する。 Rustの場合は、先にbuildを済ませて、できたexeファイルをコマンドで指定する。

oj t -c "(exeファイルのパスを指定)"

テスト結果が表示される。

今は少し面倒だが、この作業でごまかしている。

2023-03-05

Rustで競プロがやりたい(7)

Rustで灰Diffの問題を500問近く解いた。

500問解いたら流石に余裕と言いたいが、今でも詰まる要素が多々ある。大体1分で解ける問題と、何かしらで詰まり10分、またはそれ以上かけてようやく解けるような問題がある。

しかし、Rustはそこまで難しくないとも思い始めている。

よく見るのが、変数に .() を付けまくっている書き方。最初は呪文のように見えたが、冷静に見るとそうではないことが分かる。

例えば、下記コードでは文字列 X の 1 の数を数えている。

#[allow(non_snake_case)]
fn main() {
    let X = "000101".to_string();
    println!("{}", X.chars().filter(|&x| x == '1').count());
}

X を Chars 型にした後、filter で 1 文字ずつ 1 かどうかを確認し、最後に count で個数を返す。

もう一つ例を挙げる。

#[allow(non_snake_case)]
fn main() {
    let X = [1, 3, 2, 7, 9];
    println!("{}", X.iter().max().unwrap());
}

X の要素から、max で最大値を求め、Option 型で返されるので unwrap で値を取り出す。

つまり、「X を最終的にどうしたいか？」を考えて、必要であればそれを処理するために必要な処理を書き加えて...とすればいい。

あまりに長くなる場合や、処理ごとに分けて改行している人もいる。

#[allow(non_snake_case)]
fn main() {
    let X = [1, 3, 2, 7, 9];
    println!("{}", X.iter()
                        .max().unwrap());
}

ところで、通常は vec や array などは println! では出力できない。下記のコードだとエラーが出てしまうが、それだとデバッグの際に困ってしまう。

#[allow(non_snake_case)]
fn main() {
    let X = [1, 3, 2, 7, 9];
    println!("{}", X);
}

しかし内部に :? を書くと、vec や array も出力できる。これは Some(x) などの状態も出力できるのでかなり便利。

#[allow(non_snake_case)]
fn main() {
    let X = [1, 3, 2, 7, 9];
    println!("{:?}", X);
}

ちなみに、dbg! でも出力できる、dbg! の場合は何行目で出力したかも書かれるので見やすい。しかし、デバッグ時にしか出力されないので、提出の際の出力として使うことはできない。

#[allow(non_snake_case)]
fn main() {
    let X = [1, 3, 2, 7, 9];
    dbg!(X);
}

変数を宣言する際、宣言する場所に気を付ける必要があった。以下のコードでは、ans は -1 を出力する。

#[allow(non_snake_case)]
fn main() {
    let ans = "-1";
    if true {
        let ans = 99;
    }
    println!("{}", ans);
}

これは、if の中の ans は if のブロックを抜けたと同時に解放される為、なかったことになる。いわゆるライフタイムというやつで、宣言する場所は大丈夫か、他の処理で回避できないかなど考える必要がたまにあった。

この処理をどうやってやればいいか分からないといったとき、普通は検索して調べるのだが、今はchatGPTを使う方法がある。 Rustでどういう処理をしたいかを聞くことで、コードまで書いて返してくれる。

この手法はかなり便利だが、質問の仕方や内容によっては頓珍漢な回答をされるので、参考程度にするとよい。

Rust は分かってくると楽しいが、灰Diffなのでまだ struct や impl の段階に行ってないし、そもそも参照で呼ぶべきなのか分からなかったり、*&x などという頓珍漢な参照が出てきたり。環境面に関しても、デバッグビルドやリリースビルドなどは一切分からず、最終目標であるビジュアライザを作る辺りも一切手を付けれていない。

という状態でこれからも頑張る。

2023-02-25

Rustで競プロがやりたい(6)

AtCoderの灰色を埋めると決め、githubに解いたコードをあげることにした。

github.com

とりあえず灰試験管は全て解くことができたが、かなり詰まってしまった。 Twitterで「これができない」だの「エラーが出る」だの言いまくって、その度に助けてくれた皆には感謝しかない。

灰色問題とはいえ、難易度が高かった。特に文字列が難しい。

以下のような宣言だと、&strになる。

let S = "Moji";

それを.to_string()でStringになる。

let S = "Moji".to_string();

ところで、String型はstring型ではないらしい。こういった大文字、小文字もしっかり区別してかかないといけない。

1文字1文字for文で見たいとなったときは、Stringを.chars()で変換しないといけない。

for s in S.chars() {
    // test
}

.chars()でCharsにしたのを.collect()で配列として代入したり。

let S = S.chars().collect::<Vec<char>>();

matchを使うには、.as_str()で変換しないといけなかったり。

match S.as_str() {
    "abc" => "YES",
    _ => "NO",
}

Stringのi番目の要素を取得したいとき、かなり面倒な手順になるし。

let s = S.chars().nth(i).unwrap();

逆に後ろの文字は.last()で取れるし。

let s = S.chars().last().unwrap();

文字列の操作をしているときにかなり見たのだが、unwrap()をよく使うことになる。これは、Option型の結果が渡されるので、その中身の値を取り出す、という認識でいる。本当はエラーを考慮しないといけなかったりしそうなのだが、今回は大丈夫ということにする。

とりあえずやりたいことに合わせて型を変えたり、配列に入れたり、結果を取り出したり...と結構覚えることがたくさんある。特に型が違うとエラーで使えない、というのが頻発して大変だった。

これ以外にも色々覚えるべき文法はあるが、解き続けて覚えていくしかない。残りの灰埋めを頑張ることにする。

2023-02-13

Rustで競プロがやりたい(5)

前回の記事から日が開いてしまった。

competeを使って自動作成して提出もコマンドでできて、と楽だったのだが、Rustを書くのはボロボロだった。というより、基礎がまだちゃんとしていない状態でPythonでいうClassを書こうとして心が折れてしまった。

ここは一旦基本に忠実ということで、灰Diffを埋めてみる。 competeも一旦使わず、cargo newからまっさらの状態で始めてみる。

proconioは使う方針で。

[dependencies]
proconio = {version = "0.4.3", features = ["derive"]}

テンプレート、fastoutとnon_snake_caseだけ採用する。

use proconio::input;
use proconio::fastout;

#[fastout]
#[allow(non_snake_case)]
fn main() {
    input! {
        ,
    }
    println!();
}

まずは以下の問題から。 atcoder.jp

ACしたときは以下のようなコードになった。

use proconio::input;
use proconio::fastout;

#[fastout]
#[allow(non_snake_case)]
fn main() {
    input! {
        Y: usize,
    }
    let mut ans = "NO";
    if Y % 4 == 0 {
        ans = "YES";
    }
    if Y % 100 == 0 {
        ans = "NO";
    }
    if Y % 400 == 0 {
        ans = "YES";
    }
    println!("{}", ans);
}

しかし実際はかなりつまずいている。最初はlet mut ans = "";にifをif ~ else if ~ elseで書いて通せるようにした。すると次のwarningが出た、warningが出てもコードは回せる。

warning: value assigned to `ans` is never read
= help: maybe it is overwritten before being read?
= note: `#[warn(unused_assignments)]` on by default

つまり、ansを他の変数で操作や出力前に確定で別の値に上書きするので注意されている。下に#[warn(---)]と出ているので#[allow(---)]と書き加えれば出なくなるが、今回はwarningを消したい。

次はlet mut ans;と書き換えてみた。しかし別のwarningが出てしまう。

warning: variable does not need to be mutable
= note: `#[warn(unused_mut)]` on by default

今回if文で値を書き換えるのが1回だけの為、ミュータブルである必要がないみたいだった。最終的にlet ans;でwarningが消えたので解決した。

ちなみに普通にWAを出してしまったので最終的にあのACの形になった。

別の問題も見る。 atcoder.jp

2点間の距離は三平方の定理で求めることができる。 ACコードは以下の通り。

use proconio::input;
use proconio::fastout;
use libm::hypot;

#[fastout]
#[allow(non_snake_case)]
fn main() {
    input! {
        N: usize,
    }
    let mut Points = vec![];
    for _ in 0..N {
        input! {
            x: f64,
            y: f64,
        }
        Points.push((x, y));
    }
    let mut ans = 0.0;
    for i in 0..N {
        for j in 0..N {
            let distance = hypot((Points[i].0 - Points[j].0).abs(), (Points[i].1 - Points[j].1).abs());
            if ans < distance {
                ans = distance;
            }
        }
    }
    println!("{}", ans);
}

躓いた点をいくつか挙げる。

まずx, yを入力で受け取るフェーズ。 input!は最初に実行して全て受け取らないといけないと思っていたが、2か所に分けてもいいらしい。後は空の配列を用意する、そこに追加するといった基本的な処理も、まだ調べないとできなかった。 forも調べないと書けなかった。

次に実際に距離を求めるところ。 Rustはhypotを使うと距離を求めることができる。なので、use libm::hypot;を書き加え、hypotを使えるようにする。ちなみにCargo.tomlにlibmを書き加えないと使えない。

[dependencies]
libm = "=0.2.1"

今回tupleで座標を追加したため、[0]ではなく.0で呼び出さないといけなかった。またhypotはf64しか受け付けていないが、自前で計算を用意する場合でも答えが小数点になる可能性があるので座標の入力をf64で受け取らないといけない。座標だからusize確定ということがないことを意識しないといけない。

やる度に新しいことがでてきて大変だが、灰Diff埋めでしばらくは頑張っていこうと思う。

2023-02-07

AHC017を通した戒め

0. はじめに

AHC017 に参加して 921 位でした。
パフォーマンスは 426 でレートが 536 → 563 になりました。
つらい。

1. ビジュアライザの使い方をちゃんと見ていなかった

ビジュアライザを見て、Input があって Output がある。
Output に出力を乗せると下の画像が変化する。
じゃあ大体の使い方はこうだな、で使っていました。
しかし詳細を見ると「dayの値を1以上にすると、その日に工事する辺のみがピンク色で表示されます。頂点をクリックすると、その頂点からの最短距離の増加量に応じて各頂点が色付けされます。」と書かれていました。
実際この機能は凄まじく便利で、頂点をクリックするとスコアの変化によって頂点に色が付けられる為、考察にかなり役立つ機能でした。
ちゃんとビジュアライザの詳細は見るべきでした。

2. 問題の得点を正確に求めすぎた

今回の問題は状態の得点を正確に求めようとすると、かなり時間がかかります。
コンテスト中は正確な得点を高速に求めることを必死に考えて、ドツボにハマっていました。
近似値となるスコアを高速に求めて山登りや焼きなましを試す方が、結果的には高得点に繋がることを初めて知りました。

3. テストケースをシード 0 しか試さなかった

最初はランダムな出力を試し、あとは 2 で高速化を頑張っていたのですが、その時に使ったテストケースはシード 0 だけでした。
ランダムだから 0 だけ見る、結果が良くなるか見たいだけだから 0 だけ見る、そんな感じで 0 だけ見てました。
テストケースによって答えが良くなったり、悪くなったりするのを見るべきところを 1 ケースで済ませたのは良くありませんでした。

4. 提出するコードをちゃんと確認しなかった

このような長期コンだと提出の間隔は WA だろうが TLE だろうが 30 分ごとになります。
つまり、答えをちゃんと出力できていないコードを間違えて提出すると無駄に 30 分提出できなくなります。
今回、ビジュアライザに貼り付けるために出力をテキストに書き込むコードを提出してしまった為、ファイルパスを晒した挙句 30 分無駄に提出できなくなってしまいました。
焦らず確認してから提出しようと思いました、間違って提出したコードは消させて欲しいです。