2021-01-01から1年間の記事一覧
こんにちは、ねぼこです。 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解は単純にすべてのペアについて調べるだけ…