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

2022/10/02(日) 17:43:58.66

↑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/

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

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

2022/10/02(日) 17:48:55.39

あ、すまん、うっかりテンプレのコマンド部分消してしまったわ
>>950
次スレ立てるときは次のレスのテンプレからコピペしてくれ

2022/10/02(日) 17:55:37.59

コマンド先頭に書こうとしたら弾かれるわ
!extend:checked:vvvvv:1000:512
要は>>950はこれを先頭に２行つけてな
ワッチョイ表示用コマンド、詳細とかはググってくれ

2022/10/02(日) 18:53:41.67

フレームワーク使っていい競技？

2022/10/02(日) 19:35:57.30

数学っぽい問題を解くために一からアルゴリズムのコード書いていくタイプの競技だから、あんまフレームワークを活用できる機会ないかも

2022/10/02(日) 21:00:40.58

そうじゃない
そこはフレームワークなんて使うわけないだろ馬鹿
とか罵るところだろ

2022/10/02(日) 22:11:28.18

どんなフレームワークを使うつもりだったのか聞きたい

2022/10/03(月) 00:08:34.99

業プロの人ってフレームワークとかそういうフワフワした言葉大好きだよね

2022/10/03(月) 01:46:07.58

AtCoderのWebサイトは何のフレームワークで実装されてるんだろう

2022/10/03(月) 04:01:38.80

ここに書いてある

レールは続く】 Ruby on Rails Part21 【これからも
https://medaka.5ch.net/test/read.cgi/php/1545146635/103

Rails 製、「爆速すぎて笑う」　表示速度が“異常な”Webサイト「dev.to」　その仕組みは？

BuiltWith で、サイトが使っている技術を調べる

2022/10/05(水) 20:15:07.12

算数パズルにフレームワーク

2022/10/06(木) 04:14:49.38

ライブラリとフレームワークの違いもよくわからんしな

2022/10/06(木) 12:52:23.39

同じdiffでもABCかARCかAGCか、前の方に置かれたか後ろの方に置かれたか、いつごろコンテストが行われたかでだいぶ難易度変わるよな
なんかいい感じの補正できないか

2022/10/06(木) 13:07:07.83

この深層強化学習で行列積アルゴリズムを改善したというnature論文かなり注目されているな
chokudaiもRTしてたし
NNの重み埋め込んで使えば競プロでもウハウハじゃね？って思ったけど、10%とか20%の改善で競プロで劇的に役立つほどの改善じゃなさそう
とはいえ、深層学習とかも中身は結構行列演算だし、人類に相当貢献するアルゴっぽい
https://www.nature.com/articles/s41586-022-05172-4

2022/10/06(木) 14:08:36.03

この論文が特にすごいのは、発見した行列積アルゴリズムそのものよりも、AlphaZeroのやり方で優秀なアルゴリズムも発見できる、ということだけどな

2022/10/07(金) 08:03:59.07

ある工事完了に必要な作業1～6について以下の制約がある。
作業2は作業1が終わるまで開始できない。
作業3は作業1が終わるまで開始できない。
作業4は作業2と3が終わるまで開始できない。
作業5は作業3が終わるまで開始できない。
作業6は作業4と5が終わるまで開始できない。
この工事はT日以内で終えねばならず、各作業iはt_i日かかる。
しかし臨時作業員を雇うことにより作業日数を減らすことができるが、
s_i日よりは少なくはできない。また、1日減らすのにm_i万円かかる。
費用を最小にする作業計画をたてよ。

minimize: 農{i=1}^{6} m_i × (t_i - x_i)
subject to:
x_1 + x_2 + x_4 + x_6 ≦ T
x_1 + x_3 + x_4 + x_6 ≦ T
x_1 + x_3 + x_5 + x_6 ≦ T
s_i ≦ x_i ≦ t_i (i = 1, …, 6)

模範解答では各作業の開始日y_iという変数も考えています。
上の解答は間違っていますか？

2022/10/07(金) 09:38:43.05

合ってると思うぞ
全パスを列挙する必要があるから制約の数が指数オーダーになるが

2022/10/07(金) 10:02:47.32

>>17
ありがとうございました。念のため本に書いてある模範解答を以下に書きます。
minimize: 農{i=1}^{6} m_i × (t_i - x_i)
subject to:
y_1 = 0
y_1 + x_1 ≦ y_2
y_1 + x_1 ≦ y_3
y_2 + x_2 ≦ y_4
y_3 + x_3 ≦ y_4
y_3 + x_3 ≦ y_5
y_4 + x_4 ≦ y_6
y_5 + x_5 ≦ y_6
y_6 + x_6 ≦ T
s_i ≦ x_i ≦ t_i (i = 1, …, 6)

2022/10/07(金) 18:03:45.88

https://youtu.be/7DbdPKWhrpY

令和のコペルニクスさんによって固定されています
令和のコペルニクス
2 年前（編集済み）
六角アミダって有りそうで無かったので自作しました。xyz空間座標も「６方向」ということで。

ソースコードはこちら。

https://drive.google.com/file/d/1hsFT2F4AMgUv1JHqy0si_7Yj7q7TyHnR/view?usp=sharing

室町時代のアミダくじは円形であること、ベンゼン環の六角構造、赤青緑の三色ダイオードを考えてみた。

令和のコペルニクス
1 年前
地動説をとる人には、地動説をとるのを妨げない。天動説をとる人には、天動説をとるのを妨げない。学説上において人びとの所見を妨げず、かつ実生活においても、「令和のコペルニクス」は決して客観的に善悪正誤など認定しない。

2022/10/07(金) 19:38:27.44

区間最大値の問題解くためにセグメントツリーのアレを書いたら実装に２時間かかったぞこの野郎

2022/10/07(金) 22:47:40.57

じゃあ次はsparse tableを実装しよう

2022/10/08(土) 00:33:30.00

単純な腕力は鍛えて損はない

2022/10/08(土) 12:52:33.92

やはり暴力、暴力はすべてを解決する

2022/10/08(土) 13:47:42.95

明日のARCの配点どんな感じなんだろ
5-7は崖ができやすいので6を増やしてほしい

2022/10/08(土) 17:34:43.15

atcoder.jp/contests/tessoku-book/tasks/tessoku_book_m

この問題の解答として以下のコードを作ったのですが、なぜか小さい入力データに対して
実行時間制限オーバーになってしまいます。大きい入力データに対してはすべてパスしています。

ideone.com/CUJvso

2022/10/08(土) 17:41:04.41

バグを見つけました。

2022/10/08(土) 22:47:32.78

恥ずかしいんだが、競プロ初心者の俺のD問題のコードを見てほしい
bfsを使って解いたんだが、なぜかTLEが出てしまった。
このコードの何がいけないのか有識者教えていただけないだろうか。
次のレスでコードのせます。

2022/10/08(土) 22:49:39.36

import numpy as np
import math

n, m = list(map(int, input().split(" ")))
mapp = np.zeros((n, n)) - 1
mapp[0, 0] = 0

p = []
for i in range(n + 1):
temp = m - i ** 2
if temp < 0:
continue
t = math.sqrt(temp)
if t - int(t) <= 1e-7:
p.append((int(i), round(t)))
temp = []
for a, b in p:
temp.append((-a, -b))
temp.append((a, -b))
temp.append((-a, b))
directions = list(set(temp + p))

def is_inside(pp, qq):
return 0 <= pp <= n - 1 and 0 <= qq <= n - 1

que = [(0, 0)]

2022/10/08(土) 22:49:55.06

while True:
if len(que) == 0:
break
y, x = que.pop(0)
num = mapp[y, x] + 1
for s, t in directions:
yy, xx = y + s, x + t
if not is_inside(yy, xx):
continue
if mapp[yy, xx] != -1:
continue
mapp[yy, xx] = num
que.append((yy, xx))
mapp = mapp.astype(int).astype(str).tolist()

for i in mapp:
print(" ".join(i))

2022/10/08(土) 22:50:57.84

ここにコードを乗せるのは無理があったか

2022/10/08(土) 22:56:46.79

G乱択想定解かー
教育的だね

2022/10/08(土) 22:58:15.49

pastebin辺り使え

2022/10/08(土) 23:04:25.31

>>28
あんま競プロでPython使わないんだけど、まずDってO(N^3)とかO(N^2√M)だから遅い言語だとちょっと定数倍遅いだけで2secで通らなくなるような問題だと思う
そしてそのコードは(x,y)で状態持ってたりしてて定数倍微妙そうなコードだなと思ったな
numpy使ってるってことはPyPyじゃなくてCPythonでしょ？それだとアルゴリズム自体は間違ってなくてもTLEで落ちるんじゃないかな

2022/10/08(土) 23:09:23.51

que.pop(0)ってやってるけど、PythonのlistにFIFOとしての機能あったっけ？
listの内部実装次第だけど、そこで計算量オーダー増えててもおかしくないような
queueを使いたいときにはdequeとか使ってる人が多い印象

2022/10/08(土) 23:09:40.62

suffix arrayってどの色のdiffくらいから前提知識として求められるアルゴリズムなん？

2022/10/08(土) 23:14:27.40

手元のPythonで見てみたけど、listでpop(0)すると配列の長さ分計算時間がかかってそうだから、その書き方だとO(N^4)とかO(N^5)になってるんじゃないかな
ぶっちゃけ別にBFSである必要はないからque.pop(0)→que.pop()でだいぶ早くなるんじゃない？
確かstackとしては使えたはず

2022/10/08(土) 23:14:43.63

深さ優先でも上手く行くんかな

2022/10/08(土) 23:18:18.42

>>35
出る難易度帯からすると青ぐらいの印象
ただ概念的にはそんなに難しくないかなあ（SA-ISというアルゴリズム自体は頭いいけど）
知識的な敷居の高さから後ろに置かれることが多いけど、水色ぐらいでも練習すればACLを活用しつつ普通に解けるレベルの問題も多いと思う

2022/10/08(土) 23:20:22.20

>>29
ちょっと今外で詳しくは見れてないけどこの手のdfsでTLEになるって
deque使わずにキューしちゃったか、訪れ済みのマスを飛ばしてないとかだよ

2022/10/08(土) 23:21:14.83

あ、すまん、ボケてたわ
最短距離問題からBFSである必要はあるわ、忘れてくれ
dequeをcollectionsからimportして、使えばいいと思うよ
あとnumpyを使わずに実装しなおしてPyPyで提出しなおせば

2022/10/08(土) 23:24:18.99

>>38
なるほどありがとう
丁度その手前の帯域にいるからこれを機に勉強してみるわ

2022/10/08(土) 23:36:17.47

>>25
二分探索だけど、ちょうどこの前話題になった「めぐる式」二分探索って実装方針がバグらせにくくておすすめだよ
ググれば出てくると思う

2022/10/08(土) 23:45:35.49

ARCの配点出たのか
この前みたいに5-7で崖ができるとやりにくいなー

2022/10/08(土) 23:49:58.84

>>42
めぐる式いいんだけどこの前のabc269Eみたいな２分探索だと色々バグらん？

2022/10/09(日) 00:03:22.87

>>44
判定関数をf(n) = (1 n 1 Nと入力したときの応答がn-1のときはtrue、nのときはfalse)みたいな風にすればめぐる式でできない？

2022/10/09(日) 00:05:11.03

初期値はok = N, ng = 0で

2022/10/09(日) 13:10:10.78

昨日コードかいたものだけど
サンクス、numpyをやめてqueをdequeにして
python3.8⇒pypyにしたらTLEにならず通った

しかし、python3.8にしたら通らなかった

なんだかな。。言語によっては通らないみたいなのやめた方がいいんじゃないだろうか。。

2022/10/09(日) 13:16:26.59

言語じゃなくて処理系の違いだからセーフ

2022/10/09(日) 13:22:07.84

計算量の見積りは大事な要素だから遅い言語使う方が悪いということになってる
実際Pythonはpypy あるしRubyはCrystalあるからどうにもならないって人はそんなにいないはず
aclがc++にしかない方が不公平に感じる

2022/10/09(日) 13:49:20.47

君もC++で書いて計算量的に数十倍かかるゴミコードでACしよう

2022/10/09(日) 13:53:56.11

CPythonだとC++の10～30倍ぐらいは遅いから、なんでもかんでも確実にCPythonで通るようにtime limit設定するとC++で非想定の悪い解がバンバン通るようになってゲームが成立しなくなる
一方PyPyは確かJavaと同等かちょっと遅い程度だからそれでほぼ通せるはず
言語ごとにtime limit変えるみたいな話もなくはないけど、ちょっと詳しい人なら遅い言語にC++とかのコンパイル済バイナリ埋め込んで通すみたいなことができてしまうし、現行のルールはなるべくしてなったものだと思うよ

2022/10/09(日) 15:09:36.52

そういえばAGCって年6回開催が目標だったけど、今年まだ2回しかやってないのか
一昔前はARC級が全然なくて黄橙がつらい言ってたけど、こっちは順調なペース
WTFもないし、上級者向けコンテストが枯渇してる

2022/10/09(日) 15:27:54.23

りんご時代より大幅に減ってるんだな
Admin無能すぎでは

2022/10/09(日) 16:24:26.89

admin を片手間の学生に任せてるのがおかしいのでは？

2022/10/09(日) 18:01:54.02

>>47
ジャンプの問題かな？
自分も Python & deque で最初は TLE した。
問題の対象性を利用して (i, j) が確定した時に
合わせて (j, i) の値もセットして訪問済みに
したら Python でも通るようになった。
一方で E は PyPy でないと通らなかったわ。

2022/10/09(日) 19:47:34.94

>>55
なんと。。1/2倍にしたっていうことだよね。確かに正方形だしナイトの動きだと思えばi.jも確定するね
定数倍速くするのは競プロ系だとあまり意味ないと思ってた

2022/10/09(日) 20:49:39.37

もうすぐレギュラーだ
A問題だけでもなんとかして解きたい

2022/10/09(日) 20:50:21.13

競プロ初めて2ヶ月、A問題さえ解ければ茶色になれる

2022/10/09(日) 20:57:07.39

よし、気合入れるぞ
A問題に全精力を注ぐ

2022/10/09(日) 21:51:11.27

緑から水色いくのにARCの問題解くのって効果的かな？それともABCの緑以上の問題解いてた方がいい？

2022/10/09(日) 23:03:37.83

a問題でスパゲッティコード書きまくって結局RE
泣きたいですよ

2022/10/09(日) 23:51:12.05

冷えたなー
Cが曲者だった

2022/10/09(日) 23:51:27.48

ARC2、3完安定してきたと思ったら初めて0完して泣いてる