競技プログラミングにハマるプログラマのスレ 28

■ このスレッドは過去ログ倉庫に格納されています
1仕様書無しさん
垢版 |
2020/07/25(土) 20:52:15.42
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)やCTFなどを楽しんでる競技プログラマ(競プロer)の雑談スレ
競プロイベントや競プロ問題や有名競プロerや競プロでよく使うアルゴリズム等について語りあったり、競プロ関連の質問相談なんでもおｋ
競プロ初心者でググっても解説読んでも分からないことがあったらスレの競プロの先輩方に訊いてみるのも手だよ(‮よいなれしもかるれくてえ教かと籍書かとトイサ説解いすやりか分‬)
次スレは>>950

# オンラインジャッジ・コンテストサイト
## 日本語
yukicoder https://yukicoder.me/
AtCoder https://atcoder.jp/
AIZU ONLINE JUDGE (AOJ) http://judge.u-aizu.ac.jp/onlinejudge/
## 英語
TopCoder
Single Round Match (SRM) 関係リンク集 http://codeforces.com/blog/entry/21879
Marathon Match (MM) https://community.topcoder.com/longcontest/?module=ViewPractice
※TopCoderは初参加までの手順が煩雑です。まずはググってみて、それでも分からなかったらスレで聞こう！
Codeforces http://codeforces.com/
CS Academy https://csacademy.com/
Project Euler https://projecteuler.net/ 和訳 http://odz.sakura\.ne.jp/proj
※前スレ
競技プログラミングにハマるプログラマのスレ 27
http://medaka.5ch.net/test/read.cgi/prog/1593447074/
65仕様書無しさん
垢版 |
2020/08/01(土) 12:12:52.01
この前のF
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_f

これなんかまさに高難度タイプの実装問題ってイメージがあるな、横からぶつかるか正面からぶつかるかの判定をすればいいというのと、それを二分探索でうまくやればよいというのは水あれば気づける気がするけど、実装がクソ面倒なので黄diffになってる
2020/08/01(土) 15:10:25.03
>>62 >>64
「実装が重い」だけでなく「やるだけ」も含まれるのですね
回答ありがとうございました
2020/08/01(土) 15:28:14.72
>>65
二分探索じゃなくて場合分けでは
2020/08/01(土) 16:30:48.03
場合分けしてから二分探索が必要
2020/08/01(土) 16:59:25.57
場合分けしてるなら二分探索いらなくないか
2020/08/01(土) 17:11:40.40
確かに必要はない
でも実装を考えるなら二分探索のほうが簡単そうだな
2020/08/01(土) 17:45:38.53
ソートして隣接を比較のほうが簡単
2020/08/01(土) 19:01:44.08
そんな言い切るほどの差があるとは思えないが
二分探索から書かないといけない言語は除く
2020/08/02(日) 13:44:43.55
AGC生えてる
2020/08/02(日) 13:56:30.12
旭硝子はAGC
2020/08/02(日) 14:17:38.97
毎回とりあえず110分って書いてるの馬鹿なん？
2020/08/02(日) 14:32:34.91
なんだしなんだしAGCきたな
2020/08/02(日) 15:19:09.08
日曜日コンテストやめてくれ
半沢直樹見れない
2020/08/02(日) 15:45:48.70
> 腕に覚えがある人も、まだまだプログラミングは始めたばかりという人も、一度参加されてみてはいかがでしょうか？

はい沼
79仕様書無しさん
垢版 |
2020/08/02(日) 17:37:48.21
kyopro_friendsの問題苦手なので鬱。
2020/08/02(日) 21:57:59.48
おまえらやってないやろ
2020/08/02(日) 22:00:30.17
30分前に終わった
2020/08/02(日) 22:04:08.66
はやいな
俺は20分前だ
2020/08/02(日) 22:28:54.53
全完多いっすね
2020/08/02(日) 22:40:04.02
なんだこのC問題！？(驚愕)
2020/08/02(日) 22:42:26.97
Cの問題がわからなかった
入力が7の場合答えは何になるの？
2020/08/02(日) 22:45:35.62
>>85
1じゃないの
2020/08/02(日) 22:49:26.17
A
初心者なんだがなにがだめなん？
https://i.imgur.com/mZjwvRx.jpg
2020/08/02(日) 22:50:48.71
if(-40 <= X <= 40)
を消せ
2020/08/02(日) 22:52:35.77
>>88
消してやってもみた気がするんだが
2020/08/02(日) 22:52:39.21
scanfの中&dじゃなくて%dでは
91仕様書無しさん
垢版 |
2020/08/02(日) 22:52:59.98
Fはググるとまんま同じ問題がspojで出ててdrkenさんがソース公開してるから、入力の順番だけ入れ替えてコピペすると通るぞ
2020/08/02(日) 22:54:00.09
あと大体のジャッジでは通る気もするけど最後に改行した方が良い
2020/08/02(日) 22:54:26.53
うしさんのコードは壊れててけんちょんさんのコード貼るとACってそりゃないよ
2020/08/02(日) 22:54:34.31
通常ABCなのに1万人切ってるのか
人減ってきたな
2020/08/02(日) 22:54:49.21
>>90
これだったわ
2020/08/02(日) 22:55:15.62
うわあ
これ受かっときたかったわ
2020/08/02(日) 22:56:23.88
ライブラリ公開してる人がコンテスト中にコード変えて動かなくしたら面白いだろうな
98仕様書無しさん
垢版 |
2020/08/02(日) 22:57:14.18
うしさんのやつ手元では動いたんだけどatcoder上では全然違う値が出てきた
なんでだろ
2020/08/02(日) 22:57:28.03
>>86
77も777も7の倍数だよね
数列の制限はどこから導けば良かったの？
100仕様書無しさん
垢版 |
2020/08/02(日) 23:01:27.54
"初めてkの倍数が登場するのは何項目ですか？"で7は7の倍数なんだから1項目が答えでしょ
それ以上なにが疑問なんだ
2020/08/02(日) 23:02:33.69
>>92
ありがとう
2020/08/02(日) 23:02:34.93
>>100
いや、今わかった…
何項目（め）だったのか…何項目（もく）だと思ってたわ
2020/08/02(日) 23:02:52.04
別に問題が言わんとしてる事はわかったけど「何項」って一般的な言い方なの？
2020/08/02(日) 23:03:39.95
来週のAGOは初心者には難しい？
105仕様書無しさん
垢版 |
2020/08/02(日) 23:05:07.21
少なくとも初項とか第n項とかってのは一般的だし何項目ですか？って日本語に私は違和感覚えなかったけど
2020/08/02(日) 23:09:06.01
>>100
もう一つ聞きたいんだけど7の数列の上限って言語の最大桁でいいの？
2020/08/02(日) 23:14:01.00
>>106
上限などというものはない
108仕様書無しさん
垢版 |
2020/08/02(日) 23:16:56.71
>>106
？？
c++とかでは整数型だと20桁くらいしか使えないからそこまでだけ考えればいいかってこと？
それは明確にNOで、この問題は、1万桁の数字とかをそのまま扱おうとすると破滅してしまうのでうまく処理する方法がないかってのが本質的なところ


例えば(7がnけた)÷kの余りがmだった時は、(7が(n+1)けた)÷kの余りは(m×10+7)%kと求められる(筆算をイメージしてもらうといいかも)から、こうやると何万桁あろうと各桁についてO(1)で処理できる
2020/08/02(日) 23:19:41.74
m×10の発想が出なかったよ…orz
2020/08/02(日) 23:20:34.07
キャスでデュフフ面白い
2020/08/03(月) 01:04:30.32
diff低いな
2020/08/03(月) 01:20:42.79
>>108
なるほど前回の余りに対して検証を繰り返すのか
腑に落ちてないのはどこで-1（回答なし）の判定をするかって点なんだけど、それは無限ループでいいの？
2020/08/03(月) 01:35:13.64
>>112

既に見たことのある余りをもう一度見たらそこからはループするので-1
114仕様書無しさん
垢版 |
2020/08/03(月) 02:40:47.65
kで割った余りが絶対に0以上k-1以下になることに着目すれば、k回計算を繰り返せば絶対に0に到達するかすでに見たことある余りに到達するので(まだ見たことない数字は最大k個しかないため)、今回の制約では必ずTLEにならずに>>113の方法で解けるんすね
もっと言えばすでに見た数字を配列とかsetとかで管理しなくても、適当にk回ループ回して0に到達するかどうかみるだけでも通る
115仕様書無しさん
垢版 |
2020/08/03(月) 02:52:52.05
茶色がフツーに優秀な時代が
2020/08/03(月) 03:00:22.26
鳩の巣原理
2020/08/03(月) 05:13:23.48
で、CのK<=10^12での解法が結局思いつかないんだけど誰か教えて
118仕様書無しさん
垢版 |
2020/08/03(月) 06:30:59.26
editorialは読んだ？
iを求める問題は離散対数問題そのもの
2020/08/03(月) 07:41:08.06
オイラーの定理でa^φ(L)≡1だからφ(L)を求めて、その約数を小さい順から試していくとか？
2020/08/03(月) 08:06:20.53
>>113,114
kが上限か！！
やっと理解できた・・ありがとうございました
2020/08/03(月) 08:12:28.49
>>113
7の数列は倍数の列じゃないからループしなくない？
2020/08/03(月) 08:55:53.44
なんだその理屈?
2020/08/03(月) 09:14:53.95
最近コンテスタントのレベルかなり上がってね？
2020/08/03(月) 09:17:09.72
検索したらレピュニット数が出てきたので、1、11、111、・・・の列には2や5で割れる数は出てこないこともわかった
逆に、2と5以外の素数は必ず割り切れるし、2と5の倍数以外の全ての自然数で割り切れることも証明できる
2020/08/03(月) 09:28:41.74
>>122
10m＋7だから商に規則性が無い
126仕様書無しさん
垢版 |
2020/08/03(月) 09:30:56.46
前回の株のやつとか、今回のDみたいにエスパー早解きされる系を
ちゃんと証明して解こうとして乗り遅れるのつらい
2020/08/03(月) 09:35:44.41
>>126
Fまで証明でいければ順位上がるくね？

ところでC解けなかったのに、解説ACしたらコード短すぎて泣いたわ
2020/08/03(月) 09:50:05.79
>>125
それの繰り返しだから規則性あるだろ
129仕様書無しさん
垢版 |
2020/08/03(月) 09:55:40.36
>>125
10m+7のmになにが入るかのみが問題なので、mに入る数が高々k通りしかなければk桁目までみることで必ずループに入る
2020/08/03(月) 10:42:12.28
>>125
商じゃなくてあまりだけが問題だよ。あまりは有限通りしかないので必ずどこかで同じのが出て、以降の並びは同じになる。
フィボナッチ数列を任意の数でmodを取ったものが必ずループする、とかも似たような話。
131仕様書無しさん
垢版 |
2020/08/03(月) 11:10:04.88
今回のCはこれ知ってたから一瞬だったわ
https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%90%88%E5%90%8C%E6%B3%95
132仕様書無しさん
垢版 |
2020/08/03(月) 11:11:12.82
厳密にいうと違うけど
2020/08/03(月) 11:13:36.62
で、Eはどうよ。解の二分探索できた奴どれくらいいる？何色？
2020/08/03(月) 11:16:21.53
difficulty的にも水くらいならだいたい解けてるんじゃないか
135仕様書無しさん
垢版 |
2020/08/03(月) 12:16:49.86
何かの値を決め打ちすると単調性があるのでにぶたんできる、ってタイプの問題は初めてだと気づきにくいけどわりと出題されるので、慣れると一瞬で解ける
線形探索が間に合わなさそうな時orきつそうな時はそうやると結構な確率でうまくいく

水色ですがそういう問題を何回か解いたことがあったのですぐいけました
2020/08/03(月) 12:44:57.86
似た問題は解いたことあったが気付くの時間かかってしまったなあ。

問題解放フローチャートみたいの作っておいたら、気付くの早くなるかも？

全探索できる？
二分探索できる？　みたいの。
脳内でやれば良いだけだが、慣れないうちは図示することで気付きやすくなるかも。
2020/08/03(月) 14:12:56.77
https://www.itmedia.co.jp/enterprise/articles/1002/06/news001_3.html
昔これ読んだことあったからすぐ解けた
2020/08/03(月) 15:41:13.87
似たようなのが蟻本に載ってるってのもあるね
2020/08/03(月) 17:14:19.63
10年前ならこれ解けたら黄コーダーくらいかな
2020/08/03(月) 19:23:39.09
>>137
2ページ目の「非常に狭い世界に閉じこもって、プログラムが十分に組める“つもり”になってしまっているだけではないでしょうか？」、
近頃の競プロまわりの論争を見ているとなんとも皮肉だな
2020/08/03(月) 19:23:54.82
B Extraの投票500点が多いけど簡単にできるの？
142仕様書無しさん
垢版 |
2020/08/03(月) 20:40:23.21
E,pythonだとフツーにTLEするので何とかしてほしい、せめてpypyとnumpyを同時に使えるように・・・・
2020/08/03(月) 20:44:36.52
？昨日のEならPythonで余裕だろ
2020/08/03(月) 21:00:22.86
どんな実装してんだそれ
2020/08/03(月) 21:08:41.57
言語のせいでMoをやってTLEした人はかわいそう
2020/08/03(月) 21:10:15.47
簿記で人生詰んでる競プロer可哀想
2020/08/03(月) 21:37:11.05
Eはにぶたんのループを何も考えず100回にしたら1500msくらいかかったから、実装雑だと落ちそう
ループの終了条件をr-l<1e-9にしたりしてないかな？
2020/08/03(月) 22:08:54.12
結局切り上げにするんだから整数で二分探索すればいい
ということはループも30回でいい
149仕様書無しさん
垢版 |
2020/08/03(月) 22:33:40.00
100回ループしたところでループ回数は2×10^7でしょ
まともな言語なら1500msもかからないと思うんだけど
2020/08/03(月) 22:56:02.51
pythonはN=4000でO(N^2)が間に合わなかったりしたことがあるので全然あり得るかと
151仕様書無しさん
垢版 |
2020/08/03(月) 23:36:21.61
一番重いのが、二分探索のなかでA/cを足していくところで、
それでも二分探索の回数* N程度なのにどーなってんのと・・・
2020/08/04(火) 00:26:17.11
pypyで何の問題もなく通ったよ
153仕様書無しさん
垢版 |
2020/08/04(火) 00:54:22.34
パイパイはよくお世話になるけど、ベクトルのまま処理できるような書き方が正義だと思ってるので、極力numpy使いたいでござる・・・・
2020/08/04(火) 01:13:17.64
>>146
ぼきさんって簿記三級？
橙になる脳味噌があるなら簿記なんかどうにでもなりそうなものだけど。なんにしろ頑張ってほしい。あっとこ副社長にでも相談すりゃいいのに。
2020/08/04(火) 01:36:12.47
2級だと思う
156仕様書無しさん
垢版 |
2020/08/04(火) 01:54:35.50
DBと機械学習、時系列解析を駆使して会計学を踏み潰してアップデートできそうなものだが・・・
2020/08/04(火) 02:28:24.10
面接で絶対言われてるはずだけど本人がその条件を呑んで、結局落ちたんかな
2020/08/04(火) 02:46:25.30
プログラマが簿記覚えるとなんかできること広がりそう
2020/08/04(火) 03:38:34.55
能力的には余裕だろうけどぼきさんは一夜漬けでなんとかならないからな
2020/08/04(火) 06:21:24.59
ぼきさんだから3級だろう。さすがに入社前に2級落ちたら内定取り消しは厳しすぎる
2020/08/04(火) 06:29:26.31
前時代的な表の表現と
試験時電卓必須ときいて
うんざりしてやめた
2020/08/04(火) 06:34:55.61
>>158
複式簿記というシステムの仕様に詳しいってだけの話
独立した時に確定申告が自分でできる程度だよ
2020/08/04(火) 06:41:15.43
前時代的て言われても代わりのものなんてないんだけどな。複式簿記の叡智はゲーム脳の競プロerには難し過ぎて理解できないのかもしれん
2020/08/04(火) 06:49:55.08
ほんの数年前だが
数字と項目名を同じ列に書くように指導されていた記憶があるが
俺の気のせいか？
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況