ripity

ripity

    • 解説：パソコン甲子園

    • 競プロ

      主に、想定でない解法

      • 解説：パソコン甲子園

      • 競プロ

    • 固定された記事

    入青の書き散らし

    やっとだ～～～、という感じです。AtCoder における青コーダーになりました。 水色の期間がかなり長かった……。 約 2 年を競プロに費やしてこれですからね、自分よりもっとはやく上に行っている人たちはすごいです。マジで。 特に、自分より年下でデカいレート上昇をしている人は、もはや怖さすらあります。（競技の世界に年下とかいう概念を持ち込むのはあまりよろしくないか。） さて、自分の取り組みにはこれといった独自性もないのでこんな「書き散らし」と称した色変記事を書いているわけで

    ripity

      • ABC250F - One Fourth

        問題リンク：https://atcoder.jp/contests/abc250/tasks/abc250_f 提出コード：https://atcoder.jp/contests/abc250/submissions/37954352 以下では 0-indexed で書きます。 多角形$${p_{(L\bmod N)}p_{(L+1\bmod N)}\cdots p_{(R\bmod N)}}$$を$${P(L, R)}$$、$${P(L, R)}$$の面積を$${S(L

        ripity

        • 2023年ですね

          ラジオ体操といえば「新しい朝が来た」というフレーズが有名ですが、1973 年から 1981 年までは、「新しい年が来た」というフレーズに変わっていたことがあるそうです。粋ですね。 新しい年が来ました。今年もどうぞよろしくお願いします。豆知識は嘘です。

          ripity

          • HACK TO THE FUTURE 2023 予選 参加記

            参加記というよりは解法の紹介が主になりそう。まあいいか。 競技プログラミングをやっている人は「やったこと」の項まで読み飛ばしてください。 HTTFとはだそうです。 これはプログラミングコンテストの中でもヒューリスティックスとかマラソンとか言われるやつで、スコアアタック的なものだと考えてもらえば良いです。今回はいい感じの暗号を考える問題でした（かっ、かっこいい～～！！）。 問題文（引用は一部抜粋）：A - Graphorean (atcoder.jp) 日記一日目：$

            ripity

          マガジン

          マガジンをすべて見る すべて見る
          • 解説：パソコン甲子園
            ripity
          • 競プロ
            ripity

          記事

          記事をすべて見る すべて見る

            ABC276F - Double Chance

            新規性はないです。考察のステップを記しただけなので、実装の解説はありません。 問題リンク：F - Double Chance (atcoder.jp) 方針期待値ではなく、とりあえず確率を求めたい。 数 A の復習 ここは数 A の復習なので、分かる人は飛ばしてください。さて、次の問題を解いてみましょう。 「集合$${S=\{1,2,\cdots,10\}}$$から要素をひとつ選んで記録する」という操作を$${2}$$回行うことを考える。記録した数の最大値が$${5

            ripity

            JOI2009予選F - ビンゴ

            2000msを切れるかと思ったが，残念ながら失敗． 斜め累積和を使っても解くことができます． 解法 問われているのは，次の条件を満たす数列$${A=(A_1,A_2,\cdots,A_{N^2})}$$の数え上げです． すべての$${i=1,2,\cdots,N^2-1}$$に対して，$${A_i\lt A_{i+1}}$$． すべての$${i=1,2,\cdots,N^2}$$に対して，$${1\le A_i\le M}$$． $${\sum_{1\le i\l

            ripity

            JOI2017/2018予選D - 水ようかん (Mizuyokan)

            $${SN^2\log S\ (S=\sum_i L_i)}$$解法です．高速な言語でゴリ押そう！ 解法 切り分ける際に，「どの羊羹の長さも$${L}$$以上$${R}$$以下になるようにする」という制約をつけてみます．このとき，制約を満たす切り分け方が存在した場合に$${R-L+1}$$が回の候補になります． $${L}$$を固定して考えます．すると，制約を満たす切り分け方は，$${R}$$の値に対して単調性があります（$${R}$$が大きいほど切り分けに成功しやすい

            ripity

            ABC270E - Apple Baskets on Circle の Bonus 解法

            $${A}$$を昇順にソートした配列を$${B}$$と置きます．また，簡単のため，$${B_0=0}$$とします． $${i=1,2,\cdots,N}$$の順で，次の手順を行います． $${D=B_i-B_{i-1}, L=N-i+1}$$とする． $${D\times L\lt K}$$のとき： $${K}$$から$${D\times L}$$を引く． $${D\times L\ge K}$$のとき： $${F=\mathrm{floor}(K/L)}$$とす

            ripity

            パソコン甲子園2022に参加しました

            本来は名前だけ貸して出ないつもりだったのですが（模試の日だったので）、なんか出たくなったので出ました。 参加前 普段は Kotlin を書いているので Java の記述が煩雑に思えるが、仕方ないので練習する。とりあえずセグ木と平方分割を実装して感覚を取り戻す。 あと模試を自宅受験する旨を伝えに行く。リスニングは学校でやることになったが、所定の時間に遅刻したため、クソ蒸し暑い教室で後々やることに。 当日 集合時間に５分ほど遅刻するも、予選開始までは１時間ほどあるのでノ

            ripity

            期待値DPのメモ

            $${K}$$面のサイコロを振って$${N}$$マスの双六をゴールするとき、サイコロを振る回数の期待値を求めたい（マス$${N,N+1,\cdots}$$をゴールとする）。 $${E_i=}$$（マス$${i}$$からゴールするとき、サイコロを振る回数の期待値）とする。このとき、 $${i\ge N}$$のとき：$${E_i=0}$$ $${i\lt N}$$のとき：$${E_i=\sum_{1\le k\le K} (E_{i+k}+1)/K=1+\sum_{1\le

            ripity

            ABC263D - Left Right Operation

            問題リンク 解法 $${dp[i][j]\ (1\le i\le N, 1\le j\le 3)}$$を以下で定める。 $${dp[i+1][0]=dp[i][0]+L}$$ $${dp[i+1][1]=\min(dp[i][0], dp[i][1])+a[i+1]}$$ $${dp[i+1][2]=\min(dp[i][1], dp[i][2])+R}$$ ただし、 $${dp[1][0]=L, dp[1][1]=a[1], ap[1][2]=R}$$ このとき、$

            ripity

            ABC252D - Distinct Trio

            問題文リンク 概要 整数列$${a=(a_1,a_2,\dots,a_N)}$$が与えられます。$${a_i,a_j,a_k}$$が相異なるような添え字の組$${(i,j,k) (i\le j\le k)}$$の個数を求めてください。 制約 $${3\le N\le 2\times10^5}$$ $${1\le a_i\le 2\times10^5 (1\le i\le N)}$$ 解法$${a}$$は適当な座標圧縮がされていると仮定します。これにより、制約が

            ripity

            PCK2021G（予選）- ミックススパイス 2 / Mixed Spice II

            AOJ に解説がない PCK の問題の解説です。最後には Java での実装例のリンクが張ってあります。（更新：今はあるみたいです） 決め打ち二分探索を知っていますか？僕は知っています。 頻出のテクなので知っておきましょう！ 問題文リンク 概要 整数$${C}$$、および長さ$${N}$$の整数列$${a,b,x}$$が与えられます。以下の条件をすべて満たす長さ$${N}$$の整数列$${b'}$$を考えます。 $${0\le b'_i}$$ $${\sum_{i

            ripity

            CR789C (Div.2) - Tokitsukaze and Strange Inequality

            やることは典型ですが、面白かったので解法を書き留めます。 使う知識は imos 法と集合に関する基礎的なものです。 問題文リンク 概要 $${(1,2,\dots,N)}$$の順列$${p}$$が与えられます。$${p_a\lt p_c}$$かつ$${p_b\gt p_d}$$を満たす添え字の組$${(a,b,c,d)(1\le a\lt b\lt c\lt d\le N)}$$を数え上げてください。 制約 $${4\le N\le 5000}$$ $${p}$$

            ripity

            CR713D (Div. 2) - Corrupted Array

            自明な上界を見積もるヤツです。 問題概要 整数$${n}$$と数列$${b=(b_1,b_2,\dots,b_{n+2})}$$が与えられます。 以下の手順で$${b}$$を生成できるような数列$${a=(a_1,a_2,\dots,a_n)}$$を$${1}$$つ構築してください。または、そのような$${a}$$が存在しないことを報告してください。 各$${i=1,2,\dots,n}$$について、$${b_i=a_i}$$とする $${b_{n+1}=\sum a

            ripity

            AGC056A - Three Cells per Row and Column

            $${ 2 }$$つの公式解説のどちらとも方針が違ったため、自分が取った方針・解法を書こうと思います。 （ごちゃごちゃ実験をしてたらできた解法なので、少し実装が煩雑です。ご了承ください。） 解法とりあえず $${ 3 }$$つの条件のうち、上の$${ 2 }$$つを満たすものをまず考えます。 これは、$${3 \times 3 }$$の黒い正方形を斜めの一直線上に配置していき、盤面の端っこで調整をすることで可能です。「調整」のイメージは以下のものです。この状態を「盤面A」

            ripity