Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

技術室奥プログラミングコンテスト#4 Day1 反省会

技術室奥プログラミングコンテスト#4 Day1 - AtCoder

A

大きいサイドのやつは、Wより大きい微小な数を足すだけでいいじゃんまではわかったけど、以上はわからず謎の解答を出したが、なぜか通った。

B

正しく書けず3回WAした。これって、配列にKを入れてからソートして、Kの位置を探索するということにしたら簡潔だったかも知れない。

D

問題を理解出来なかった。絶対値で書いてあるというのが何かの間違いだと思いこんでいた。最後の方になって気づいたが、気持ちがもうだめだった。

紛れのない実装としては、各点について前との傾き、後ろとの傾きの2本の配列を用意してしまい、計算して、異なってる場合は採用というものが考えられるかなと思った。1本の配列で実装すると、実装を失敗しそう。

問題の性質的に端点は絶対に採用だけど、上の枠組みで実装するならば、端点の横に同じ値の点をくっつければ、題意を破壊せずにきれいに書けると思う。

G

解法は違うけど、例外を除いては3をとるのが良いという事実に気づけたのは良かった。

// log3 / log2 > 3 / 2 

エディトリアルは、6で区切ってやってるけど、自分はこういう感じで「4は22でとるのが最強だから例外扱い」という実装をした。

        let mut remaining = q; // >= 5
        let mul = if (remaining - 4) % 3 == 0 { // 7, 10
            let k = (remaining - 4) / 3;
            4 * modpow(3, k, p)
        } else if (remaining - 2) % 3 == 0 { // 5, 8, 11
            let k = (remaining - 2) / 3;
            2 * modpow(3, k, p)
        } else { // 6, 9, 12
            let k = remaining / 3;
            modpow(3, k, p)
        };

H

プライオリティキューを使ったダイクストラ法を、題意に沿うように変更すればいいだけだと思ったが、Rust標準ライブラリはmax-heapを提供していて、その順序を逆にするためにtraitを実装していたのだけど、これが1.15でコンパイル出来ず、泣いた。最新コンパイラでサンプルが通る実装だけはした。1.15では、値を逆にしてmax-heapをmin-heapに解釈するという、あとで見て混乱しそうな実装をする必要がある。コンテスト後に書き換えたけど、コンパイラのバージョンが上がったらまた書き戻すと思う。

I

問題を読んでみると良問に見えるが、Hで泣いてしまったため、コンテスト中に手を着けなかった。あとでやりたい。

TBD