ブラックホールへの道(回避)
そもそも、去年の10月に42に入学したのに、それも書いてなかったですね。なんか最近、Twitterでつきあいのある人たちや、42の人がどうもnoteの方に書くことが多いので、なんとなくそれにならってあっちに書いている。
この手前の記事はAtCoderでしたが今はサボっている。
さて、なんか前回受験時(2022年)も「無職になった！ Piscineを受けよう！」と考えた記憶がありますが、今回もです。それで、2回目で受かったわけです。
ちなみに1回目のPiscineで受かった場合は、課題の提出期限がすぎて退学になった場合、もう一度Piscineからやり直せるので、できれば1回で受かりましょう。
ブラックホール直前
というのもですね、実はいま、まさに課題の提出期限がすぎて退学になりそうになっているのです。入って半年経ってないのにもうかよ。
どのくらい迫っているかというと、いま「2025/04/25・7 days left」みたいに表示されています。うわー、どうしてこうなるまで放っておいたんだ……。
放っておいたというより、手が遅い。勤勉さが足りない。長期間がっつり休む度胸はないんですが、ちょいちょいサボってる。
いやー、でも、ここまでくると、もういろいろ覚悟が決まってきます。もともと私物をほとんど置けないので、せいぜいインスタントコーヒーくらいなんだけど、それも、何日の段階で捨てるか持って帰るか、などと頭の端では考えていて、頭の残りの部分ではまだ粘ってなんとかしようとしている感じですね。
レビュー通過が絶望的になったとき、ギブアップするのですが、そうすると次の提出・レビューまで何日か待たされます。ようは、自分の書いたものを精査するのにその程度かかるでしょうというのと、無闇にギブアップするなというペナルティなんだと思っています。今の課題はそれが3日間なので、1回失敗すると3日カレンダーが進みます。これが今みたいに期限が迫ってきていると、大きい。
どこまで内部事情を書いていいのかわかりませんが、意外とレビュアーになってくれる人がいないんですよね。したがって、レビュー1回1時間で終わると仮定しても、3時間あれば3回受けられるわけじゃないです。本当に1日1回、2回とかあります。朝から夜までいれば3回いけるかも。人がいないからその辺の人にリアルで頼んでスロットを開けてもらったという話も聞きました。
このレビューというののときに、相手のいる席を見るために相手のプロフィールをチラッと見るんですが、課題の進捗とか以外にも、退学の期限がせまっていると毒々しい真っ赤な字で出るんです。
それで、先日もすごく申し訳なさそうにゼロ点にする方がいました。今日の方も、うん、だいぶプレッシャーかかっていたと思う。
ああ、他人にあんまり変なプレッシャーを掛けるもんじゃないなと思いました。 「これを×にしたらもう退学しかない」というボタンを他人に押させるものではない。そういうのって、得てして本人は憶えてなかったりするもんですが、押した方にとっては傷になるんじゃないかな……。もちろん、それは、その人の42にかける思いの重さにもよるとは思いますが。
(ここで5日経った。)
生き残った
5日前にこれを書いて、いや、さすがに生々しすぎるかなと思って、下書きに入れたのでした。
ま、結局これを書いた翌日くらいに課題をパスして、生き残ったのでした。次の期限は7月くらいだと思います。
なんか無駄なことをしている気がする……と思ったんだけど
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の問題の範囲では多分これはわりとどうでもよいトピックなんだと思う。
AtCoderの次のコンテスト環境のテストが行われていますが……
AtCoderの次のコンテスト環境のテストが行われているので、参加してみています。
しかし、下準備(後述)をし、とりあえず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
vec<u32>の総和はsum<u64>()でもu32の最大値でオーバーフローする
要素がu32型のvecの総和を求める際、いつもはfor式を使い、sum()を使わないのだが、ちょっとかっこつけて使ってみたら失敗したという話です。
和を取るとき、オーバーフローするというのはよくあるのだが、sum()に
そもそも、N=109、A[i]=109 (0≦i<N)みたいな、よくある設定がありますが、あれは符号なし32bit整数型(unsigned int/u32)で計算すると桁あふれすることを狙っている場合があります。
今回の計算の場合以下のように見積もると、32bitでは足りない値が出てきました。そこで最後の総和だけは64bitにしようと考えました。
- Nはlog_2(2*105)=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 bit2105 = 1526 KiB
- 32 bit2105 = 763 KiB
という感じ。ただ、Rustでできるのか知らないけど、ベクトル演算ができるAVX512命令とかで上手く並列化できた場合は一部の計算(乗加算)は速度が倍になるかもしれない。
この例はAtCoder Beginner Contest 246(ABC246)のCである。 この問題の入力は≦109なので、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で。
0回目
今日のバグ作品です。入力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();
AtCoderを始めた
最初の提出の記録が2023-01-05なので、もう4カ月たつし、AtCoder ProblemssのStreakも87 daysだが、まだ灰色である。べつにさぼってるわけではなくて、なにかなければ、ちゃんとABCとARCには参加している。過去問もそれなりに解いていて、リアルタイムで解いたのを含めてAcceptedは360問ある。でも、灰色。ABCのCがコンスタントには解けない。ARCのAがコンスタントには解けない。
私は、以前から、アルゴリズムはよわよわで、ライブラリーやツールの知識だけで生きているところがあったが、あらためて泣きたくなるほど競技プログラミングに向いていないことがわかった。まあ、昔参加したACM ICPCも毎回1次予選で敗退だったけど、42ではわりと困らなかったし、ちょっとはマシになってると思ったんだけどなあ。幻想でした。
やっぱり、42のPiscineはアルゴリズムの勝負じゃなかったんだな。ノウハウの部分が大きかった。作業量をこなせるかが重要っていうか。
うんまあ、でも、がんばります。まだじりじりとだけど上がってるので、頭打ちってわけではないし。
あー、頭がよくなりたいーー。
