競技プログラミング総合スレ 66

1 ：デフォルトの名無しさん ：2023/03/22(水) 15:19:42.08 ID:9X0hpeOca.net

!extend:checked:vvvvv:1000:512
!extend:checked:vvvvv:1000:512
!extend:checked:vvvvv:1000:512
↑2行になるようにする

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder https://atcoder.jp/
yukicoder https://yukicoder.me/
Codeforces https://codeforces.com/
CodeChef https://codechef.com/
Project Euler https://projecteuler.net/
CLIST https://clist.by/
AtCoder Problems https://kenkoooo.com/atcoder/
AtCoder Clans https://kato-hiro.github.io/AtCoderClans/

※前スレ
競技プログラミング総合スレ 65
https://mevius.5ch.net/test/read.cgi/tech/1672026457/ VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

---

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

153 ：デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk)：2023/04/08(土) 15:43:15.50 ID:YDsW15QlM.net

>>152
その辺の人でも楽しめる競技になる道は閉ざされそうで悲しいな
元々運営にそういうモチベなさそうだったが（金のために仕方なくやってる感満載だった）

154 ：デフォルトの名無しさん (ﾜｯﾁｮｲ c6ca-HjNm)：2023/04/08(土) 19:32:52.09 ID:jzMk6Pp80.net

ノーレートで、食事したり飲みながら今までほぼ開かなかったF,GとかをchatGTPに聞いたり調べたりしながらやるのも楽しいぞい。解きたくない問題は解かなくても良いし。

155 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/08(土) 20:03:48.77 ID:RgGs2QbX0.net

ワーシャル・フロイドアルゴリズムについて質問です。

最終的に任意の2点間の最短距離を入れるための2次元配列は、
代入演算子の左右で共通のものが使われています。
それでも、問題がないのはなぜですか？

156 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 85a4-5f+B)：2023/04/08(土) 20:09:47.90 ID:8rEHJkBb0.net

ワーシャル・フロイドアルゴリズムは、全ての頂点間の最短距離を求めるためのアルゴリズムです。このアルゴリズムは、動的計画法の一種であり、一度計算された結果を再利用することで、計算量を減らすことができます。

具体的には、アルゴリズムの初期段階で、すべての頂点の間の距離を表す2次元配列を作成します。この配列は、アルゴリズムの途中で更新されますが、代入演算子の左右で共通のものが使われるため、問題はありません。

なぜなら、アルゴリズムの途中で更新される値は、それ以前の値に依存しているため、代入演算子の左右で共通の2次元配列を使用していることによって、更新された値が正しく計算され、以前に計算された値が失われることはありません。

つまり、更新された値は、以前に計算された値に基づいて正確に計算され、以前に計算された値が配列内に保持され続けるため、代入演算子の左右で共通の2次元配列を使用することは、アルゴリズムの正しい動作に影響を与えないということです。

157 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/08(土) 21:36:51.70 ID:RgGs2QbX0.net

>>155

大丈夫な理由が分かりました。

158 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)：2023/04/08(土) 22:06:19.33 ID:8FTHKj1c0.net

chatGPT便利だろ
こういう風に答えてくれる

159 ：デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/)：2023/04/08(土) 22:12:19.75 ID:dzO9pS9o0.net

ものすごくもっともらしい嘘つくから知らないことを聞くのはおすすめしないぞ

160 ：デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/)：2023/04/08(土) 22:16:56.23 ID:dzO9pS9o0.net

ワルシャワ・フローラル法を知ってる？

はい、ワルシャワ・フローラル法は、グラフの最大マッチングを求めるアルゴリズムの一種です。このアルゴリズムは、ハンガリー人数学者であるエドモンド・ワルシャワと、ポーランド人数学者であるタデウシュ・フローラルによって開発されました。

ワルシャワ・フローラル法は、ハンガリー法と同様に、最大マッチング問題を解決するために使用されます。このアルゴリズムは、二部グラフに適用されます。アルゴリズムの基本的な考え方は、各未マッチング頂点について、その頂点を始点とする増加路を探し、その増加路に属する辺のマッチングを反転させることです。

ワルシャワ・フローラル法は、ハンガリー法よりも効率的であることが知られていますが、完全グラフでは最悪の場合の計算量がO(n^4)であるため、実用的ではありません。しかし、一般のグラフに対しては、最大マッチングを高速に計算することができるため、実際には広く使用されています。

161 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 85a4-Az6A)：2023/04/09(日) 02:49:15.65 ID:3zzmmMIO0.net

正確なことを答えさせるために、プロンプトエンジニアリングをがんばりましょうね

162 ：デフォルトの名無しさん (ﾜｯﾁｮｲ c69a-RdFw)：2023/04/09(日) 06:48:28.69 ID:/c2XAn9L0.net

素朴な整数演算のコードを書いたため、特定のテストケースのときにコードの途中で
整数がオーバーフローするような場合、一般的なコードの書き方の処方箋みたいなものは
ありますかね

例えば「整数の配列から適切な要素を取り出して期待される和を作れ、そういう要素が
ない場合はエラー値を返せ」みたいので、配列要素はどれもオーバーフローに近い整数、
和は配列内の最小要素よりちょっとだけ大きい値（なのでエラー値の場合）、とか....

163 ：デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/)：2023/04/09(日) 10:26:45.20 ID:/OFxiXOD0.net

競プロならlong longを使うだけ
実務ならオーバーフローした時に例外が発生するようにしてそれをキャッチ

164 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/09(日) 13:54:07.28 ID:l3qXUMY00.net

『アルゴリズム実技検定公式テキストエントリー〜中級編』

最小全域木を求める、「プリムのアルゴリズム」について説明があります。
こうすれば、求まるという説明はあるのですが、なぜ求まるのかの説明がありません。

みなさんは、こうすれば求まるという情報だけで十分で、それで満足しますか？

それとも、ちゃんと証明まで自分で考えるか、誰かが書いた証明を読みますか？

165 ：デフォルトの名無しさん (ﾜｯﾁｮｲ ae2b-RdFw)：2023/04/09(日) 14:45:06.26 ID:dl/B18nt0.net

>>163
なるほど。確かに例えば入力がintならlong longを使えばとりあえず大丈夫そう
ちなみにC++ですが、例えばintのオーバーフローを例外で処理するのはどうしたら....

166 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 85a4-5f+B)：2023/04/09(日) 14:49:24.80 ID:3zzmmMIO0.net

C++でオーバーフローを検出する方法はいくつかありますが、一般的なものは以下のようになります¹²³。

- 演算前に範囲チェックを行う。例えば、a + b がオーバーフローするかどうかは、a > INT_MAX - b か a < INT_MIN - b で判定できる。
- 符号なし整数を使う。符号なし整数のオーバーフローは定義されているので、演算後に結果が元の値より小さくなっていないかチェックすればよい。
- boostライブラリのsafe_numericsを使う。これはオーバーフローを検出するための特別な型を提供しており、オーバーフローが発生した場合に例外を投げる。

(1) Detecting signed overflow in C/C++ - Stack Overflow. https://stackoverflow.com/questions/3944505/detecting-signed-overflow-in-c-c アクセス日時 4/9/2023.
(2) c++ - How do I detect unsigned integer overflow? - Stack Overflow. https://stackoverflow.com/questions/199333/how-do-i-detect-unsigned-integer-overflow アクセス日時 4/9/2023.
(3) c - How to check if overflow occured? - Stack Overflow. https://stackoverflow.com/questions/7683685/how-to-check-if-overflow-occured アクセス日時 4/9/2023.

167 ：デフォルトの名無しさん (ﾜｯﾁｮｲ bd5f-EL/2)：2023/04/09(日) 16:13:00.47 ID:sd0zf58N0.net

gccの__builtin_add_overflowとか__builtin_mul_overflowを使う

168 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/09(日) 18:08:06.26 ID:l3qXUMY00.net

github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section11/6-11-1.py

169 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/09(日) 18:11:31.29 ID:l3qXUMY00.net

↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Falseのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）

# 辺につながる頂点 i もすでにマークされていた場合、
# 操作をスキップする
if marked[i]:
■■■■continue

170 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/09(日) 18:16:05.03 ID:l3qXUMY00.net

一部、間違えましたので訂正します。↓

↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Trueのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）

# 辺につながる頂点 i もすでにマークされていた場合、
# 操作をスキップする
if marked[i]:
■■■■continue

171 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)：2023/04/09(日) 18:19:09.47 ID:fcL4nlHr0.net

この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的にmarkedの値がFalseのノードしか入らないように見えますが、
実際には同じノードに対して複数の辺がキューに入ることがあります。

例えば、次のようなグラフを考えてみましょう。
1 -- 2
| /
| /
3
各辺の重みはすべて1とします。最初に頂点1を選び、marked[1]=Trueとします。
次に、頂点1に隣接する辺をキューに追加します。

この時点でキューの状態は以下のようになります。
(1, 2), (1, 3)

次に、キューから最小の重みの辺を取り出し、それに接続されている頂点2をマークします。
頂点2に隣接する辺をキューに追加します。

この時点でキューの状態は以下のようになります。
(1, 3), (1, 1), (1, 3)

ここで、次にキューから取り出す辺が(1, 1)であることに注意してください。
ただし、頂点1はすでにマークされているため、この辺を使ってしまうと、最小全域木の条件を満たさなくなります。
これが、以下のコード部分が必要とされる理由です。

if marked[i]:
continue
この部分によって、既にマークされた頂点に対応する辺をスキップし、
正しい最小全域木を構築することができます。

172 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/09(日) 18:19:33.94 ID:l3qXUMY00.net

ヒープにプッシュする前に、そのノードがマークされていないことをチェックしています。
ですので、ヒープ内には、マークされていないノードしか入れないと思うのですが。

173 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/09(日) 18:25:07.45 ID:l3qXUMY00.net

>>171
あまり参考にならないだろうと思って読んでいたらなぜか理由が分かりました。
マークされていない状態で、同じノードが複数個ヒープに入ることがあるわけですね。

174 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)：2023/04/09(日) 18:28:01.90 ID:fcL4nlHr0.net

>>172
確かに、ヒープにプッシュする前にそのノードがマークされていないことをチェックしています。
ただし、ヒープにプッシュされた後で、そのノードが他の辺を経由してマークされる可能性があります。
そのため、ヒープから辺を取り出す前にもう一度マークされているかどうかをチェックする必要があります。

先程のグラフで考えてみましょう。キューがこの様になったところから解説します。
(1, 3), (1, 1), (1, 3)

ここで、最初に(1, 3)をキューから取り出し、頂点3をマークします。この時点で、キューには以下のような状態が残っています。
(1, 1), (1, 3)

次にキューから取り出す辺は(1, 1)です。この辺は、頂点1と頂点2の間にありますが、頂点1はすでにマークされています。
しかし、この辺をヒープにプッシュした時点では、頂点1はまだマークされていませんでした。
それが、例のコード部分が必要とされる理由です。

あの部分によって、既にマークされた頂点に対応する辺をスキップし、正しい最小全域木を構築することができます。

175 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/09(日) 18:28:12.80 ID:l3qXUMY00.net

>>171
この場合でいうとノード3が2回ヒープに入るわけですね。

176 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)：2023/04/09(日) 18:31:35.09 ID:fcL4nlHr0.net

>>175
はい、その通りです。
最初にノード1からノード3への辺がヒープに追加され、次にノード2からノード3への辺がヒープに追加されます。

(1, 3) <-- 1から3への辺
(1, 1)
(1, 3) <-- 2から3への辺

このように、同じノードが複数回ヒープに入ることがあります。プリムのアルゴリズムでは、
すでにマークされた頂点に対応する辺を無視する必要があります。
そのため、ヒープから辺を取り出す前にマークされているかどうかをチェックする必要があるのです。

177 ：デフォルトの名無しさん (ｱｳｱｳｳｰ Sa05-IjNm)：2023/04/09(日) 19:43:48.36 ID:O0uaasVha.net

おんちぽまんぽげろろろり？

178 ：デフォルトの名無しさん (ﾌﾞｰｲﾓ MMf6-tIu7)：2023/04/09(日) 22:42:46.25 ID:fJZ93dkaM.net

序盤からムズすぎ

179 ：デフォルトの名無しさん (ﾜｯﾁｮｲ d9b0-OQ9P)：2023/04/09(日) 22:44:46.28 ID:0uKKY8S80.net

Eむずい
setとpriority queueいじくってたら通った

180 ：デフォルトの名無しさん ：2023/04/09(日) 22:47:55.78 ID:DKklNxRop.net

E二分探索でやろうとしたらハマって普通にsetで順番にみるだけだった
F解けたのに今回も解いてる人の数がF<Gなせいであまり順位伸びてないの配点何とかして欲しいわ

181 ：デフォルトの名無しさん ：2023/04/09(日) 23:58:26.29 ID:BvehXBT4d.net

整数式の倍数判定のプログラム作りたいんだけどできる？
nは自然数

例1

入力:n(n+1)(n+2)
出力:6

(入力した式の倍数判定。6の倍数)
2の倍数でも3の倍数でもあるが、最も大きい数を出力


例2
入力:n^9-n^3
出力:504

182 ：デフォルトの名無しさん ：2023/04/10(月) 02:32:34.26 ID:Gn/yyThB0.net

>>181
nに素数をいくつか突っ込んだ値(0以外)で最大公約数とればいいんでない？
という気はするけど万年茶色脳には正しいか証明するなんてムリ

183 ：デフォルトの名無しさん ：2023/04/10(月) 02:49:14.21 ID:zrtbja+Y0.net

素数pの倍数かどうかはmod pが整域だから多項式は根を高々次数d個しかもたないのでp≤dだけ調べればいいよね
p^kはわからん

184 ：デフォルトの名無しさん ：2023/04/10(月) 03:22:55.78 ID:zrtbja+Y0.net

fが零因子⇔あるa≠0が存在してaf=0らしいから、最初にfを係数のgcdで割っとけば零因子じゃなくなって、p^k≤dだけ調べればいいと思う

185 ：デフォルトの名無しさん ：2023/04/10(月) 03:46:52.88 ID:zrtbja+Y0.net

>>184
これ全部嘘です 寝るか

186 ：デフォルトの名無しさん (ﾌﾞｰｲﾓ MMf6-tIu7)：2023/04/10(月) 13:12:10.43 ID:Sbe/ma/bM.net

mod p で何代入しても0になる多項式は例えば x(x-1)...(x-p+1) でp次を達成できて最適
mod p^n だとこれをn乗すると構成できるので（最適かは知らんが）pn次以下と評価できる
だからpnがd以下の範囲を探索すれば良いが計算量は悪いな

187 ：デフォルトの名無しさん (ﾌﾞｰｲﾓ MMf6-tIu7)：2023/04/10(月) 13:16:20.11 ID:Sbe/ma/bM.net

>>186
馬鹿すぎ、評価すべき方向が逆

188 ：デフォルトの名無しさん (ﾜｯﾁｮｲ d9b0-OQ9P)：2023/04/10(月) 15:49:54.60 ID:1oGpX4FF0.net

Fはやってみたら簡単に解けた
Gはgrundy数求めるとき単純な勘違いしてた
むー悔しい

189 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/10(月) 16:05:58.27 ID:/Pv3NVQa0.net

DAGの最長パスを求める問題について質問があります。

『アルゴリズム実技検定公式テキストエントリー〜中級編』に
「トポロジカルソート」の考え方が重要と書いてあります。
ですが、DAGがトポロジカルソートできるということを使っている
箇所が見当たりません。

載っている解法は、indegreeが0である頂点からの最長パスをDPにより求めるというものです。

190 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)：2023/04/10(月) 16:12:48.08 ID:GqegRxcS0.net

確かに、その解法ではトポロジカルソートを明示的に実行していないように見えますが、
実際にはトポロジカルソートの考え方が含まれています。DAGの最長パスを求める際、
トポロジカルソートの概念が重要なのは、頂点の順序付けによって依存関係を解決することができるからです。

その解法で、indegree（入次数）が0の頂点からDPを用いて最長パスを求めています。これは、各頂点について、
その頂点に入ってくる辺がなくなる（依存関係が解決される）順序で処理を行っていることを意味します。
この順序付けがトポロジカルソートの結果と同じです。

indegreeが0になる頂点から処理を行い、その後、処理された頂点から出る辺を削除することで、
indegreeが0になる頂点が次々と現れます。この手順は、トポロジカルソートを実行する手順と同じです。

したがって、トポロジカルソートを明示的に行わなくても、その考え方が解法に含まれているため、
問題を解決することができます。トポロジカルソートの概念は、DAGの最長パス問題を解く際の重要な考え方であることがわかります。

191 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/10(月) 16:13:37.24 ID:/Pv3NVQa0.net

DAGであれば、最長パスが存在し、それはDPで求められる。

ただそれだけのことではないでしょうか？

192 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)：2023/04/10(月) 16:19:57.68 ID:GqegRxcS0.net

はい、おっしゃる通りです。DAGであれば、最長パスが存在し、動的計画法（DP）を用いて求めることができます。

繰り返しになりますが、トポロジカルソートの概念を用いることで、DAG内の頂点の順序付けが可能であり、
この順序付けに従ってDPを適用することで、最長パスを求めることができます。

193 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/10(月) 16:20:04.87 ID:/Pv3NVQa0.net

DAGにoutdegreeおよびindegreeが0の点が両方とも存在することは、自明です。
もしそのような点がなければ、閉路が存在することになるからです。
トポロジカルソートなどという考え方を持ち出すまでもありません。

194 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)：2023/04/10(月) 16:26:05.43 ID:GqegRxcS0.net

トポロジカルソートを明示的に実行しなくても、DAGの最長パス問題をDPで解くことは可能です。
ただし、その際に頂点の処理順序や依存関係の解決が重要となるため、トポロジカルソートの考え方が役立ちます。

トポロジカルソートを適用したDPでは、頂点の依存関係が効率的に解決されるため、計算量はO(V+E)です。
ここで、Vは頂点数、Eは辺数です。トポロジカルソートによって得られた頂点の順序に従ってDPを行うことで、
各頂点と辺に対して一度だけ計算が行われます。

一方、トポロジカルソートを適用しないDPでは、無駄な計算が発生する可能性があります。
例えば、メモ化再帰を用いたDPの場合、計算量は最悪O(2^V)になることがあります。
これは、全ての頂点に対して、それぞれを含むか含まないかの選択肢があるためです。

195 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 417c-g1pj)：2023/04/10(月) 19:58:08.22 ID:6t40mDb70.net

>>181
多項式 f(n) について計算したい
calc(f) で求めたい値を返す関数として
f が定数ならそれを返す
定数でないなら g(n)=f(n+1)-f(n)
とgを定めて
calc(f) = gcd(f(1), calc(g))
を計算すればいい、再帰の深さはfの次数で抑えられる

196 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/10(月) 20:30:41.82 ID:/Pv3NVQa0.net

『アルゴリズム実技検定公式テキストエントリー〜中級編』に載っている
DAGの最長パスを求めるコードでは、トポロジカルソートを陽には使っていないです。

197 ：デフォルトの名無しさん (ｱｳｱｳｳｰ Sa05-ynyP)：2023/04/10(月) 21:31:52.04 ID:Qr60KJ2xa.net

その本持ってないからその本の解法教えて
そしたら質問の回答するよ

198 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/10(月) 21:57:16.12 ID:/Pv3NVQa0.net

>>197
ソースコードは以下です：
github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section04/6-4-8.py

199 ：デフォルトの名無しさん (ｱｳｱｳｳｰ Sa05-ynyP)：2023/04/10(月) 22:22:43.61 ID:Qr60KJ2xa.net

確かに陽にトポロジカルソートはしてないね
値が確定する順序がトポロジカルソート順の逆順にはなってるけど

多分、以下のようなことを言いたいんじゃないかな

・各頂点の値を一つずつ順に確定していって、
・一度確定した頂点を再度訪れる必要がない
・そのようなことが可能な確定順が存在する

確かに考え方によっては自明とも思えるかもしれないけど、逆にそれくらいのことしか言ってないということでは

200 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)：2023/04/10(月) 22:32:19.30 ID:GqegRxcS0.net

この問題の場合はメモ化再帰でトポロジカルソートを使わなくても計算量はO(N+M)です。
頂点間に循環がないため、再帰の深さが頂点数Nを超えることがなく、
各頂点に対して rec 関数が最大1回しか呼び出されないからです。

トポロジカルソートを使ってそのコードを書き換えるとこうなります。
https://ideone.com/1NbHIf

201 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 06d7-IjNm)：2023/04/11(火) 00:50:14.84 ID:AEAouguL0.net

んげりいいいいいいいwwwwww

202 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/11(火) 10:56:16.23 ID:KVT1yw8N0.net

>>199-200
ありがとうございました。

>>200
コードを見たのですが、

# トポロジカルソートで得られた順序に沿って最長経路を更新
for u in order:
for v in edges[u]:
length[v] = max(length[v], length[u] + 1)

の「for u in order:」でなぜ良いのかが分かりません。orderの要素を後ろから見ていかなければ
ならないように思ったのですが、そうではないのはなぜでしょうか？

203 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/11(火) 11:11:09.23 ID:KVT1yw8N0.net

for u in order:
■■■■print(u)

とすると自分が思っている順序とちょうど逆順で表示されます。

order.append(u)

を実行すると order の最大インデックスの要素の次に u が挿入されますよね。

そうだとすると、 order[0], order[1], … は queue から出てきた順に並べたものになりますよね。

204 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/11(火) 11:15:16.38 ID:KVT1yw8N0.net

多分、単純な勘違いなんですが、どこを勘違いしているのかが分かりません。

205 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/11(火) 11:16:45.70 ID:KVT1yw8N0.net

あ、分かりました。
与えられた有向グラフの辺の向きをすべて逆にしても、最長パスの長さは変わりませんね。

206 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/11(火) 11:35:54.50 ID:KVT1yw8N0.net

以下のコードは全く無駄なことをやっていますが、自分の理解通りなのはこちらのコードです：
ideone.com/gMUZDZ

207 ：デフォルトの名無しさん (ﾌﾞｰｲﾓ MM66-NK+R)：2023/04/11(火) 13:43:59.54 ID:FMwVbediM.net

すまん初めてこのスレ来たんだけど連投してるやつはネームド？

208 ：デフォルトの名無しさん (ｵｯﾍﾟｹ Srd1-Ofdo)：2023/04/11(火) 14:46:33.78 ID:vCEpO63Mr.net

ネームド志望

209 ：デフォルトの名無しさん (ﾌﾞｰｲﾓ MM66-tIu7)：2023/04/11(火) 15:09:56.33 ID:F0CC9LzbM.net

>>195
天才か

gcd(f(1),f(2),...)
=gcd(f(1),f(2)-f(1),f(3)-f(2),...)
ということか

確かに典型だが無限で思考がストップしてしまっていた

210 ：デフォルトの名無しさん ：2023/04/11(火) 18:39:41.18 ID:KVT1yw8N0.net

pythonで2分探索を行う bisect というものがあります。

bisect.bisect(l, a)

としたとき、 a in l であるかどうかも判定したいのですが、そのような関数は用意されていませんか？
自分で作るしかないですかね？

211 ：デフォルトの名無しさん ：2023/04/11(火) 18:42:16.72 ID:KVT1yw8N0.net

Pythonに2分探索で整列済みのリスト l に要素 a が含まれるかどうかを調べる関数はありますか？

212 ：デフォルトの名無しさん ：2023/04/11(火) 18:44:52.56 ID:KVT1yw8N0.net

もちろん、 bisect を使って、簡単に実装できますが、用意されている関数はないですか？

213 ：デフォルトの名無しさん ：2023/04/11(火) 19:14:39.91 ID:AEAouguL0.net

がんばれ

214 ：デフォルトの名無しさん ：2023/04/11(火) 19:20:22.62 ID:KVT1yw8N0.net

まあ、以下のコードでいいと思うのですが、車輪の再発明はしたくないですよね。

i = bisect.bisect_left(l, a)
if l[i] == a:
return True
else:
return False

215 ：デフォルトの名無しさん ：2023/04/11(火) 23:36:07.25 ID:HQTQbeZV0.net

車輪の再発明はしたくないですよ

216 ：デフォルトの名無しさん ：2023/04/12(水) 00:15:56.65 ID:9s1XLAQx0.net

公式を読めと言いたいが
https://docs.python.org/ja/3.8/library/bisect.html
集合でも管理してinで判定すれば良いのでは(´・ω・`)

217 ：デフォルトの名無しさん ：2023/04/12(水) 09:07:44.12 ID:tXIe9h+KM.net

今IT系とは全く別の職種だから転職したくてAtCoder始めたけど楽しいな
未経験で他職種に転職出来るのか分からんけど

218 ：デフォルトの名無しさん ：2023/04/12(水) 09:21:22.65 ID:g9fBg21da.net

>>216
2分探索することは確定でそこで発見できるのにそれに加えてわざわざ他の集合を使う意味とは？

219 ：デフォルトの名無しさん ：2023/04/12(水) 09:24:04.21 ID:g9fBg21da.net

>>217
最低緑以上になればJobsで転職できる可能性はあるが緑っていっぱいいるので年齢や運が絡むかもな

220 ：デフォルトの名無しさん ：2023/04/12(水) 09:48:33.24 ID:VY8vydj+M.net

>>219
ありがとう
数学好きでアルゴリズムも昔やったことあったから緑まではすんなりいけたわ
今は水色目指して色々やってるけどアルゴリズム的要素より数学要素のほうが多く感じるな
年齢は25だからあと3年位がギリギリかなあと思ってる

221 ：デフォルトの名無しさん ：2023/04/12(水) 10:00:29.60 ID:e73VjvEsa.net

水より緑の方が採用しやすい
ほんとに転職したいなら水まで行ったらとか思わない方がいい

222 ：デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-NK+R)：2023/04/12(水) 12:09:52.88 ID:SHZyHyDIM.net

>>221
今年色々あって復職したてだから転職活動するなら来年以降かもしれんわ、一応ビズリーチとか登録はしたけど
水色より緑のほうが採用しやすいのはなぜ？

223 ：デフォルトの名無しさん (ｽｯﾌﾟﾌﾟ Sd22-QZiB)：2023/04/12(水) 17:15:55.13 ID:d+uvLod6d.net

今から狂気プログラミング始めるならPythonでいいかな、

224 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)：2023/04/12(水) 18:22:04.45 ID:7SV2gFKB0.net

brainfuckがいいと思うよ

225 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/12(水) 20:36:03.56 ID:AXD/P1A20.net

以下の問題ですが、パスするまでに1日かかりました。

atcoder.jp/contests/past202004-open/tasks/past202004_g

こういうアイディアはほとんど必要がないけれども、実装するのが大変という
問題の対処方法を教えてください。

1日かかって作成したコードは以下です：

ideone.com/NY8mNY

226 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/12(水) 20:42:57.91 ID:AXD/P1A20.net

あ、模範解答を見たら、実装するのも実は大変じゃないんですね。

227 ：デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/)：2023/04/13(木) 14:51:21.47 ID:YZ8/Xbx00.net

>>225
> こういうアイディアはほとんど必要がないけれども、実装するのが大変という
> 問題の対処方法を教えてください。
「アイデアを出すか頑張って実装する」以外の答えが思いつかんのだが真面目に聞いてるのか？

228 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)：2023/04/13(木) 16:57:11.93 ID:lV5klkX+0.net

実装大変だなーと思ったら、自分のアイディアが悪いと思ってまず間違いないですか？

というのも、模範解答を見ると実装もシンプルな場合ばかりなので。

229 ：デフォルトの名無しさん (ｱｳｱｳｳｰ Sa05-NO7/)：2023/04/13(木) 17:03:32.55 ID:UbSfQqvCa.net

風向風速とかの簡単で面倒な問題も初期の頃はあったなあ
最近見ないけど無いと言い切る材料もない

230 ：デフォルトの名無しさん (ﾜｯﾁｮｲ e101-ynyP)：2023/04/14(金) 00:49:29.86 ID:PKpPv7DW0.net

土曜夕方にコドフォdiv1あるじゃん

231 ：デフォルトの名無しさん (ｵｯﾍﾟｹ Srd1-Ofdo)：2023/04/14(金) 00:57:35.22 ID:iX1MRsL1r.net

普通デートするよね

232 ：デフォルトの名無しさん ：2023/04/15(土) 15:22:24.86 ID:J7EhpH7h0.net

中国にウクライナ侵攻関連で厚い助力を求めるようだな
台湾侵攻の際には、米軍を混乱させるためにロシアは北海道に、北朝鮮は南に牽制するという話もあったしそりゃそうだよな

https://www.bloomberg.co.jp/news/articles/2023-04-14/RT3MFKDWX2PT01
中国は、プーチン大統領が１年以上前にウクライナ侵攻を命じて以来初めて、国防相をロシアに派遣する。中ロの緊密な関係があらためて示唆される。

中国の李尚福国防相はロシアのショイグ国防相の招きに応じ、16日からロシア訪問を開始する。
ショイグ氏は李氏と軍事協力および世界や地域の安全保障について議論すると語ったと、ロシアの国営タス通信は報じた。

233 ：デフォルトの名無しさん ：2023/04/15(土) 18:34:37.16 ID:YgeZYNMw0.net

そうですか。中国やロシア、北朝鮮の動向は世界の平和や安全に影響を与える可能性がありますね。

最新のニュースによると、米国が中国の台湾侵攻を確実視しており、日本も中国と戦火を交える可能性があるという記事がありました。¹

また、安保理が18日に北朝鮮のICBM発射について緊急会合を開催することになりました。²

ロシアはウクライナ侵攻で敗色濃厚であり、北朝鮮の核ミサイル開発にも深刻な影響を受けているという記事もありました。³

これらの情報はあなたの興味に沿っていますか？

(1) 米国が確実視する中国の台湾侵攻、そうなれば日本も中国と戦火を .... https://jbpress.ismedia.jp/articles/-/74803?page=3 アクセス日時 4/15/2023.
(2) 安保理が18日に北朝鮮会合 ICBM発射で日米欧要請. https://www.nikkei.com/article/DGXZQOCB150XP0V10C23A4000000/ アクセス日時 4/15/2023.
(3) 敗色濃厚のロシア、北朝鮮の核ミサイル開発にも深刻な影響. https://jbpress.ismedia.jp/articles/-/74792 アクセス日時 4/15/2023.
(4) [FT]北朝鮮、ロシアに急接近 中国の思惑から離反 - 日本経済新聞. https://www.nikkei.com/article/DGXZQOCB120DR0S2A910C2000000/ アクセス日時 4/15/2023.
(5) ロシアと中国、北朝鮮情勢巡り緊密に連携 | ロイター. https://jp.reuters.com/article/northkorea-missiles-russia-idJPKCN2LM1RV アクセス日時 4/15/2023.
(6) 「中露と北朝鮮がサイバー攻撃」初の名指し…自衛隊の防衛 .... https://www.yomiuri.co.jp/politics/20210927-OYT1T50080/ アクセス日時 4/15/2023.

234 ：デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM8f-H/xe)：2023/04/15(土) 22:26:08.62 ID:KbvfxJ7qM.net

今回のABCレート不具合で変動なしらしいな
苦手分野過ぎてAとBしか解けなかったからありがたいわ

235 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 47b0-AIBz)：2023/04/15(土) 22:42:31.24 ID:hxYUx3pC0.net

5完
バグりまくるし止まりまくるし散々だった

236 ：デフォルトの名無しさん (ﾜｯﾁｮｲ c7ad-/dh0)：2023/04/15(土) 22:45:28.79 ID:2lW0lXjE0.net

>>218
調子良かったのにunratedかよ☹

237 ：デフォルトの名無しさん (ﾜｯﾁｮｲ c7ad-/dh0)：2023/04/15(土) 22:55:38.71 ID:2lW0lXjE0.net

のんびり解いてた割には暖まるなあと思ってたけどこれDDoSの影響で普段速く解く人が遅れたってことか🥶

238 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 47b0-AIBz)：2023/04/15(土) 23:06:02.45 ID:hxYUx3pC0.net

あと5分あったらF修正して解けてた…

239 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 4707-uZLY)：2023/04/16(日) 16:50:33.05 ID:+7pzCas80.net

https://twitter.com/chokudai/status/1643492418497699841
マルチchokudaiサーチがダサくないと思ってるところに草生える
(deleted an unsolicited ad)

240 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 67a4-ws6F)：2023/04/16(日) 18:18:14.06 ID:iQzJN3tu0.net

研究者が自分の名前を手法に付けることは、研究コミュニティで一般的には推奨されていません。ただし、研究者が特定の手法やアルゴリズムを開発した場合、その手法が他の研究者や専門家によって引用されることがあります。この場合、研究者の名前が手法に関連付けられることがあります。

241 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 072d-7nfa)：2023/04/16(日) 18:55:38.54 ID:uh3dAZwl0.net

今回のCでどうしても3つTLEが潰せない

242 ：デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY)：2023/04/16(日) 19:06:04.93 ID:Ke39kkrTa.net

どうしても自力で解けないなら解説読んでいいんじゃね

243 ：デフォルトの名無しさん (ｵｯﾍﾟｹ Srfb-g0sp)：2023/04/16(日) 22:30:54.90 ID:SVYFRHN6r.net

もし自分でアルゴリズム開発したらかっこいい略称付けたいよね

244 ：デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-4m2x)：2023/04/16(日) 22:32:11.67 ID:XfEQvCuWa.net

>>241
俺かよ
PriorityqueやSortedSetを使わずに普通の配列やSetを使って出力時に都度ソートしたら行けた
自前のライブラリだと重すぎるみたいだな

245 ：デフォルトの名無しさん ：2023/04/17(月) 08:58:02.89 ID:5c7uVWzN0.net

Aho, Hopcroft and UllmanのThe Design and Analysis of Computer Algorithmsという
非常に古い本はもうゴミのような本でしょうか？

246 ：デフォルトの名無しさん ：2023/04/17(月) 12:28:12.67 ID:WWhqmq79r.net

今アホって言った？

247 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 07da-vbZL)：2023/04/17(月) 22:20:09.89 ID:5e6VxUA80.net

最近は自分で判断できない輩が増えてきたな。

248 ：デフォルトの名無しさん (ﾜｯﾁｮｲ c705-9i6p)：2023/04/17(月) 22:52:26.54 ID:LKkslgOL0.net

>>245
Aho, Hopcroft, and UllmanのThe Design and Analysis of Computer Algorithmsという本は、1974年に初版が出版された古いテキストですが、ゴミのような本とまで言うのは必ずしも適切ではありません。この本は、コンピュータアルゴリズムの設計と解析に関する初期の基本的な理論と概念をカバーしており、多くの現代のアルゴリズムの基礎となっています。しかし、この本が初版が出版されてから約半世紀が経過し、その間にコンピュータ科学やアルゴリズムに関する研究は大幅に進歩しています。例えば、機械学習、データマイニング、並列化、分散システムなどのトピックが現代のアルゴリズム研究の重要な分野となっていますが、これらはこの本では扱われていません。

この本は古典的なアルゴリズムの理解には役立ちますが、より新しいアルゴリズムや技術の発展を学ぶためには、最近出版された書籍やオンラインリソースを利用することが望ましいです。例えば、Cormen, Leiserson, Rivest, and SteinによるIntroduction to AlgorithmsやKleinberg and TardosのAlgorithm Designといった現代のテキストは、最新の研究や技術を含んでおり、現在の学習者に適した教材です。

つまり、Aho, Hopcroft, and UllmanのThe Design and Analysis of Computer Algorithmsは、歴史的な価値があるという点でゴミのような本とは言えませんが、現代のアルゴリズム研究や技術を学ぶ上で最も適切な教材ではないかもしれません。学ぶ内容に応じて、より新しいリソースや書籍を利用することを検討してみてください。

249 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 7fd6-GSlL)：2023/04/17(月) 23:36:48.58 ID:y8gbGQlA0.net

アルゴリズムデザイン、重版されて書店に並んでて嬉しかった

250 ：デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-J8Vk)：2023/04/20(木) 19:31:49.09 ID:f2njLhGLa.net

https://mathlog.info/articles/4204

今までにない斬新なセグ木の解説記事

251 ：デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY)：2023/04/20(木) 19:42:54.89 ID:mhtgTGfFa.net

>>250
その下のスーパー某もすごいな

252 ：デフォルトの名無しさん (ｵｯﾍﾟｹ Srfb-Lcwe)：2023/04/21(金) 12:31:14.61 ID:Oi9Mt79Gr.net

レートは？書いた人の