2023-08-21

なんか無駄なことをしている気がする……と思ったんだけど

ABC314のC - Rotate Colored Subsequenceである。

べつにバグではないんだけど、競技中にあんまり調べていられなかったのと、「リングバッファ」というの名前が思い出せなくて、結局vecの要素のシフトをこう書いてしまった。

どことなくアホっぽいけど、これでも時間制限には引っかからないんですよね。reverse()ってO(M)くらいかと思うけど、意外と他の方法とかわらない。

    for clr in 1..=m {
        let tmp = map[clr].pop().unwrap();
        map[clr].reverse();
        map[clr].push(tmp);
    }

ちなみに、これ、なんでひっくり返しているかというと、取り出すときに都合がよかったのですよね。もちろんVecDequeueで書けばひっくり返す必要は無い(が、もちろん思いださなかった)。しかも先に紹介した方法のがpush_front()の回数が少ないせいか、意外なことにちょっと遅くなる。

    for i in 0..n {
        let j = map[c[i]].pop().unwrap();
        print!("{}", s[j]);
    }

pop()のかわりにイテレータで記憶しておくこともできる。添字でもいい。が、配列にする必要がある。コードは省略するが、これも速くはない。

そもそも、このようにvecの使い回しをしないで、公式の解説のように2つのvecを用意して、右から左に入れコピーした方が速くなる。が、桁が違うというほどではなかった。

Rushのコンパイラーが頭がいいせいかもしれないけど、AtCoderの問題の範囲では多分これはわりとどうでもよいトピックなんだと思う。

2023-08-06

AtCoderの次のコンテスト環境のテストが行われていますが……

AtCoder

AtCoderの次のコンテスト環境のテストが行われているので、参加してみています。

atcoder.jp

しかし、下準備(後述)をし、とりあえずA問題を送ろうとしたところで、cargo compete s aがエラーになった(下記)。

$ cargo compete s a
     Running `/Users/flashingwind/.cargo/bin/cargo-compete compete t --src /Users/flashingwind/atcoder2/newjudge-2308-algorithm/src/bin/a.rs --display-limit '4 KiB' --manifest-path /Users/flashingwind/atcoder2/newjudge-2308-algorithm/Cargo.toml --color auto`
     Running `/Users/flashingwind/.rustup/toolchains/1.70.0-x86_64-apple-darwin/bin/cargo build --bin newjudge-2308-algorithm-a --manifest-path /Users/flashingwind/atcoder2/newjudge-2308-algorithm/Cargo.toml`
    Finished dev [unoptimized + debuginfo] target(s) in 0.29s
1/3 ("sample1") Accepted (243 ms)
2/3 ("sample2") Accepted (243 ms)
3/3 ("sample3") Accepted (243 ms)
……
error: Submission rejected

ちなみに解答に対する自動テストまでは正常に走っていて、Acceptedになっています。解答をコピペしてウェブから送るとACになる。

どうもいつもの感覚だと、送信されるだけでももっと時間がかかるのに、あまりにも短時間のうちにエラーが返るので、AtCoderのウェブサイトをスクレイピングするのに失敗しているとか、アクセスが拒否されたとかそんな感じではないかと思うけど、よくわかりません。なんかCargo.tomlにマズいこと書いたかなあ。

ジタバタしましたが、ダメ。

$ cargo compete l atcoder
     Already Logged in
$ cargo compete p atcoder newjudge-2308-algorithm
warning: already participated
$ cargo install cargo-compete --force

今回試した手順は下記の通り。

まず、私の場合、Rust1.68.2とcargo competeがすでに入ってます。

Rustツールチェイン

Rustだと1.42.0→1.70.0にバージョンアップしたようです。詳細・他の言語についてはこちらを。

さて、実は私はバージョン指定がけっこうてきとーで、なぜか1.68系を使っていますが、今度こそちゃんとやろうと思う(ただし、本番のコンテスト環境はまだしばらく1.48なので、これを上げたり下げたりするとトラブルがあるかもしれず、自己責任でやってください)。現状:

$ rustup show
Default host: x86_64-apple-darwin
rustup home:  /Users/flashingwind/.rustup

installed toolchains
--------------------

1.68.2-x86_64-apple-darwin (default)

active toolchain
----------------

1.68.2-x86_64-apple-darwin (default)
rustc 1.68.2 (9eb3afe9e 2023-03-27)

私はあんまり気にしないのと、RustをAtCoderにしか使ってないので、そのままグローバルに1.70入れ、defaultにしてしまいます(直近のコンテストでは、雰囲気で、手動で1.48との差分をなんとかする予定)。

$ rustup update #stableとかを使ってるとアップデートされるので注意
$ rustup install 1.70.0-x86_64-apple-darwin
$ rustup default 1.70.0-x86_64-apple-darwin
info: using existing install for '1.70.0-x86_64-apple-darwin'
info: default toolchain set to '1.70.0-x86_64-apple-darwin'

  1.70.0-x86_64-apple-darwin unchanged - rustc 1.70.0 (90c541806 2023-05-31)

一応確認。

$ rustup show
……
1.70.0-x86_64-apple-darwin (default)
……

ライブラリー

使えるライブラリー(クレート)も先ほどのページに指定されています。さすがに、既存環境をいじりたくないので、まず新しいフォルダーを。

$ mkdir atcoder2
$ cd atcoder2
$ cargo compete init atcoder
Do you use crates on AtCoder?
1 No
2 Yes
3 Yes, but I submit base64-encoded programs
1..3: 2
       Wrote /Users/flashingwind/atcoder2/./compete.toml
       Wrote /Users/flashingwind/atcoder2/./template-cargo-lock.toml

compete.tomlにコンテスト新規作成するときのデフォルトのCargo.tomlのひな形があり、ここのdependencies = '''から'''を前述の通り書き換えます。toolchain = "1.70.0"も。ただし、AtCodeの提供するクレートの一覧は形式が違うみたいなので、いい感じに=([.0-9]+)を= "=$1"部分的に置換しました。

$ code /Users/flashingwind/atcoder2/./compete.toml
……

dependencies = '''
ac-library-rs = "=0.1.1"
once_cell = "=1.18.0"
static_assertions = "=1.1.0"
varisat = "=0.2.2"
memoise = "=0.3.2"
argio = "=0.2.0"
bitvec = "=1.0.1"
counter = "=0.5.7"
hashbag = "=0.1.11"
pathfinding = "=4.3.0"
recur-fn = "=2.2.0"
indexing = "=0.4.1"
amplify = "=3.14.2"
amplify_derive = "=2.11.3"
amplify_num = "=0.4.1"
easy-ext = "=1.0.1"
multimap = "=0.9.0"
btreemultimap = "=0.1.1"
bstr = "=1.6.0"
az = "=1.2.1"
glidesort = "=0.1.2"
tap = "=1.0.1"
omniswap = "=0.1.0"
multiversion = "=0.7.2"
num = "=0.4.1"
num-bigint = "=0.4.3"
num-complex = "=0.4.3"
num-integer = "=0.1.45"
num-iter = "=0.1.43"
num-rational = "=0.4.1"
num-traits = "=0.2.15"
num-derive = "=0.4.0"
ndarray = "=0.15.6"
nalgebra = "=0.32.3"
alga = "=0.9.3"
libm = "=0.2.7"
rand = "=0.8.5"
getrandom = "=0.2.10"
rand_chacha = "=0.3.1"
rand_core = "=0.6.4"
rand_hc = "=0.3.2"
rand_pcg = "=0.3.1"
rand_distr = "=0.4.3"
petgraph = "=0.6.3"
indexmap = "=2.0.0"
regex = "=1.9.1"
lazy_static = "=1.4.0"
ordered-float = "=3.7.0"
ascii = "=1.1.0"
permutohedron = "=0.2.4"
superslice = "=1.0.0"
itertools = "=0.11.0"
itertools-num = "=0.1.3"
maplit = "=1.0.2"
either = "=1.8.1"
im-rc = "=15.1.0"
fixedbitset = "=0.4.2"
bitset-fixed = "=0.1.0"
proconio = "=0.4.5"
text_io = "=0.1.12"
rustc-hash = "=1.1.0"
smallvec = "=1.11.0"
'''

……

toolchain = "1.70.0"

実行

$ cargo compete new newjudge-2308-algorithm # コンテスト読み込み
$ cd newjudge-2308-algorithm
$ code .
$ cargo build

$ cargo compete s a
……
error: Submission rejected

2023-06-05

vec<u32>の総和はsum<u64>()でもu32の最大値でオーバーフローする

AtCoder 今日のバグ

要素がu32型のvecの総和を求める際、いつもはfor式を使い、sum()を使わないのだが、ちょっとかっこつけて使ってみたら失敗したという話です。

和を取るとき、オーバーフローするというのはよくあるのだが、sum()にをつけてもダメだった、結果をキャストするだけらしい。今日はこれでハマった。

そもそも、N=10⁹、A[i]=10⁹ (0≦i<N)みたいな、よくある設定がありますが、あれは符号なし32bit整数型(unsigned int/u32)で計算すると桁あふれすることを狙っている場合があります。

今回の計算の場合以下のように見積もると、32bitでは足りない値が出てきました。そこで最後の総和だけは64bitにしようと考えました。

Nはlog_2(2*10⁵)=17.60…bit*1つまり、Nは18bitで表現できる。
A[i]も同様に30bitくらい。
ΣA[i]の最大値はN×A[i]の次元になるので、logだから上記2つを足して30bit+18bitくらい必要。

というか、わりとすぐに犯人は総和だとわかっていたのだけど、うまい対応が思いつかなかった。もちろん全部u64にするのがベストである。しかし、u32で計算できるのに、u64でやるのは悔しいじゃないか。

性能的には、並列化もしていないし、このこだわりに意味はない。メモリー使用量はu32で4840KB、全部u64でも5580KB。実行時間に至っては本当に差がない。一応vecの容量を計算してみたけど、

64 bit210⁵ = 1526 KiB
32 bit210⁵ = 763 KiB

という感じ。ただ、Rustでできるのか知らないけど、ベクトル演算ができるAVX512命令とかで上手く並列化できた場合は一部の計算(乗加算)は速度が倍になるかもしれない。

この例はAtCoder Beginner Contest 246(ABC246)のCである。この問題の入力は≦10⁹なので、u32で格納はできる。またdkという変数はa/xなのでaを超えない。aとkはひたすら減るだけ。加算があると問題になるのだが、加算は最後まで行われない。

まずWrong Answerなコードを:

use proconio::input;

fn main() {
    input! {
        n: usize,
        mut k: u32,
        x: u32,
        mut a: [u32;n],
    };
    a.sort_unstable();
    a.reverse();
    for i in 0..n {
        let dk = a[i] / x;
        if k <= dk {
            a[i] -= k * x;
            k -= 0;
            break;
        } else {
            a[i] -= dk * x;
            k -= dk;
        }
    }
    a.sort_unstable();
    a.reverse();
    if 0 < k {
        for i in 0..n {
            if a[i] != 0 {
                a[i] = 0;
                k -= 1;
            }
            if k == 0 {
                break;
            }
        }
    }
    println!("{}", a.iter().sum::<u32>()); // オーバーフローする
}

次に、Acceptされた方を。結局キャストするので、なんかありがたみが薄いけど。しかし、このaccとして渡されていく値に蓄積していくので、これはどうしてもu64じゃないとまずい。この部分は結局u32でも、u64でも64bitで計算せざるを得ないので、並列化してもbit数削減による並列度向上はない。速くならない。

//(前略)
    println!("{}", a.iter().fold(0u64, |acc, v| acc + (*v as u64))); // オーバーフローする
}

*1:関数電卓的な計算はGoogleで: log_2(2*10^5) - Google 検索。複雑すぎてGoogleが電卓モードにならないときはlog_2(Power[10,5]) - Wolfram|Alphaで。

2023-05-20

0回目

AtCoder 今日のバグ

今日のバグ作品です。入力nを元にk回計算をする問題です(ABC192-C: C - Kaprekar Number)。

use proconio::{input, marker::Chars};

fn main() {
    input! {
        n: Chars,
        k: usize,
    };
    let mut a = n.to_owned(); // 数字(char)の配列
    let mut a_int = 0; // 文字列aを整数にしたもの
    for _i in 1..=k {
       // aを計算
       // a_intを更新
    }
    println!("{}", a_int);
}

これだと、k=0のとき、for内部を経ないので0が出てきてしまいます。正しくはnが出力される必要があるのですが。私の作ったバグはこのような境界条件で変になるパターンが多いです。

    let mut a_int = n.iter().collect::<String>().parse::<u32>().unwrap();

2023-05-11

AtCoderを始めた

AtCoder

最初の提出の記録が2023-01-05なので、もう4カ月たつし、AtCoder ProblemssのStreakも87 daysだが、まだ灰色である。べつにさぼってるわけではなくて、なにかなければ、ちゃんとABCとARCには参加している。過去問もそれなりに解いていて、リアルタイムで解いたのを含めてAcceptedは360問ある。でも、灰色。ABCのCがコンスタントには解けない。ARCのAがコンスタントには解けない。

私は、以前から、アルゴリズムはよわよわで、ライブラリーやツールの知識だけで生きているところがあったが、あらためて泣きたくなるほど競技プログラミングに向いていないことがわかった。まあ、昔参加したACM ICPCも毎回1次予選で敗退だったけど、42ではわりと困らなかったし、ちょっとはマシになってると思ったんだけどなあ。幻想でした。

やっぱり、42のPiscineはアルゴリズムの勝負じゃなかったんだな。ノウハウの部分が大きかった。作業量をこなせるかが重要っていうか。

うんまあ、でも、がんばります。まだじりじりとだけど上がってるので、頭打ちってわけではないし。

あー、頭がよくなりたいーー。

2023-01-26

42tokyo Piscineに落ちた話

追記: この記事(2022/10)のころは、六本木に校舎があり、開発・判定環境はmacOSでしたが、新宿に移転したり、環境もLinux(具体的には不明)に変わったらしいので、シェルのオプション周りLinux風にだいぶ変わっている可能性があります。どうぞその点はお含み置きください。

Piscine(ピシン)、落ちた話も受かった話もまあまあブログ記事とかになっていて、公開できないことも多いし、僕がこれ以上つけ加えることはほとんどないと思うが………。なんていうの、やっぱり落ちればくやしいわけで、なにかポエムを書こうと思って。

42tokyo

そもそも、42tokyoは何なのだろうか。プログラミングスクールなのだろうか。もちろん学校法人ではない(一般社団法人 42 Tokyo)。~~実質はDMM様のご厚意で、会社の大きい部屋と大量のiMacを貸していただいているという感じだ。~~新宿熊野神社の隣へ独立した。

最近私が気に入っている定義は、定期的に問題を解かないと追い出されるサロンというものだ。

ピシン(Piscine)

ピシンも、入学後も、「問題と生徒だけがあって、先生がいない」基本スタイルは変わらないようである。落ちたので、本科は詳しくないけど、ウェブサイトにはそう書いてある。ピシンには体験会的な面もあるのだろう。

私ことmiidaは2022年10月度のピシンを受けた。ウェブサイトで受ける2時間かかる壮大なCAPTCHAみたいな試験があり、受かったので、ピシンに参加した。IDから「みいださん」とか「いいださん」と呼ばれていた。

私の出身は、入試偏差値で日本で三指には入ると言われるアホ高専だが、一応電子情報工学科卒で、情報系であった。情報工学専門なら42なんて行かなくてもいいんじゃない？　って思う人もいるらしいけど、ぜんぜんそんなことないから。現に落ちてるし。高校1年とかの必要性のわかってないやつらにプログラミング教育するのって難しくて、大した授業は受けられなかったのだ。

ピシンの風景

あるところに集められて、問題集渡されて、4週間放置されるみたいな感じ。レビュー予約と自動判定のシステムは一体で、大問ごとに2回レビューを受けると自動判定が走る。レビューの点数はおそらく大して大きくない。レビューを受けたいときは空き枠から選べる。逆に自分がレビューしてもいい時間帯を登録しておくと、システムを通じて勝手に予定が入る。レビューは15分単位で入れられるが、私は15分だと足りなかったから、15分ごとに枠を入れておいて、ブッキングされたら前後の空き枠を消していた。

~~リアル教室はでっかいパソコン室みたいなのが1個ある。~~リアル教室はいくつかのパソコン室みたいなのがある。私たちの回はコロナ特例でオンラインで参加できたので、ほとんどいっていない。現在は完全オンラインは不可能らしい。

勝ち方と負け方

落ちた話も受かった話もまあまあブログ記事とかになっているが、

がんがんググって、
がんがんコード書いて、
遠慮せず質問して、
がんがんレビュー受けて、
がんがん他の人のレビューする
どれが足りなくてもダメ

というのが私が身をもって(不合格になることで)学んだことだ。特に私は時間をかけすぎたことが落ちた理由である。

大問のなかに小問がいくつか入っていて、判定は小問ごとにOK/NGされる。

各大問のうち50%で合格。ただし、一番最初のNGになった小問以降は点数にならないというスパルタ。なので、

大問を最後までやるような完璧主義もダメ
だけど、凡ミスで前半の小問をNGにする注意力のなさもダメ

だと思う(大問最後までやることが、入った後に役に立つ可能性はあるが)。

これでPassしなかったら、NGの問題だけなおして、またレビュー×2、自動判定してもらう。

私が負けたのは、まずレビューのポイント制を理解してなかったこと。完璧主義であったために、提出したコードをながめて、なかなかレビューを受けず、「24時間以内に2レビュー受ける」ルールを守れてなかったことがある。書き終わってfinishボタン押してから「これで大丈夫かな？」とかぐずぐず見直したり、ブッキング入れたのにキャンセルしたり(ポイントが消える)。

これは本当にダメ。

はじめの方は、平気で書いてから4日(24時間以上)とか寝かしていた。これだけは本当に無駄。

私はせまい実家住みなので、夜型なのに、午前0時以降は通話しないと決めていたのだけど、そうするとまともにレビューができなかった。最後の方はあきらめて家族に謝って、午前2時、3時とかにレビューしてましたが、フルタイムは無理でも休日なし毎日6時間程度は必要じゃないかな。

ちなみに、finish(提出)後24時間以上経過ってもレビューが2回終わらないとどうなるかご存じの方はいますか？　これまともな人は体験しない結構なレアケースで、どうなるか知らない方もいるだろうが、1レビュー受けた瞬間に自動判定が走って、OK/NGはわかるけど、0点になります。

そんなことばっかりしてたら、お互いの進捗ってよくわからないので、最後の方のチーム戦で組んだ大学生に「え！なんで、そんなところにいるの！こっちはいいから、自分のやって！！」とめっちゃ怒られました。すみません、すみません。

とにかく最初は知識がなくても、Googleで調べたり、同期の人から情報を得るのが上手く、デバッグやレビューを参考に、驚異的な速度で私を追い抜いていって受かった人もいる。

とにかく手が動かないのは許されない。

仕事があったりして、時間がないときは

ちなみに、どうしてもピシン中に時間を確保できない場合は、事前にC言語の勉強、シェル(bash)の勉強をするしかない。

シェル使ったことない、シェルってそもそもなんですか？　ってのは論外で、大変な目にあう。

何がなくても、そのくらいの事前準備はした方がいいと思う。

主要なコマンド5個くらいかな……の名前とおおまかな機能の暗記。
あと一般的なオプションや引数の形式(つけかた)。
複数のコマンドを組み合わせるやり方とか(いくつかある)

まで、知ってるとスタートダッシュが効くかも。

そしてC言語。

どのような課題か教えることはできないが、海外も含めて42本科の最初には「ft_lib」という課題があるらしい(必修なので、できないと即退学)という記事を読んだけど、まあそういう学校なので、ft_libが何か説明を読んで、なんとなくどういう風に作るか理解できくらいのレベルが、入学を許可されるレベルなんだと思う。

公開情報によれば「ft_lib」は、「libc(glibc)」とかのサブセットを自作するようだ。Cのコンパイラに付属する標準的なツール(関数とか)が入っている「libc」というものがあるんだけど。~~あと、macOSはUNIXであるから、UNIX基準で勉強すること。~~

つまり、これから言えるのは、Cに関しては大ざっぱに言って1990年年代前半くらいまでのC言語の教科書に載っているような知識が役立つということ。当然CLI(コマンドライン)のみで、GUIはピシンには出ないとわかる。

ピシンの合格した友人たちが、このft_libでヒーヒー言っているので、もちろん一々ライブラリーの中身を使える必要はない。ただ、ライブラリーってなに？　関数ってなに？　では不利になるだろう。

合格者は即ft_libが書けること期待してるわけですからね。