2023-01-01から1年間の記事一覧
https://projecteuler.net/problem=3Pythonならこんな風に書きたいところです。 from itertools import count import sys def f(n: int) -> int: for p in count(2): if p * p > n: return n elif n % p == 0: return f(n//p) return n N = int(sys.argv[1])…
https://projecteuler.net/problem=2Pythonならこんな風に書きたいところです。 from __future__ import annotations from typing import Iterator from itertools import takewhile import sys def fibs() -> Iterator[int]: a, b = 1, 1 while True: yield…
https://atcoder.jp/contests/typical90/tasks/typical90_h文字列の中の位置とatcoderのどこまで一致したかを状態にして、その状態がいくつあるかをDPで求めます。 // AtCounter #![allow(non_snake_case)] //////////////////// constants ////////////////…
https://atcoder.jp/contests/abc327/tasks/abc327_fかごを下から順にあげていきます。そうしてx方向にスキャンします。 入力例1で、かごの上が1のとき、かごの左が1、2、3が考えられますが、そのときのりんごの数は、[1, 0, 0]です。かごを1上げたとき、(4,…
https://atcoder.jp/contests/abc327/tasks/abc327_e単なるDPで、を選ぶか選ばないかのときに同じkでRの第1項を記憶しておけばよいです。 // Maximize Rating #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T </t:>…
https://atcoder.jp/contests/abc327/tasks/abc327_dとをエッジと考えてグラフを作り、0の隣を1として矛盾が無いか調べます。 // Good Tuple Problem #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mu</t:>…
MojoはPythonのスーパーセットを目指している高速に動作する言語らしいです。 ここを見ると、インストールできます。https://dev.to/jjokah/getting-started-with-mojo-4985WSL2ならスムーズにインストールできます。インストールできたら、Project Euler 1…
https://atcoder.jp/contests/typical90/tasks/typical90_g二分探索で対象の値より小さくても最も大きい値の位置を探します。 // CP Classes #![allow(non_snake_case)] use std::cmp::min; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -></t:>…
https://atcoder.jp/contests/abc326/tasks/abc326_f奇数番目がy方向に正負のどちらにも行けるので、Aの奇数番目を足し引きしてYになればよいです。、偶数番目がx方向で同様です。 奇数番目を半分に分けると高々20なので、全ての足し引きの結果を得られるの…
https://atcoder.jp/contests/abc326/tasks/abc326_enにたどり着く確率は、0のときにnが出る確率と、1のときにn-1が出る確率と、と考えると、 です。 とすれば、 です。期待値は、 となります。 // ABC Puzzle #![allow(non_snake_case)] //////////////////…
https://atcoder.jp/contests/abc326/tasks/abc326_d左上からABC.を当てはめていき、その時点でおかしくなければ次へ進みます。そうでなければ次の文字を、文字がなくなったら前に戻ります。 // ABC Puzzle #![allow(non_snake_case)] use std::collections:…
https://atcoder.jp/contests/typical90/tasks/typical90_e入力例1で考えると、aを頭から探して、aが一つあるので、その次からbを探して、無いのでcを探して、と最後にたどり着くまで繰り返します。アルファベットを整数に直すと書きやすいです。 // Smalles…
https://atcoder.jp/contests/typical90/tasks/typical90_e多項式の掛け算に時間がかかっているので、Karatsuba法を実装してみました。 最長210msが66msになりました。 // Restricted Digits #![allow(non_snake_case)] use std::cmp::{min, max}; /////////…
https://atcoder.jp/contests/abc325/tasks/abc325_eダイクストラ法ですが、社用車と電車の2つのテーブルが必要です。 // Our clients, please wait a moment #![allow(non_snake_case)] use std::cmp::min; use std::collections::BinaryHeap; ////////////…
https://atcoder.jp/contests/abc325/tasks/abc325_d時刻t以上の商品をPriorityQueueに入れます。PriorityQueueは、終了時間が小さいほうから取り出せるようにします。 // Printing Machine #![allow(non_snake_case)] use std::collections::BinaryHeap; //…
https://atcoder.jp/contests/typical90/tasks/typical90_e入力例1で考えましょう。 1桁目を7で割った余りを考えます。そうすると、1, 4, 2が1回ずつ出てくるので、次のような母関数を考えます。 2桁目は で、これは と同じです。2桁で考えると、 となります…
https://atcoder.jp/contests/typical90/tasks/typical90_d とすれば、 となります。 // Cross Sum #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_l</t:>…
https://atcoder.jp/contests/typical90/tasks/typical90_c要は、木の径（+1）を求める問題ですね。 // Longest Circular Road #![allow(non_snake_case)] use std::collections::VecDeque; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -></t:>…
https://atcoder.jp/contests/abc324/tasks/abc324_e各Sに対し、左からと右からでTと何文字一致するかを調べますが、コードが共通化しにくいのが辛いですね。 // Joint Two Strings #![allow(non_snake_case)] //////////////////// library ///////////////…
https://atcoder.jp/contests/abc324/tasks/abc324_d各平方数に対し、与えられた文字列の並び替えで実現できるかを調べます。 そのとき、各数字の個数を4ビットで表せば、13桁を64ビット以内で表すことができます。 // Square Permutation #
https://atcoder.jp/contests/typical90/tasks/typical90_bxy座標で原点から出発して'('をx方向に1、')'をy方向に1進む、と読み替えれば、x=yより左上に行かないようにするルートがこの問題の答えの一つずつです。カタラン数と同じですね。 先入れ先出しで素…
今度はこのシリーズをRustで解いていきます。https://atcoder.jp/contests/typical90/tasks/typical90_a最適な長さは直ちには見つからないけど、最短の長さを指定したら何分割になるかはすぐに分かるので、二分探索ですね。 // Yokan Party #
https://atcoder.jp/contests/math-and-algorithmRustでだいたい解いたので、一覧にします。 最初の方は抜けていますが、あまりに易しいか同じような問題だったので飛ばしたのだったと思います。アルゴリズムと数学 001 アルゴリズムと数学 003 アルゴリズム…
https://atcoder.jp/contests/abc323/tasks/abc323_f場合分けすればなんとかなりそうですが、場合がものすごく多そうですよね。そこで、A、B、Cの位置関係を変えずに圧縮して、移動回数を数えて、圧縮した分を足せばよいです。 // Push and Carry #
https://atcoder.jp/contests/abc323/tasks/abc323_eある時刻tに曲が終わる確率をDPで求めればよいです。 // Playlist #![allow(non_snake_case)] //////////////////// constances //////////////////// const D: i64 = 998244353; //////////////////// li…
https://atcoder.jp/contests/abc323/tasks/abc323_d1が5個あったとしたら、 (1 + 1) + (1 + 1) + 1 = (2 + 2) + 1 = 4 + 1 となるので、2個に集約できますね。これは5を二進法で表して101で、1の数をカウントしたものですね。 3が3個、6が1個なら、6は3+3な…
https://atcoder.jp/contests/abc322/tasks/abc322_f木を作ってノードにparityをつけて、丸ごと反転するならparityを反転するだけ、という具合に考え方は簡単なんですが。 Rustは、固定の木だとまだなんとかなりますね。 // Vacation Query #
https://atcoder.jp/contests/abc322/tasks/abc322_e状態を各パラメータの値とします。ただし、パラメータはP以上は同じなので、そのパラメータの状態はP+1( // Product Development #![allow(non_snake_case)] use std::cmp::min; //////////////////// con…
https://atcoder.jp/contests/abc322/tasks/abc322_d回転とシフトするだけなので、しらみつぶしでも計算量は微小です。 charのテーブルを使いましたが、2進数を使った方がたぶん簡単でしたね。 // Polyomino #![allow(non_snake_case)] ////////////////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bxランダムにグラフを作ります。1点から少しずつエッジを追加していきます。次に進むノードが既存のノードか新規のノードかを確率で選びますが、新規ノードの確率を少しずつ減らし…
