2020-01-01から1年間の記事一覧
予選 1時間以上参加した初のマラソン形式のコンテストでした。 Introduction to Heuristics Contestの解説が楽しかった 夜にコンテストに参加するのがしんどく、14:00-が嬉しかった 早解きが苦手なので向いてるかもなぁと思った 本選オンラインだし通ったら…
Rust で この問題 が解きたいですが，C-style for は Rust では煩雑になりがちです． 問題 1 let ans = (0..a.len()) .scan((0, 0), |(right, sum), left| { *right += a[*right..] .iter() .position(|&a| { *sum + a > k || { *sum += a; false } }) .unwr…
第三回アルゴリズム実技検定（PAST 202005）を Rust で実装したものを、ごくかんたんな解説とともにおいておきます。 上級を取得するのに必要な問題だけ解いています。つまり、A - L 問題だけです。 drive.google.com
ABC167 解説は多くの省略を含みます。とくに添え字の範囲は、誤解がないと思われる場合ほぼすべて省略しています。 Rust を使用していますが、名前のインポートは省略されます。自作ライブラリも内容を書かずに使用します。Rust の文法をもった疑似コードだ…
雑な参加記を雑に書く。これは青色になった瞬間の記事で、青色になるまでの記事はまた別に書くかもしれない。なにかの役に立つことはあまり想定していませんが、青色になったばかりの人間の一例の雰囲気をつかむためにでもお役立てください。ABC167です。提…
直感的な、と書いていますが、計算が間に合うことは直感に反すると思います。 問題概要 F - Three Variables Game 非負整数の値をとる変数 に対して、操作を 回行います。 番目の操作は、長さ の文字列 によって表され、指定された 変数のうち一方を 増やし…
はじめに シリーズ一覧 初回の記事 この記事のmemoizeを使用します。 2-3 動的計画法 純粋関数型言語としては、扱いにくいところですね。 探索のメモ化と動的計画法 01 ナップサック問題 愚直 どうせ遅いので、リストの添え字アクセスもそのままにしています…
はじめに Haskellでメモ化再帰が楽にできるようにしてみたかったので、やってみた。競技プログラミングに使えればいい、というぐらい。 型 Ixは Data.Ix.Ix で、Unboxableは Data.Vector.Unboxing.Unboxable です。 memoize :: (Ix i, Unboxable e) => (i, i…
はじめに シリーズ一覧 初回の記事 前回の記事 2-2 貪欲法 硬貨の問題 硬貨の問題 貪欲は畳み込み、という感じがする。 solve cs a = snd $ foldl f (a, 0) cs' where f (r, a) (n, v) = (r - v*q, a + q) where q = min n $ div r v cs' = reverse $ zip cs…
はじめに 前回の続き。 2-1 階乗 こう書くと勝手に多倍長整数を扱っていると推論されるので、10000の階乗ぐらいなら一瞬で吐き出してくれます。 fact 0 = 1 fact n = n * fact (n-1) フィボナッチ数 単純な再帰。 fib n | n <= 1 = n | otherwise = fib (n-1…
はじめに プログラミングコンテストチャレンジブック（通称「蟻本」）を買ったので、Haskellのコードに落とすチャレンジをしようと思います。解説は基本的にしないつもりです。 目標とする計算量が達成できたらOKということにします。バージョンはGHC8.8.3で…
ABC161 D - Lunlun Number が Haskell できれいに解けたので簡単な解説を書いておきます． 問題概要 隣り合う 桁の数字の差の絶対値が 以下であるような正の整数を L数 といいます． 番目に小さい L数 を求めてください． 解答 （提出） main = readLn >>= p…
最近 Nim 言語を用いて競技プログラミングをしている，私の環境を紹介します． はじめに Nim については，Nimを知ってほしい - Qiita とかを見てください．この記事では知っているものとします． バージョンは AtCoder に合わせて 1.0.6 です．バージョン 1.…
2020/03/31 時点での競技プログラミングの環境 参加しているコンテスト AtCoder（cunitac） 使用している言語 Nim 0.13.0 使用しているツール atcoder-tools 入力受け取りコードを自動的に生成できる． 中間形式→コード の変換部分を改変して使用している． …
