読者です 読者をやめる 読者になる 読者になる

AGC 010 / Rust関連のメモ

http://agc010.contest.atcoder.jp/
A
奇数が奇数個なら無理。
みんな早すぎじゃないか?
http://agc010.contest.atcoder.jp/submissions/1092027

B
差を見て、5→1のように減っているところを数える。
こういうの本当に苦手だ。
http://agc010.contest.atcoder.jp/submissions/1097636

C
これは本番中に解けなかった。
例えば子→親のパスを通る数が2, 2, 2だとすると、
1, 1, 2 →
1, 0, 1 →
0, 0, 0
という感じで3つペアが作れる。
この「作れるペアの最大」をどうやって求めるのかがわからなかった。
結局min(sum - max, sum / 2)とやればいいという結論に解説等を見て至ったが、自力で思いつくにはどういう思考をたどればいいのかよくわからん。構成ゲーみたいな発想なんだろうか。
http://agc010.contest.atcoder.jp/submissions/1097807
先日のこどふぉでスタックオーバーフローしたので心配だったが、普通に通った。
デフォルトのスタックサイズや拡張方法についても調べた方が良さそうだ。

競技プログラミングの練習はご無沙汰していたが、最近はだいぶ精神状態もマシになったのでまた頑張ろうと思う。

後半は単なるメモ

・cargo install-update -a でcargoでいれたパッケージの更新
これ本体にマージした方がいいと思うんだけど。

・cargo script
というのをいれてみた。競技ではわりと便利な気がする。
デフォルトだとoptimizeされるので
alias rust='cargo script --debug'とすることにした。
また~/.cargo/.cargo/script-cacheにゴミがたまるので、cargo script --clear-cacheで適宜消去する。

・fishのaliasは
alias hoge=' '
funcsave hoge
で設定する。既存関数と同名は不可

・RustのRange( (0..n)みたいなやつ)にはIteratorトレイトが実装してある
別になくてもいいんだけど使ってて楽しい系のやつ。
let vec: Vec = (0..n).map(|_| scanner.nextint()).collect();
みたいな。
僕は最近知ったんだけどこれ常識だったりするんだろうか。

・便利関数iter().sum()はatcoderでは使えない
Rust 1.11以上が必要で、AtCoderは1.07なので。
かわりにiter().fold(0, |acc, &x| acc + x)とすればいいのだがちょっと面倒。
iter().max()は使える。

・struct hoge<'a> {}
RustのLifeTimeをジェネリクスで書くタイプの構造体。
結局IndexMutやイテレータ等参照を持ってる系のものに使うらしいのだが(std::io::Cursorとかmoveするやつもある)、自作structに組み込むのがかなり難しいように思う。
競技プログラミング用のscannerを実装するとき、本当はSplitWhitespaceを持たせたかったんだけど結局usizeを持って自力でSplitした。
要するに構造体のメンバとしてStringとSplit(まあStringへの参照みたいなもん)を持ってるとき、「この2つのライフタイム同じだから安全ですよ!」とコンパイラに伝えてあげればいいのだが、どうすればいいのかよくわからない。
どっかで質問するなりしたほうがいいのだろうか。
まあ今の実装で動いてるから別にそこまで困ってはいないんだけど、ちょっと気になる。