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

レス数が1000を超えています。これ以上書き込みはできません。
1デフォルトの名無しさん (ﾜｯﾁｮｲ 1f9f-qCnf)
垢版 |
2021/07/28(水) 21:58:48.02ID:nljYiy+l0
!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/

※前スレ
競技プログラミングにハマるプログラマのスレ 62
https://medaka.5ch.net/test/read.cgi/prog/1626625368/
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
947デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/02(日) 12:43:27.85ID:c1nVdKJ60
大槻のAtCoder入門という本は買わなくて正解でした。
図書館で借りて読めば十分な内容です。
948デフォルトの名無しさん (ﾜｯﾁｮｲ ff10-UJKs)
垢版 |
2022/10/02(日) 14:48:02.40ID:m2kqJsOp0
>>944
確かに その方が実装綺麗にまとまるね
2022/10/02(日) 16:15:35.42ID:FsOTPbTb0
正解です
2022/10/02(日) 16:49:02.85ID:eK4S0SoN0
>>946
大槻さんの本で初級用の知識は入ったんだろうから問題集に移ることをオススメする。
2022/10/02(日) 16:56:26.21ID:eK4S0SoN0
>>950踏んだけど立てられなかったから誰か立ててくれ
2022/10/02(日) 17:44:45.80ID:FqAfPtIrM
次スレ
https://itest.5ch.net/mevius/test/read.cgi/tech/1664700238/l50
2022/10/02(日) 17:58:33.59ID:eK4S0SoN0
>>952
助かったありがとう
2022/10/02(日) 20:39:28.28ID:RBz4Dz1b0
AHC、他の人の解法を参考に自分のを高速化しただけで60M超えてつらい
自分が高速化だと思ってコンテスト中やってたことが逆効果になってただけだったし
2022/10/02(日) 21:43:51.33ID:zlxZgBGt0
今ランキング見てるけど日本人多いんだね
まだまだこの国も未来がありそう（他人事）
2022/10/02(日) 22:03:53.70ID:bP9R5MM60
こどふぉのランキング見てると中国がスゲェ
957デフォルトの名無しさん (ﾜｯﾁｮｲ ffbd-atM5)
垢版 |
2022/10/02(日) 22:36:17.43ID:RAAxIiX40
コンテスト中に呟いちゃいけないんだろうけど

1時間以上Aを考えてるがわからん
2022/10/02(日) 23:16:35.86ID:cj6ZUnIP0
匿名の書き込みでも普通にやめた方がいい
そのぐらいなら大丈夫だと思うけど、それを見てまだラインがわからない人が勘違いしてさらに際どいことを書き込んでしまう危険性が
959デフォルトの名無しさん (ﾜｯﾁｮｲ ffbd-atM5)
垢版 |
2022/10/02(日) 23:26:55.10ID:z5LMHK5C0
わかった。少なくともコンテスト終了後に呟くようにする


今日のAわからなかった。。
どうやっても10^10**5がmで割り切れるかを10^5回するし


ゾロ目数に規則性はあるっちゃあるけど、ないから
全くわからんかった
2022/10/02(日) 23:30:32.52ID:cj6ZUnIP0
桁数大きい整数がある整数の倍数になるみたいな問題は類題があるから、それで早解き出来た人も結構いるかも
2022/10/02(日) 23:58:17.51ID:cj6ZUnIP0
D、平衡二分探索木のsplit-mergeみたいなのでどうにかできないかなというのは自分も少し考えたけど、反転と組み合わせてそういう操作ってできるんだっけ
2022/10/03(月) 00:21:39.73ID:sJyra2/X0
Aって出力形式変えたらN, M<=1e18 とかで解けたりしない?
2022/10/03(月) 00:31:17.62ID:EDkvNrQV0
上から全探索だとO(N)はかかっちゃいそう
(10^N - 1) % M自体はO(log(NM))で計算できるけど
2022/10/03(月) 00:36:30.02ID:EDkvNrQV0
N<=10^18,M<=10^5ならグラフ作ってBFSとかでいけそう
2022/10/03(月) 00:38:27.23ID:EDkvNrQV0
というか別にグラフ作る必要もないか
f(x) = (x-1)/10を作用させ続ければO(M)で解が見つかるか、不能判定ができるという話
2022/10/03(月) 00:58:09.84ID:3ar7JQ8O0
解説に書いてあるくね？
967デフォルトの名無しさん (ﾜｯﾁｮｲ 6f71-0qRf)
垢版 |
2022/10/03(月) 01:04:26.18ID:lndyBnH50
というか10^(10^5)なんて数を扱う事あるのかｗｗｗ

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1463346279
＞1m3に10個程度の原子（ほとんど水素）なら10^79となります。多めに見積もっても10^80は妥当なところだと思います。宇宙の半径130億光年であっても1桁増える程度です。
2022/10/03(月) 01:32:24.69ID:sJyra2/X0
解説読んでなかったわサンクス 本番(10^n-1)/9とEulerの定理方針が最初に見えたんだけど300点なことを思い出して引き返せた
2022/10/03(月) 01:35:16.73ID:EDkvNrQV0
累乗modの問題だしオイラーの定理で高速化できるか
頭固かったわ
970デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/03(月) 03:00:23.71ID:kRWtLYQ60
atcoder.jp/contests/abc137/tasks/abc137_d

この問題の解答を作ったのですが、一部の入力例に対してしかパスしません。
どこにバグがあるか分かる人はいますか？

解答は以下です：
ideone.com/uZ1cUa
971デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/03(月) 03:42:55.31ID:kRWtLYQ60
>>970
のバグが分かりました。

大槻の『AtCoder入門』ですが、結局、独力で解答を見ずにすべての問題を解けました。
972デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/03(月) 03:45:23.53ID:kRWtLYQ60
>>949
ありがとうございました。
>>950
問題集ってPASTの問題集ですか？
米田の本はまだ見ていないのですが、売れ行きはいいですよね。
973デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/03(月) 03:49:30.34ID:kRWtLYQ60
ideone.com/z97s8q

バグの修正を上のようにしました。

パスしなかった入力を見ることができれば、バグ修正もやりやすいでしょうが、
実際には見ることができません。

みなさんはどうやって、バグ修正していますか？
974デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/03(月) 03:55:00.31ID:kRWtLYQ60
大槻の『AtCoder入門』ですが、普通の「アルゴリズムとデータ構造」の本に書いてあるようなことは
ほとんど書いていない変な本ですね。

競技プログラミングで「アルゴリズムとデータ構造」の知識をほとんど必要としない問題用の本ですね。
2022/10/03(月) 04:48:16.87ID:TupNe+4/r
うんち
2022/10/03(月) 05:17:41.51ID:hBuxdlaYM
その本はプログラミング経験もアルゴリズムの学習経験も皆無に近い人(中高生も含め)がatcoderのC問題あたりを解けるようにして、本当に簡単なアルゴリズムを触れるようにするぐらいのレベルのもの
not for youだな
というかそもそも大多数の競プロ本はアルゴリズムとデータ構造の教科書を志向していないから
2022/10/03(月) 05:24:09.62ID:hBuxdlaYM
デバッグは自分でテストケース作ってやるのがいい
実は過去コンテストのテストケースを見に行くことはできるが、競プロコンテスト本番のデバッグ力を鍛えることができないからオススメしない
978デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/03(月) 08:54:28.68ID:kRWtLYQ60
>>976-977
ありがとうございます。

過去問の入力データを見に行けるんですね。
解答を見るのと、解答を見ずに入力データは見るというのだったら、後者のほうが勉強になると思います。
独力で正解を作るのがベストだとは思いますが。
979デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/03(月) 08:55:09.57ID:kRWtLYQ60
テストケースを作るのは非常に大変だと思います。
2022/10/03(月) 10:07:34.75ID:hBuxdlaYM
乱数で入力を発生させ、計算量的に悪いけど簡単に思いつけて実装できる部分解法で正しい出力を出せばいいわけで、そんなハードル高いものじゃないぞ
上位層はコンテスト中にちゃちゃっとやってると思う
2022/10/03(月) 10:14:59.33ID:Jd0Y4vRLM
独力で頑張ってるようで応援してるよ
典型的なアルゴリズムも自分で思いつけるようなものなのか興味ある
982デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/03(月) 19:13:46.77ID:kRWtLYQ60
>>980-981
ありがとうございました。

>>980
「計算量的に悪いけど簡単に思いつけて実装できる部分解法」
これは思いつきませんでした。ありがとうございました。

『競技プログラミングの鉄則』を今読んでいて第2章の累積和の途中まで読み終わりました。
確かにレベル的にはそれほど高くない本だとは思いますが、勉強になったことがありました。
・問題で添字が1始まりの問題ではプログラムでもそれに合わせて1始まりにすると分かりやすくなる。
・使用メモリ量については寛大なので無駄遣いしても全く構わない。
・1つのfor文でまとめて処理できる場合でも、複数のfor文に分ける（それでもオーダーは変わらない）と、分かりやすくなることがある。
・
for (int i = 0; i < N; ++i) {
□□cin >> A >> B;
□□ここに処理を書く。
}

とできる場合でも、

for (int i = 0; i < N; ++i) {
□□cin >> A[i] >> B[i];
}

とまずすべての入力を受け取ってしまってから、後で処理を書いても良い。
983デフォルトの名無しさん (ﾜｯﾁｮｲ 6f71-0qRf)
垢版 |
2022/10/03(月) 20:26:59.27ID:lndyBnH50
https://twitter.com/intent/favorite?tweet_id=1516784253656506369
@rui314
さん
あれはSAPIXとか鉄緑会と同じカルチャーだと思う。
https://twitter.com/5chan_nel (5ch newer account)
2022/10/03(月) 23:10:45.15ID:8ESWd8Bnr
本当のことを言うのはやめろ
2022/10/03(月) 23:45:23.95ID:hBuxdlaYM
せめて数オリ情オリと言ってほしい
2022/10/04(火) 00:26:34.06ID:cX4mL7Ac0
>>972
atcoder probremsってサイトで自分のレートに合った問題をひたすら解くってこと
codeforces　ladderとかで検索してもいい。
987デフォルトの名無しさん (ﾜｯﾁｮｲ 8301-kE2G)
垢版 |
2022/10/04(火) 01:28:16.20ID:6c7uePz80
https://atcoder.jp/contests/abc271/tasks/abc271_b
https://atcoder.jp/contests/abc269/tasks/abc269_b
こういうの問題文読んだだけじゃ何のことか分からなくて、入出力例を見てやっと「あーそういうことかー」となるんですけど、あんまり向いてないのかな？
皆さんは問題文だけで何すればいいのか分かるんですか？
988デフォルトの名無しさん (ｱｳｱｳｳｰ Sa27-XVJY)
垢版 |
2022/10/04(火) 01:43:10.78ID:s5OlCB28a
入出力例見て推測する方針でだいたい正しいと思う
2022/10/04(火) 02:13:42.65ID:OovsoZ2q0
そこらへんは慣れ
竸プロあるいは数学への
2022/10/04(火) 03:36:56.17ID:iVVbMmK7M
特にその二つの問題は慣れてても難読だから
問題自体の難易度と問題文の読みやすさは独立
2022/10/04(火) 08:06:43.06ID:SSbTCaS5r
形式的に書きすぎな感はあるよな
こどふぉなんかだと一般的な説明の後に、形式的に説明すると～、って二段階の説明があるから分かりやすい
2022/10/04(火) 08:28:01.29ID:wdMm995x0
それはそうと直近のこどふぉの問題文全体的にわかりにくくなかった？
ABも誤読しそうな内容だしCですら最初は頭が壊れそうだったのにDに至ってはsetとかいうゲームを遊んだことがなかったせいでルールの理解までにだいぶ時間がかかったわ
2022/10/04(火) 19:14:27.62ID:bvpWOdzfM
言うほど最近の話か？
2022/10/04(火) 21:06:46.50ID:5od2FDFXM
こどふぉは本当にテストケースから題意を推測することが多い
995デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/05(水) 05:29:59.65ID:hHqeDYjf0
>>986
ありがとうございます。
本が好きなのでつい本を読もうと考えてしまいます。
996デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/05(水) 13:26:30.13ID:hHqeDYjf0
競技プログラミングの問題の設定ですが、わかりやすさを狙ってだと思うのですが、スヌケ君がどうとか
余計な（？）設定が多いと思います。

純粋に数学的に問題を述べてくれたほうが分かりやすいように思います。
2022/10/05(水) 14:22:04.19ID:ijil3GMs0
情報を素早くかつ適切に取捨選択するのも能力の一つだし多少はね
2022/10/05(水) 15:49:05.06ID:PBU6oUE40
こどふぉ次のDiv. 1が遠いなあ
2022/10/05(水) 15:54:00.97ID:PBU6oUE40
と思ったらこのDytechlab cupってDiv.1 + Div. 2でratedなのか
https://codeforces.com/blog/entry/105117
2022/10/05(水) 17:58:45.46ID:KHX87r1NM
改めて次スレ
https://itest.5ch.net/mevius/test/read.cgi/tech/1664700238
10011001
垢版 |
Over 1000Thread
このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 433日 19時間 59分 57秒
レス数が1000を超えています。これ以上書き込みはできません。
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。