いかたこのたこつぼ
https://ikatakos.com/pot/
2024-03-19T13:20:51+00:00
FeedCreator 1.8 (info@mypapit.net)
AtCoder Regular Contest 174 C,E 問題メモ - [解法]
2024-03-19T09:52:58+00:00
2024-03-19T09:52:58+00:00
https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2024/0317_arc174
ikatakos
ikatakos@undisclosed.example.com
AtCoder Regular Contest 174 C,E 問題メモ
AtCoder Regular Contest 174
速解き回のようで速解き回でない、少し速解き回のARC
C - Catastrophic Roulette
C - Catastrophic Roulette
問題
* $1~N$ の目が等確率で出るルーレットがある
* 先手と後手がゲームをする$\mod{998244353}$$1 \le N \le 10^6$$i$$P_i$$Q_i$$P_0=0,Q_0=0$$i-1$$i$$\dfrac{i}{N}$$i-1$$Q_{i-1}$$P_{i-1}$$\dfrac{N-i}{N}$$i$$Q_i+1$$P_i$$P_i=\dfrac{i}{N}Q_{i-1}+\dfrac{N-i}{N}(Q_i+1)$$Q_i=\dfrac{i}{N}P_{i-1}+\dfrac{N-i}{N}P_i$$Q_i$$P_i$$P_{i-1},Q_{i-1}$$Q_i$$i$$P_N,Q_N$$1,...,N$$K$${}_NP_K$$P=(P_1,...…
AtCoder Regular Contest 174 C,E 問題メモ
AtCoder Regular Contest 174
速解き回のようで速解き回でない、少し速解き回のARC
C - Catastrophic Roulette
C - Catastrophic Roulette
問題
* $1~N$ の目が等確率で出るルーレットがある
* 先手と後手がゲームをする$\mod{998244353}$$1 \le N \le 10^6$$i$$P_i$$Q_i$$P_0=0,Q_0=0$$i-1$$i$$\dfrac{i}{N}$$i-1$$Q_{i-1}$$P_{i-1}$$\dfrac{N-i}{N}$$i$$Q_i+1$$P_i$$P_i=\dfrac{i}{N}Q_{i-1}+\dfrac{N-i}{N}(Q_i+1)$$Q_i=\dfrac{i}{N}P_{i-1}+\dfrac{N-i}{N}P_i$$Q_i$$P_i$$P_{i-1},Q_{i-1}$$Q_i$$i$$P_N,Q_N$$1,...,N$$K$${}_NP_K$$P=(P_1,...…
モノグサプログラミングコンテスト2024(AtCoder Beginner Contest 345)E 問題メモ - [解法]
2024-03-19T06:26:00+00:00
2024-03-19T06:26:00+00:00
https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2024/0316_abc345
ikatakos
ikatakos@undisclosed.example.com
モノグサプログラミングコンテスト2024(AtCoder Beginner Contest 345)E 問題メモ
モノグサプログラミングコンテスト2024(AtCoder Beginner Contest 345)
E - Colorful Subsequence
E - Colorful Subsequence
問題
* $N$ 個のボールが1列に並び、$i$ 番目のボールは色 $C_i$、価値 $V_i$
* ちょうど $K$ 個のボールを取り除き、同じ色のボールが連続しないようにしたい$1 \le N \le 2 \times 10^5$$1 \le K \le \min(N,500)$$DP[i,j]=i$$j$$i$$DP[6,3]$$DP[5,3],DP[4,2],...$$i$$C_i \neq C_6$$V_6$$O(NK)$$O(K)$$O(NK^2)$$DP2[i,j,k]=DP[i,*]$$(i,j)$$k=0$$k=1$$k=2$$DP[6,3]$$DP2[5,3,*]$$DP2[5,3,1]$$C_6$$DP2[5,3,2]$$DP1[5,3…
モノグサプログラミングコンテスト2024(AtCoder Beginner Contest 345)E 問題メモ
モノグサプログラミングコンテスト2024(AtCoder Beginner Contest 345)
E - Colorful Subsequence
E - Colorful Subsequence
問題
* $N$ 個のボールが1列に並び、$i$ 番目のボールは色 $C_i$、価値 $V_i$
* ちょうど $K$ 個のボールを取り除き、同じ色のボールが連続しないようにしたい$1 \le N \le 2 \times 10^5$$1 \le K \le \min(N,500)$$DP[i,j]=i$$j$$i$$DP[6,3]$$DP[5,3],DP[4,2],...$$i$$C_i \neq C_6$$V_6$$O(NK)$$O(K)$$O(NK^2)$$DP2[i,j,k]=DP[i,*]$$(i,j)$$k=0$$k=1$$k=2$$DP[6,3]$$DP2[5,3,*]$$DP2[5,3,1]$$C_6$$DP2[5,3,2]$$DP1[5,3…
std::setを使わない代替テクニック - [std::setを使わない代替テクニック]
2024-03-19T01:49:26+00:00
2024-03-19T01:49:26+00:00
https://ikatakos.com/pot/programming_algorithm/data_structure/balancing_binary_search_tree/tree_free
ikatakos
ikatakos@undisclosed.example.com
std::setを使わない代替テクニック
競技プログラミングでは、C++ に std::set という(事実上)平衡二分探索木ライブラリがあるから、たまにその使用を前提とした問題が出る。
std::set, multiset は、集合を順序を持って管理するデータ構造であり、以下のことができる($O(\log{N})$$O(\log{N})$$O(\log{N})$$O(\log{N})$$1~10^6$$O(\log{N})$$k$$O(\log{N})$$x$$O(\log{N})$$x$$O(\log{N})$$x$$bit.add(x, 1)$$x$$bit.add(x, -1)$$k$$bit.lower\_bound(k)$$k$$x$$bit.sum(x)-bit.sum(x-1) \gt 0$$x$$bit.lower\_bound(bit.sum(x))$$x$$bit.lower\_bound(bit.sum(x - 1) + 1)$$x$$1$$x$$N+1$$i=1$$i=2$$N=10^6$$1~N$$k$$k \pm 1$$k$$x$$x$$L[k]$$L…
std::setを使わない代替テクニック
競技プログラミングでは、C++ に std::set という(事実上)平衡二分探索木ライブラリがあるから、たまにその使用を前提とした問題が出る。
std::set, multiset は、集合を順序を持って管理するデータ構造であり、以下のことができる($O(\log{N})$$O(\log{N})$$O(\log{N})$$O(\log{N})$$1~10^6$$O(\log{N})$$k$$O(\log{N})$$x$$O(\log{N})$$x$$O(\log{N})$$x$$bit.add(x, 1)$$x$$bit.add(x, -1)$$k$$bit.lower\_bound(k)$$k$$x$$bit.sum(x)-bit.sum(x-1) \gt 0$$x$$bit.lower\_bound(bit.sum(x))$$x$$bit.lower\_bound(bit.sum(x - 1) + 1)$$x$$1$$x$$N+1$$i=1$$i=2$$N=10^6$$1~N$$k$$k \pm 1$$k$$x$$x$$L[k]$$L…
トヨタ自動車プログラミングコンテスト2024#3(AtCoder Beginner Contest 344)F,G 問題メモ - [解法]
2024-03-15T04:40:55+00:00
2024-03-15T04:40:55+00:00
https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2024/0309_abc344
ikatakos
ikatakos@undisclosed.example.com
トヨタ自動車プログラミングコンテスト2024#3(AtCoder Beginner Contest 344)F,G 問題メモ
トヨタ自動車プログラミングコンテスト2024#3(AtCoder Beginner Contest 344)
F - Earn to Advance
F - Earn to Advance
問題
* $N \times N$ グリッドを左上 $(1,1)$ から右下 $(N,N)$ まで移動する
* はじめ、所持金は0
* マス $(i,j)$ では以下の3種類の行動を行える$P_{i,j}$$R_{i,j}$$D_{i,j}$$2 \le N \le 80$$P_{i,j}$$R_{i,j}$$DP[i,j,k,l]=(1,1)$$(i,j)$$P_{k,l}$$C_①,C_②$$0 \le C_①,C_② \lt P_{k,l}$$C_②+P_{k,l} \gt C_①$$C_②$$P_{k,l}$$O(N^4)$$N$$Q$$y=A_i x + B_i$$Q$$Q$$A_i,B_i$$1 \le N \le 5000$$1 \le Q…
トヨタ自動車プログラミングコンテスト2024#3(AtCoder Beginner Contest 344)F,G 問題メモ
トヨタ自動車プログラミングコンテスト2024#3(AtCoder Beginner Contest 344)
F - Earn to Advance
F - Earn to Advance
問題
* $N \times N$ グリッドを左上 $(1,1)$ から右下 $(N,N)$ まで移動する
* はじめ、所持金は0
* マス $(i,j)$ では以下の3種類の行動を行える$P_{i,j}$$R_{i,j}$$D_{i,j}$$2 \le N \le 80$$P_{i,j}$$R_{i,j}$$DP[i,j,k,l]=(1,1)$$(i,j)$$P_{k,l}$$C_①,C_②$$0 \le C_①,C_② \lt P_{k,l}$$C_②+P_{k,l} \gt C_①$$C_②$$P_{k,l}$$O(N^4)$$N$$Q$$y=A_i x + B_i$$Q$$Q$$A_i,B_i$$1 \le N \le 5000$$1 \le Q…
AtCoder Regular Contest 173 A,B,C,D問題メモ - [解法]
2024-03-14T01:01:57+00:00
2024-03-14T01:01:57+00:00
https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2024/0310_arc173
ikatakos
ikatakos@undisclosed.example.com
AtCoder Regular Contest 173 A,B,C,D問題メモ
AtCoder Regular Contest 173
ケアレスな実装ミスでタイムロスしちまうのはなおらないねえ。
A - Neq Number
A - Neq Number
問題
* ある正整数 $X$ を(先頭に0のつかない)十進法表記した際に、同じ数字が隣り合わない場合、$X$$K$$T$$1 \le T \le 100$$1 \le K \le 10^{12}$$d$$1~9$$d-1$$0~9$$9^d$$d$$K$$9^{未定桁数}$$i$$0,1,2,...,9$$B=10$$K_{max}$$D$$D=14~15$$O(BD)$$N$$3 \le N \le 300$$\left \lfloor \dfrac{N}{3} \right \rfloor$$L$$C$$L$$L$$L$$N-C$$\min(\left \lfloor \dfrac{N}{3} \right \rfloor,N-C)$$ax+by+c=0$$a,b,c$$c$$\dfrac{c(c-1)}{2}$$…
AtCoder Regular Contest 173 A,B,C,D問題メモ
AtCoder Regular Contest 173
ケアレスな実装ミスでタイムロスしちまうのはなおらないねえ。
A - Neq Number
A - Neq Number
問題
* ある正整数 $X$ を(先頭に0のつかない)十進法表記した際に、同じ数字が隣り合わない場合、$X$$K$$T$$1 \le T \le 100$$1 \le K \le 10^{12}$$d$$1~9$$d-1$$0~9$$9^d$$d$$K$$9^{未定桁数}$$i$$0,1,2,...,9$$B=10$$K_{max}$$D$$D=14~15$$O(BD)$$N$$3 \le N \le 300$$\left \lfloor \dfrac{N}{3} \right \rfloor$$L$$C$$L$$L$$L$$N-C$$\min(\left \lfloor \dfrac{N}{3} \right \rfloor,N-C)$$ax+by+c=0$$a,b,c$$c$$\dfrac{c(c-1)}{2}$$…
DEGwer さんの D 論応援コンテスト B問題メモ - 作成
2024-03-13T16:45:53+00:00
2024-03-13T16:45:53+00:00
https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2023/1202_degwer2023
ikatakos
ikatakos@undisclosed.example.com
DEGwer さんの D 論応援コンテスト B問題メモ
DEGwer さんの D 論応援コンテスト
B - vs. DEGwer
B - vs. DEGwer
問題
* $H \times W$ のグリッド上に部屋が並んでいる
* 上下左右に隣接する部屋の間に扉があり、互いに繋がっている
* 一番左列の部屋の左側にそれぞれ扉があり、入口となる大部屋 $S$$T$$S$$T$$H,W$$1 \le H,W \le 20$$S,T$$S$$T$$S,T$$H \times (W+1) + (H-1) \times W=2HW+H-W$$HW+2$$2HW+2$$2HW+H-W \ge 2HW+2$$H \ge W+2$$H \ge W+2$$H = W+1$$H \ge W+2$$H = W+1$$H \le W$$H = W+1$$H,W$$H \ge W+3$…
DEGwer さんの D 論応援コンテスト B問題メモ
DEGwer さんの D 論応援コンテスト
B - vs. DEGwer
B - vs. DEGwer
問題
* $H \times W$ のグリッド上に部屋が並んでいる
* 上下左右に隣接する部屋の間に扉があり、互いに繋がっている
* 一番左列の部屋の左側にそれぞれ扉があり、入口となる大部屋 $S$$T$$S$$T$$H,W$$1 \le H,W \le 20$$S,T$$S$$T$$S,T$$H \times (W+1) + (H-1) \times W=2HW+H-W$$HW+2$$2HW+2$$2HW+H-W \ge 2HW+2$$H \ge W+2$$H \ge W+2$$H = W+1$$H \ge W+2$$H = W+1$$H \le W$$H = W+1$$H,W$$H \ge W+3$…
点位置決定問題 - [二分木・四分木]
2024-03-13T02:56:49+00:00
2024-03-13T02:56:49+00:00
https://ikatakos.com/pot/programming_algorithm/geometry/planar_point_location
ikatakos
ikatakos@undisclosed.example.com
点位置決定問題
* ポリゴンで分割された2次元平面があります
* ポリゴンは互いに重ならない、どのポリゴンにも属さないエリアは無い
* 平面にある点が落とされました
* 落ちたのはどのポリゴンですか?$O(NM)$$O(NM)$$u$$x=k$$v,w$$u$$(x,y)$$x$$(x_i,y_i)$$x_i$$y_i$$O(P^2)$$O(P^2)$$O(\log{P})$$\frac{P}{2}$$\frac{P}{2}$$x$$O(P)$$O(P)$$O(P \log{P})$$O(P)$$O(\log{P})$
点位置決定問題
* ポリゴンで分割された2次元平面があります
* ポリゴンは互いに重ならない、どのポリゴンにも属さないエリアは無い
* 平面にある点が落とされました
* 落ちたのはどのポリゴンですか?$O(NM)$$O(NM)$$u$$x=k$$v,w$$u$$(x,y)$$x$$(x_i,y_i)$$x_i$$y_i$$O(P^2)$$O(P^2)$$O(\log{P})$$\frac{P}{2}$$\frac{P}{2}$$x$$O(P)$$O(P)$$O(P \log{P})$$O(P)$$O(\log{P})$
同一直線上に並ぶ点のカウント - [$O(N^2)$ 解法]
2024-03-13T01:02:45+00:00
2024-03-13T01:02:45+00:00
https://ikatakos.com/pot/programming_algorithm/geometry/collinear_points
ikatakos
ikatakos@undisclosed.example.com
同一直線上に並ぶ点のカウント
問題設定
* 2次元平面上の $N$ 点の座標が与えられる
* (1) 同一直線上に並んでいる3点組の個数を求めよ
* (2) 最も多くの点を通る直線(複数ある場合はその一例)と、通る点の個数を求めよ$|x|,|y| \le 10^9$$i,j$$i \lt j$$L$$j \lt k$$L$$k$$i,j$$\dfrac{1}{2}|(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)|$$A→B$$B→C$$ax+by+c=0$$(a,b,c)$$(x_1,y_1),(x_2,y_2)$$d_x=x_2-x_1,d_y=y_2-y_1$$d_yx - d_xy + (d_xy_1 - d_yx_1)=0$$(a,b,c)$$d_x$$d_y$$d_x$$d_x,d_y$$-1$$d_x$$d_y$$d_y$$(a,b,c)$$k$$\dfrac{k(k-1)}{2}$$O(N^2)$$k$${}_kC_{3}$…
同一直線上に並ぶ点のカウント
問題設定
* 2次元平面上の $N$ 点の座標が与えられる
* (1) 同一直線上に並んでいる3点組の個数を求めよ
* (2) 最も多くの点を通る直線(複数ある場合はその一例)と、通る点の個数を求めよ$|x|,|y| \le 10^9$$i,j$$i \lt j$$L$$j \lt k$$L$$k$$i,j$$\dfrac{1}{2}|(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)|$$A→B$$B→C$$ax+by+c=0$$(a,b,c)$$(x_1,y_1),(x_2,y_2)$$d_x=x_2-x_1,d_y=y_2-y_1$$d_yx - d_xy + (d_xy_1 - d_yx_1)=0$$(a,b,c)$$d_x$$d_y$$d_x$$d_x,d_y$$-1$$d_x$$d_y$$d_y$$(a,b,c)$$k$$\dfrac{k(k-1)}{2}$$O(N^2)$$k$${}_kC_{3}$…
QGISで変数を使用した複数レイヤの描画条件の一括変更
2024-03-13T00:54:46+00:00
2024-03-13T00:54:46+00:00
https://ikatakos.com/pot/software/qgis/variable
ikatakos
ikatakos@undisclosed.example.com
QGISで変数を使用した複数レイヤの描画条件の一括変更
環境
* Windows10/11
* QGIS 3.34
概要
* 複数レイヤに対して、同じ文字列を条件として、フィルタや色分けなどの描画条件を指定している
QGISで変数を使用した複数レイヤの描画条件の一括変更
環境
* Windows10/11
* QGIS 3.34
概要
* 複数レイヤに対して、同じ文字列を条件として、フィルタや色分けなどの描画条件を指定している