エンジンの勉強として１週間でゲームを作成する Jam に参加してみました。 １週間じゃ想定していた工程の３割しか終わらないことを体感し、打ちひしがれた RRRRRRRRespawn by nebocco 今は完全に燃え尽きています、楽しかった～

こんにちは、ねぼこです。 adventar.org ととりにゃあ Advent Calendar 2021、8日目です。 毎日進捗 アトリのトトリエ 〜アーランドの錬金術士2〜 あとりにゃあ アトリ科 Fringillidae アトリ科（アトリか、学名 Fringillidae）は、鳥類スズメ目の科である。…

浮動小数点数に直して $\arg$ 求めるの嫌いなので整数のままソートしましょう。 偏角の取りうる範囲は $[0, 2 \pi )$ とします。 追記 投稿直後にもっと賢い方法が投稿され、膝から崩れ落ちました ngtkana.hatenablog.com ソートする時には、二点 $p = (p _ …

みんなはちゃんと証明しましょう 問題 リンクはこちら 解法 現在の出目が $i$ の時、出目を $T$ に変える最適な戦略でかかる合計コストを $C(i)$ と書くことにします。 戦略はゴールまで増やし続けるか一旦振り直すかです。 振り直した後にかかるコストの期…

文字列に含まれる文字の種類数を $σ$ とおきます。 $O(N2^{σ})$ で解きます。 問題 リンクはこちら 解法 $σ = 1$ まずは $σ = 1$ の場合を考えてみましょう。このとき答えは明らかに $2^{N} - 1$ です。これをDPで解いてみることにします。配列 $g[i] \colon…

初めてのWebアプリを作りました。 twst-simulator.herokuapp.com プログラミングをやっているからにはいつかWebの技術も触りたいなあ、と思いながらも特に作るアイデアもなくのうのうと過ごしていましたが、ふとこれを思いついたので作ってみました。 これの…

競技プログラミング作問支援ツール Rime を Windows10 で使えるように改造しましょう！ rime Mac なんかに……負けないっ……！ おことわり 作業にあたって Rime 非公式ドキュメント を大いに参考にさせていただきました。基本的にはここのチュートリアルに従い…

AtCoderの提出詳細で見れるコードは、デフォルトでタブ幅が8に固定されています。 見にくいね 作りました。 AtCoder Tab 4matter 2021/05/03 追記 TamperMonkey から Stylus に移行しました。 AtCoder Tab 4matter 見やすいね 嬉しい～～

余談が本編 問題 リンクはこちら 概要 $N$ 個の国があり、それぞれの国 $i \; (0 \leq i < N)$ に対して以下の行動のうち一つを選ぶ。 選択 $p$ : ツアー旅行に行く。利得 $b_i$ 選択 $q$ : 個人旅行に行く。利得 $c_i$ 選択 $r$ : 行かない。利得 $0$ ただ…

$O(N)$ で解きます。$O(N \log N)$ はこちら 問題 問題ページ 概要 $$ \max _ {1 \leq l \leq r \leq n} \left\lbrace (r - l + 1) \cdot \min _ {l \leq i \leq r} a _ i \right\rbrace $$ 解法 前回の続きです。今回は皿の大きさ順ではなく、シンプルに左…

$O(N \log N)$ で解きます。$O(N)$ はこちら 問題 問題ページ 概要 $$ \max _ {1 \leq l \leq r \leq n} \left\lbrace (r - l + 1) \cdot \min _ {l \leq i \leq r} a _ i \right\rbrace $$ 解法 以下では、載っているミカンが多い皿を「大きい皿」、少ない…

$O(N+M)$ で解きます。 問題 リンクはこちら 概要 $N$ 頂点 $M $ 辺の有向グラフが与えられる。極小のサイクルを一つ見つけよ。 解法 問題文に書かれている条件は「概要」のように言い換えることができます。editorialでは 最小のサイクルを見つける サイク…

$ O(M ^ 2) $ (一般の $N, M $ については $ O(NM ^ 2) $ ) で解きます。 問題 リンクはこちら 概要 $N$ 個のスイッチと $M $ 個の電球がある。$i$ 番目のスイッチ $ (1\leq i\leq N) $ は $ k _ i $ 個の電球 $s _ {i1},s _ {i2},\ldots,s _ {ik _ i}(1 \le…

\(O(N \log N)\) で解きます。 問題 リンクはこちら 概要 与えられる点の集合 \(S\) の中から二点を選ぶとき、それらを結んだ直線の傾きが \(-1\) 以上 \(1\) 以下になる組み合わせはいくつあるか？ 解法 editorial解は単純にすべてのペアについて調べるだけ…

\(O(N )\) で解きます。 問題 リンクはこちら 概要 $$ \sum _ {l = 1} ^ N \sum _ {r = l} ^ N \mathrm{min} \left( a _ l, a _ {l + 1} , \ldots , a _ r \right) $$ を求めなさい。 解法 editorial解は平衡二分木を用いたものです。Pythonの標準ライブラリ…

\(O( \log N )\) で解きます。 問題 リンクはこちら 解法 editorialのDP解法をベースに考えます。 \(i\) 文字目を決める際の遷移は \(i\) の値によらず常に固定なので、漸化式を行列の累乗に落とし込むことができます。64次元線形空間の行列を手書きで入力す…

\(O(N)\) で解きます。 問題 リンクはこちら 概要 $$ \underset{P}{\min} \sum _ {i=1} ^ {N} (X _ i - P) ^ 2 $$ を求めなさい。 解法 制約が \( N \leq 100,\ X _ i \leq 100\) と小さいので、 \(X\) の取りうる範囲すべてを調べても \(O(NA) \, (A = \max…

\(O(N \log K )\) で解きます。また、本問題の「与えられたグラフが巡回置換に分解できる」という特性をほとんど用いていないので、 \(P\) が順列でない場合でも少し書き換えるだけで解くことができます。 問題 リンクはこちら 解法 ダブリングで前処理をし…

Qiitaに投稿しました。 qiita.com

\(O(\sqrt N )\) で解きます。 問題 リンクはこちら 概要 $$ \sum _ {i=1} ^ {N} i \cdot \mathit{d}(i) $$ を求めなさい。 解法 公式editorialの \(O(N)\) 解法を高速化することを考えたいです。結局、 \(S[k] := \sum _ {i=1} ^ {k} i\) として $$ \sum _ …

公式解説が分かりづらかったので 問題 リンクはこちら 概要 $$ \sum _ {i=0} ^ {n-1} \sum _ {j=i+1} ^ n \mathrm{lcm}(A _ i, A _ j) $$ を求めなさい。 解法 以下、計算は素数mod上で行うため、何かで割る操作は逆元を掛けているものだと思ってください。 …