X

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

レス数が1000を超えています。これ以上書き込みはできません。
2022/12/26(月) 12:47:37.63ID:CkzYHyzir
!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/

※前スレ
競技プログラミング総合スレ 64
https://mevius.5ch.net/test/read.cgi/tech/1664700238/
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
2022/12/26(月) 14:43:41.21ID:0EESOEy50
新スレ乙
2022/12/28(水) 11:48:49.25ID:a6/n2za+0
社長曰く以外の感じなので、例えばバックエンドエンジニアで良い評価が欲しいなら青色くらい必要
https://twitter.com/chokudai/status/1474258242452987907

AtCoderがそのまま役立つ業務ってだいぶ少なくて、
【評価高】は赤まで、
数理最適化・研究開発
【評価中】は青～水まで、（黄もまれに？）
バックエンドエンジニア・機械学習エンジニア
【評価低～評価無】は水～茶色まで、
その他のITエンジニア

くらいがプラス評価になります。関連度が高ければ高いほど高いレートが評価されやすくなり、逆に低いと低いレートですぐカンストしちゃう、って感じ。

評価低に関しては「コードが書けることが保証されてる」くらいのアピールにしかならないです。
https://twitter.com/5chan_nel (5ch newer account)
2022/12/28(水) 11:49:39.60ID:a6/n2za+0
以外の感じ、じゃなくて、以下の感じ
2022/12/29(木) 14:44:42.37ID:QPTCFirgr
どっちも過疎ている😭
2022/12/29(木) 16:06:10.95ID:NFGqah83a
年末年始こそ暇なのにコンテストがない
2022/12/29(木) 17:01:03.30ID:w08nm0DJ0
その点こどふぉはいつでも何かしらやっているという安心感がある
https://codeforces.com/blog/entry/110638
2022/12/29(木) 17:03:59.96ID:9T4aEcS90
問題文によってX軸とY軸がどの方向か明記されていない場合どうすれば良いのでしょうか

左右方向がX軸
上下方向がY軸
と思って解いていたら解説の画像見ると真逆でした

例えば鉄則本のB09 - Papers
2022/12/29(木) 17:05:49.24ID:w08nm0DJ0
>>3
プラス効果実感できそうなのが青くらいというのはそうなのかもしれない
茶色以上だったら、ないよりはある方がマシって場面はたくさんあると思うけどね
こんなのセルフプロモーション力次第だから、そこがヘタクソだと何色でも…というところがあるかな
2022/12/29(木) 17:10:50.36ID:axYNlbu7r
やっぱりh-w表記が1番やね
2022/12/29(木) 17:15:02.16ID:w08nm0DJ0
>>8
本持ってないので確認できないけど、確かに普通数学では左右がx軸、上下がy軸方向で書かれることが多いからちょっと混乱する人もいるかも
問題見た限り、答えに影響しないのでどっちで書いてもいいってことで、逆に書いたんじゃないかな
ちなみに競プロだと配列の添字の関係で逆に書く場合のメリットもあるんだよね（この問題はそのメリットも別にないけど）
明記されてない場合はほぼ答えに影響しない場合だから、勝手に自分の中で決めればいいと思う、影響するんなら質問タブから聞こう
2022/12/29(木) 17:16:36.67ID:w08nm0DJ0
>>11
ごめん、思い切り多次元配列使うから普通にメリットあったね
2022/12/29(木) 17:19:36.13ID:oSKPPGt3a
軸の方向なんてだいたいどうでもいいよ
自分の好きに描いてくれとしかいえない
向きの考慮必要な問題なら普通は記載されてる

ただまあ実装としては配列操作の都合上、どっちかのほうが簡単になることはあるので、
賢いひとだと考察や実装しやすいように柔軟に向きを入れ替えてるかな
2022/12/29(木) 17:22:41.23ID:9T4aEcS90
>>11
＞＞答えに影響しないのでどっちで書いてもいいってことで、逆に書いたんじゃないかな
ありがとうございます
2022/12/29(木) 17:32:05.96ID:eomnc8IgM
業務プログラミングでも画像処理やってるとたまに軸の順番が入れ替わるから困る
2022/12/29(木) 17:34:19.09ID:eomnc8IgM
googbyeみたいに定期的にall ratedコン出せるのすごいよな
逆にAtCoderが厳格すぎる
2022/12/29(木) 17:53:57.43ID:YzoArJYh0
質問
apg4bが終わったばかりの競プロ初心者だけど、次に読めばいい本は3つのうちのどれですか？
・競技プログラミングの鉄則
・問題解決のためのアルゴリズム×数学
・アルゴリズムとデータ構造
2022/12/29(木) 18:06:03.05ID:TesRzOIcr
全部いらない
2022/12/29(木) 18:10:47.93ID:axYNlbu7r
apg4b終わった時点でも人によってどのくらいの行間を読めるか違うから一概に言えない
実際に書店とかで読んで選んではどう？
2022/12/29(木) 18:13:58.61ID:axYNlbu7r
俺は蟻本にしたけど中級編辺りからきつくなった😭
2022/12/29(木) 18:54:14.77ID:fxGsZcMtd
新しい本だから今取り組んでる人が多いという理由で鉄則本かなあ
〇〇本を読んで上達したみたいな話は聞かないから
結局自分の努力次第だよね
2022/12/29(木) 18:59:57.08ID:oBwaLSHSM
AtCoder Problemsで自分のレートに近いdiffの問題解いていくのが結局一番着実だったりする
2022/12/29(木) 19:01:07.31ID:zROXqcZ10
蟻本完璧に咀嚼しきれたら青〜黄色はいけると思うしアレは中級者向けでしょ
螺旋本は教養としては大事だけど傾向が若干違う気もするし鉄則本かけんちょん本が良さそう
2022/12/29(木) 19:02:10.21ID:zROXqcZ10
結局本とかで勉強するよりも自分の実力ちょい上の問題を解きまくる方が効果あるのは事実
2022/12/29(木) 19:06:55.24ID:fxGsZcMtd
蟻本完璧なら橙までいけると言われてるから
2022/12/29(木) 19:16:19.36ID:oBwaLSHSM
黄色より上は知識とは別体系の技能だから、本読んでどうこうって感じの世界ではないかな
2022/12/29(木) 19:32:12.24ID:bDkXL6yD0
蟻本は難易度的には、第2章が普通に初心者向けの内容だし、初心者でも読めるでしょ
ただジャッジがPOJとかだったりして不便、という理由があるために今どきの入門者向けではないかなあ

基礎問題のあとにいきなり難易度が上がった問題が出てきたりするけど、そういうのを飛ばせば誰でも読めるだろうし、
そういうのも全部習得していけばABC卒業できるほどの基礎力が付く

鉄則本は基礎問題が中心に載ってて、解説もわかりやすいから、数学力に自信のない初心者にはとてもおすすめ
28デフォルトの名無しさん (ﾜｯﾁｮｲ 6b7a-V47g)
垢版 |
2022/12/29(木) 20:01:46.63ID:iTlEyNON0
おじさんが学生の頃は螺旋本読んで蟻本読んだら青になれた
最近は新しい本出てるらしいけど読んだことがないので何色向けか分からない
2022/12/29(木) 20:49:26.60ID:w08nm0DJ0
・数学の得意不得意
・プログラミングの経験
この二つで結構勉強方針変わるかも
2022/12/29(木) 21:06:10.84ID:bDkXL6yD0
そうそう、初心者向けじゃない競プロの本なんてないけど、地力の違いでどれがフィットするかはちょっとずつ変わるよねえ
2022/12/29(木) 22:02:33.33ID:wCOIbN16H
数学そんなに得意じゃない場合、大学数学の場合の数や整数の参考書が役に立つこともある
2022/12/29(木) 22:12:00.98ID:wCOIbN16H
あ、大学数学じゃなくて大学受験な
大学数学も実は役に立つ本あるんだが
2022/12/29(木) 22:32:16.32ID:w08nm0DJ0
今日仕事納めで調子に乗って酒飲みすぎた
2022/12/29(木) 22:35:00.36ID:w08nm0DJ0
>>30
蟻本も人によってはくどくなくてちょうどいい入門書だからね
2022/12/30(金) 00:20:49.75ID:Jg6kHZTu0
数学は特に得意でも不得意でも無いよ
あと、プログラミングの経験はほとんど無くてAPG4bが初めてと言っても過言では無いと思う
上で挙げた3つの本の他にけんちょんさんが書いてるAtCoder入門なんかも良さそう
2022/12/30(金) 00:23:54.34ID:Jg6kHZTu0
>>31
整数とか場合の数も暇な時に復習します
2022/12/30(金) 09:42:02.64ID:SISDjQCo0
AtCoderも年末年始にコンテスト欲しいわ
2022/12/30(金) 09:57:28.45ID:H46YuG/U0
運営がワールドワイドならそれも可能だろうけどこれはしゃーねえべ(´・ω・`)ぽれはお盆の時期とか出たくないのに逆にコンテスト生やしてくるし
2022/12/30(金) 12:12:30.73ID:1cdhane2r
俺も正月はいいや、暇だけど実家だから回線悪い(´・ω・｀)
2022/12/30(金) 12:51:42.69ID:E9c39SFN0
ｍｈバチャしようぜ！
2022/12/30(金) 12:52:06.77ID:E9c39SFN0
ｍｈは謎の入力ミス
2022/12/30(金) 14:52:31.97ID:DWxAyMkpM
整数と場合の数だと大学への数学のやつかな
あれを全部スラスラ解けるぐらいにしとくと捗る
43デフォルトの名無しさん (ﾜｯﾁｮｲ e355-s0Sd)
垢版 |
2022/12/30(金) 14:57:53.70ID:3r6Oj/Bn0
初等整数論とか組合せ論の初歩についてあまり詳しくないけれど、
プログラミングコンテストでは強いっていう人はいるんですか？

プログラミングコンテストで強い人はみな数学にも強いのではないですか？
2022/12/30(金) 15:18:16.52ID:jg66J2pLM
プログラミングコンテストにもいろいろあって、競技プログラミングのアルゴリズムという分野のコンテスト（具体的にはAtCoderのABC、ARC、AGCは全部そう）は、整数、組合せ論の問題が離散数学の一部として出題されるので、もろに成績に関係する
一方で、ヒューリスティックだったりKaggleに関しては、実はそうでもないんじゃないかという気がする
当然、基礎的な能力として、整数と組合せ論を最低限勉強しておいた方が離散数学的な操作に慣れて思考の助けになるところはあると思うし、勉強さえすればレベルの高いところまでできるような人がいずれのコンテストでも上に来ると思うけど
2022/12/30(金) 15:41:25.54ID:SISDjQCo0
組合わせ論・数論の精選とかパーフェクトマスターみたいな数オリ用対策用の参考書って競プロにも役立つの？たまに買ってる人見かけるけど黄色以上で効くのかな
2022/12/30(金) 15:43:17.20ID:bLivZhNAM
競プロに必要なことは競プロで身につく派
47デフォルトの名無しさん (ﾜｯﾁｮｲ e355-s0Sd)
垢版 |
2022/12/30(金) 15:47:04.57ID:3r6Oj/Bn0
繁野麻衣子著『ネットワーク最適化とアルゴリズム』を買いましたが、積読状態です。
この本は競技プログラミングに役立ちますか？
2022/12/30(金) 15:54:21.28ID:1cdhane2r
あっとこなら問題解くだけで良さそう
2022/12/30(金) 15:58:00.92ID:jg66J2pLM
いつだったか、数オリ高度典型の幾何がAGCかARCに出てて話題になったからごくたまに効くんじゃないか
2022/12/30(金) 16:03:39.51ID:mLpRFjn60
>>47
未読なので目次見ただけだけど、この本のアルゴリズムは全部競プロで頻出だと思うので、知らない知識を摂取するって意味だとどれも役立ちそうかな？
51デフォルトの名無しさん (ﾜｯﾁｮｲ e355-s0Sd)
垢版 |
2022/12/30(金) 16:10:15.82ID:3r6Oj/Bn0
>>44,48,50
ありがとうございました。

>>50
読んでみます。
2022/12/30(金) 18:13:16.86ID:EYdMYpIMM
純粋な学術書は体系的すぎて競プロで使うには多く説明しすぎてることもあるから、効率がいいかはわからんな
ただ、普通に競プロ関係なく勉強になるところはいい
2022/12/30(金) 18:23:53.70ID:iKE0Xuujr
最悪計算量と何ができるか知ってるだけでも競プロでは使えるな
順位クエリ処理できる二分探索木の仕組み分かってないけど他人のライブラリコピペして使ってるわ
2022/12/31(土) 13:45:22.58ID:iNV3O62Z0
新年ABCもう三つも入ってるのか
2022/12/31(土) 13:50:39.96ID:Yd+ifoMYa
なかなか灰色から上がることが難しそうですね...
とりあえずアルゴリズム×数学 本 か鹿本(AtCoder入門)を買ってみませんか
茶色に上がってみましょう
2022/12/31(土) 13:51:25.78ID:iNV3O62Z0
和を積に変換
https://twitter.com/noshi91/status/1608869946792235008

和のままで十分性質がいいじゃん！と先入観で思ってしまうが、あえて多項式を使った式を介して積にした方がtop treeに乗せやすいみたい
面白い
https://twitter.com/5chan_nel (5ch newer account)
2022/12/31(土) 13:54:08.95ID:iNV3O62Z0
>>55
数学が苦手な人は入茶でもかなり時間かかる時代な気がするね
灰色を分割して階級をさらに分けるのは真面目にありだと思ってるけど
2022/12/31(土) 14:48:43.15ID:kgmqtCAB0
toptreeとか初めて聞いたわ
2022/12/31(土) 14:50:30.16ID:VUYQSQV/M
部分列（連続ではない）の和の総和は[x]Π(2+ax)か
この場合はそんなに役立ってる感ないが
2022/12/31(土) 15:00:28.46ID:++4zxiH/M
TopTreeて高度典型みたいなやつだろ
俺も名前しか知らん
2022/12/31(土) 15:07:27.00ID:ST9eXwUwM
LC木の上位互換でLC木に乗らないものが乗ったりするが、そもそもLC木自体がマニアックでAtCoderではなかなか使用機会ないだろうな
強いデータ構造がなきゃ解けない問題、強いデータ構造で一瞬で解けてしまう問題をAtCoderがそもそも好まないというのもあるし
2022/12/31(土) 15:33:19.70ID:ST9eXwUwM
データ構造に載せるモノイド、頑張れば多項式か行列に帰着できる説
2022/12/31(土) 15:51:06.59ID:uDVZ4h8P0
半束とかはモノイドだけど多項式や行列にはならなくないか
2022/12/31(土) 16:04:37.43ID:ST9eXwUwM
適当に和に相当する演算を導入して半環の積にできんかとか考えたけど無理か
2022/12/31(土) 18:13:36.09ID:iNV3O62Z0
あまり半束であって束じゃない例について考えたことなかったけど根付木のLCAとか？
66デフォルトの名無しさん (ﾜｯﾁｮｲ 1a55-9yt5)
垢版 |
2022/12/31(土) 18:22:00.74ID:zJ9NYHz+0
>>65
ところで、束論はどの本で勉強しましたか？
離散数学の本にすこしだけ書いてあることがありますが、役に立ちますか？
2022/12/31(土) 18:40:09.52ID:iNV3O62Z0
>>66
min, maxの一般化であるってことと定義を知っているってだけで、まともに勉強したことないかなあ
どこで最初に知ったんだろ、雪江代数にあったっけ？
ゼータ変換を束を使って捉え直すことができるみたいなのはあった気がするけど、束論自体をつきつめることが直接競プロにプラスになる感じではない印象
というか、抽象代数の勉強は全般的にそんな感じな気がする
2022/12/31(土) 18:59:35.78ID:zUUU5DPH0
(1+a_k)の積を微分していったら定数項に基本対称式が全部出るのか 嬉しいかなあ
2022/12/31(土) 19:05:33.95ID:iNV3O62Z0
今日日モーメント母関数がそんなにうれしいものなのかという話になりそう
2022/12/31(土) 19:28:10.86ID:fzjWly+gM
何の捻りもないけど、セグ木にのせてrange M次対称式 query（与えられた区間内の要素のM次対称式を出力）がQMlogNで解ける
2022/12/31(土) 19:33:39.16ID:fzjWly+gM
と思ったけどlogMつくか
更新ないんならセグ木に乗せるんじゃなくて累積和でやる方がいいな
2022/12/31(土) 23:33:15.73ID:iNV3O62Z0
どっかで出てそうと思ってelementary symmetric polynomials segment treeとか検索してるけど意外とないもんだ
73デフォルトの名無しさん (ﾜｯﾁｮｲ 1a2f-ed2K)
垢版 |
2023/01/01(日) 10:08:11.89ID:30E/zMtT0
https://nunjuk.in/35c41f
74デフォルトの名無しさん (ﾜｯﾁｮｲ 1a55-9yt5)
垢版 |
2023/01/01(日) 10:12:49.91ID:+0Q+h7mh0
>>67
ありがとうございました。
2023/01/01(日) 13:05:49.08ID:jk3nqRU4M
初ARC初AGCはいつ入るか
2023/01/01(日) 17:23:02.16ID:HtIB66xPr
鯖のcpu性能が上がったせいで過去の問題が別の解法(計算量悪化)で通せるようになることってあるのかな？
パソコン新しくしようとしてて気になった
2023/01/01(日) 17:35:44.53ID:jk3nqRU4M
N=2*10^5だとガチガチにチューニングしたC++で非想定が通ってしまうからN=3*10^5にしたみたいな問題だと、普通に非想定通るようになってそうだな
2023/01/01(日) 18:51:37.63ID:BuEF5d0U0
2014年くらいの問題でそういうのあったと思う
2023/01/02(月) 16:31:00.87ID:5iFotiMhM
お、ARC生えたか
2023/01/02(月) 18:38:41.71ID:1lMhDqk90
ABCと土日逆転してるのって何か意味あるのかな
2023/01/02(月) 19:37:24.20ID:Bxk6jeghM
土夜と日夜だったら普通の人は土夜の方が予定入りやすいとかあるんかな
2023/01/02(月) 22:43:11.18ID:xXWO03uC0
日曜ははよ寝たならんか
2023/01/02(月) 22:49:42.58ID:mvKrG9xT0
テレワークで出勤時間なくなってからは24時までに寝られれば十分になった
84デフォルトの名無しさん (ﾜｯﾁｮｲ 5bb3-3363)
垢版 |
2023/01/03(火) 00:54:06.77ID:u0M4IWsD0
AtCoderの過去問って他人の提出検索できるけど、case_11.txt だけ間違えてるやつ一覧みたいのって取ってこれるんかな？
2023/01/03(火) 01:00:58.84ID:l1uyhUQar
同じようなテストケース通し具合のコードを持ってくるサービスあった気がする
探したけど見つからなかった
確か赤コーダーTLで見つけたはず
86sage (ｵｯﾍﾟｹ Srbb-A544)
垢版 |
2023/01/03(火) 01:14:46.33ID:3U7/noadr
>>84 >>85
もしかして: AtCoder Companions
2023/01/03(火) 01:39:20.81ID:5KR4gJydM
言語仕様の勘違い由来のバグ取りはかなり気付くの難しいから、初心者がそういうの見つけるのに使えそうだな
2023/01/04(水) 01:26:53.42ID:WeNv9SlE0
今年こそ青に定着したいのに三が日何もやってねえ...(´・ω・`)
2023/01/04(水) 08:04:52.46ID:aNwmJoG10
正月で生活リズムが整っちゃってこどふぉに出られなくなっちゃった
2023/01/04(水) 15:05:35.57ID:JS//sD6wM
Hello 2023普通に良コンテストだったぞ
ドンマイ
2023/01/04(水) 22:15:22.80ID:vSzNCwvu0
えAtCoder Companions有能すぎるんだけど. これ何でテンプレ入ってないん?
2023/01/04(水) 23:19:19.62ID:mr/FCdH/0
TL少し長めの問題なら、10^9回計算する解法でも通るんだね（想定解法じゃなかったけど）
2023/01/05(木) 06:17:26.70ID:7AKtp3Yz0
重複組合せの式nHrで、整数のオーバーフローをできるだけ避けて計算したいのですが

とある、場合の数を数える問題で、普通はたぶんDP的に解くんだけど、規則的な形だった
ので、「これって重複組合せじゃん」と見抜いたんですよ
でnHrを例の階乗の公式(n+r)!/n!/r!で計算して、テストケースを走らせるとnやrが小さい
のは通るのでやはりおkらしい。ただnやrが大きくなると階乗がオーバーフローしてしまう
解が数式で求まったのに数値的にはそんなに便利じゃないって?

でも普通nHrの計算って分子と分母でキャンセルして結果は大きくならないことが多い
ですよね。うまいこと変形したらオーバーフローしなさそう。もしそういうのが既にあれば
nHrの漸化式みたいので計算する手もありそう、って結局DPみたいなことしてる気がw
2023/01/05(木) 10:09:29.03ID:36BPqP5u0
ちなみにnとrはどういう大きさの値？
2023/01/05(木) 10:51:51.53ID:7AKtp3Yz0
>>94
どちらも2から60ぐらいの間の整数がランダムな感じでセットされるようです
2023/01/05(木) 11:18:12.30ID:36BPqP5u0
>>95
(n+r)!/n!/r! = n+r C r
と変形して、あとはKnuthのTAOCPに載ってるオーバーフローしにくいやり方で組み合わせを計算してみよう
https://stackoverflow.com/questions/1838368/calculating-the-amount-of-combinations/1838732#1838732
97デフォルトの名無しさん (ﾜｯﾁｮｲ 362a-3363)
垢版 |
2023/01/05(木) 12:36:04.14ID:BpZRjrYb0
パスカルの三角形で計算する方が確実かな
2023/01/05(木) 12:51:55.08ID:7AKtp3Yz0
>>96
どうもです。が、n, mは実際には100ぐらいまでいくようで（すみません）、
リンク先の最初のコードだと 100 C 99 とかで間違った答えが。おっとクヌース先生敗北?

こういう場合は普通にCの性質より 100 C 99 = 100 C (100-99) = 100 C 1 とすれば
精度も計算量も良さそうです
というわけで... 全テストケースクリアしました! ありがとうございます
2023/01/05(木) 13:03:57.95ID:dpF3fKIy0
100C50はint64に収まらないからね
2023/01/05(木) 13:23:09.26ID:7AKtp3Yz0
>>99
そうですね、nCrで r=n/2付近はでかい数になりますよね
テストケースではそういう場合は除外されているようです

そういうわけで、組み合わせを直接計算するとテストケースでは64bit整数がいるんですが、
組み合わせの直接計算でなく、DPで再帰的に場合の数を計算するようなコードだと
32bit整数で大丈夫な感じなんですが... ええと
2023/01/05(木) 13:39:53.75ID:7AKtp3Yz0
ああそうか、それが実質的には >>97 パスカルの三角形を上向きに登っていくのと等価なの
かな。三角形がでかい場合はあんま三角形の底辺の真ん中の方には行かない場合のみで
と自己納得w
2023/01/05(木) 14:48:33.70ID:WkAYqVn/d
よくわからんけど答えが32bit整数に収まる程度なら適当に大きめのmodとればいいんじゃないの
2023/01/07(土) 18:03:15.80ID:Fs1C7h8fp
ARC3週連続か
2023/01/07(土) 19:51:43.95ID:SPR4wSEy0
ARC生えまくり
嬉しいけど息切れしないか心配
105デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 22:45:57.01ID:LoL6HnAVa
Dの解説読んでもわけわからん
まず、割り切れるのがわかってるんだから、iの最大値なんて関係なくない？

iの2乗で割り切れる時に解が見つかるとして計算したけど時間内に解が求められなかった。
糞問題じゃないのこれ？
2023/01/07(土) 22:47:21.33ID:j8FCEvhl0
どんまい
2023/01/07(土) 22:47:32.24ID:/Ri7nxfpM
解けなかったら糞問
で、おまえのレートは？
2023/01/07(土) 22:49:07.34ID:e3AWo2MYp
Dで素因数分解出来ることが保証されてるのが頭から抜けてたせいで絶対想定解じゃないだろって思いながら無駄にミラーラビン素数判定法とか使ってしまった
2023/01/07(土) 22:51:15.35ID:e3AWo2MYp
素因数分解出来ることっていうより素因数分解の一意性か
2023/01/07(土) 22:52:05.10ID:SPR4wSEy0
問題は全然クソじゃないと思うけど、i=1,2,…,⌊N^(1/3)⌋のうち、N が i で割り切れるような最大の i って書き方が何か変で、i=2,…,⌊N^(1/3)⌋のうちNを割り切る最小のiと言った方が正しいような気がする
2023/01/07(土) 22:54:54.84ID:SPR4wSEy0
G、本質パートからしてボリュームあるのにさらに任意ｍod二項係数使うんかいって思ったけど、想定解は全然使ってなかった
2023/01/07(土) 22:57:18.84ID:SPR4wSEy0
>>105
ちなみに、そのやり方でTLEしないと思うんだけど、N^(1/3)までで探索打ち切った？
113デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 22:58:15.60ID:LoL6HnAVa
あー、二乗の計算時間もだめだってのか。効率化難しいな。
sqrt使うところに頭が向かわなかったわ。
お前らよく解けるねこれ...
114デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 22:59:01.50ID:LoL6HnAVa
>>105
打ち切った。でもダメだった。
2023/01/07(土) 23:00:27.31ID:j8FCEvhl0
Dは想定回じゃなくても、いろんなテクで解けるし、みんないずれかの解法にサクッとたどり着いてる感じだな
2023/01/07(土) 23:01:13.52ID:SPR4wSEy0
>>113
なんかその書きぶりだと、もしかしてj^2 = N/iになるようなjも探索で出した感じ？
2023/01/07(土) 23:01:47.41ID:e3AWo2MYp
Eが素直なDFSすぎてDと逆でも良いだろとは思った
2023/01/07(土) 23:03:43.12ID:SPR4wSEy0
Eはむしろ個人的には意表を突かれた感じでギョッとした
Fの方が実は素直にロリハやるだけだったりする
119デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 23:04:53.24ID:LoL6HnAVa
>112
すまん、冷静に考えたら打ち切ってない
必ず1個の解が見つかるはずで、解が見つかったら打ち切ったら良いんだから、N^(1/3)までカウントアップしないと思ったんだ。だから、N^(1/3)で止めるロジックは無意味だと思ってる。

ただ、自分のやり方だと解を二乗根に絞って計算したせいで最大値がN^(1/2)/2になってしまったんだね。
そのせいか...
120デフォルトの名無しさん (ﾜｯﾁｮｲ 11bd-vxq+)
垢版 |
2023/01/07(土) 23:06:46.63ID:SPR4wSEy0
>>119
>必ず1個の解が見つかるはずで、解が見つかったら打ち切ったら良いんだから、N^(1/3)までカウントアップしないと思ったんだ。だから、N^(1/3)で止めるロジックは無意味だと思ってる。
確かにそれはそう、ナンセンスな質問ですまない
O(N^(1/2))になってたのがTLEの原因っぽいね
2023/01/07(土) 23:08:57.85ID:j8FCEvhl0
EやFはサクッと解けたけど、おれもDはちょっとギョッとしたよ
おれも数学弱だな
てかEなんてほぼナイーブで解けるレベルに感じたし、500点問題としてはあまりにも簡単すぎでは
2023/01/07(土) 23:47:37.23ID:XF8T3NwUM
Ex、Polya の原理や包除原理知ってても簡単に見えないし、ABCで出した理由は有名問題だからなんかな
2023/01/07(土) 23:49:55.07ID:XF8T3NwUM
というか、GみたいのもOEISにあるのな
この問題用に出てきた謎の量にしか見えなかったが
2023/01/08(日) 00:04:08.29ID:lAEXMGQ20
なんちゃらのフルイ使わないでやったらTLEして
脳死で数値設定したら足りなくてWAした雑魚
125デフォルトの名無しさん (ﾜｯﾁｮｲ 5bba-wqvi)
垢版 |
2023/01/08(日) 01:25:51.19ID:4thZdV2f0
ついこないだライブラリ作ったポラード・ローの高速素因数分解でDをしばき倒せたので良かった
2023/01/08(日) 11:32:11.67ID:4xTAT7w0a
Dは簡単すぎて本当にこれでいいのか何度も見直したんだが

まず2から順に素数で割っていって割り切れたものがpかq
さらに同じ数で割って割り切れたらp確定
その場合はp*pで割った商がq

割り切れなかった場合はその素数がqなので割った商の平方根がp
2023/01/08(日) 11:59:00.32ID:VXOhkNVAd
それの計算量解析ができるか？って問題だからな
2023/01/08(日) 12:11:35.54ID:4xTAT7w0a
できるだろ
素数の判定・列挙はO(sqr(N))
2023/01/08(日) 12:14:36.88ID:xVz3ul4wp
そうじゃなくて小さい方がNの平方根で抑えられるかを見抜けるのが本質では
2023/01/08(日) 12:14:57.98ID:xVz3ul4wp
平方根じゃなくて立方根
2023/01/08(日) 12:16:33.74ID:PLtXzXPr0
>>128
N≤9×10¹⁸ なのでそれではだめ
2023/01/08(日) 12:17:04.65ID:4xTAT7w0a
ていうか小さい順に割っていくならpとqの最大値で最も時間がかかるからO(root3(N)*T)
2023/01/08(日) 12:17:37.84ID:4xTAT7w0a
>>131
なんでよ？
2023/01/08(日) 12:22:05.66ID:xVz3ul4wp
>>133
p,qのうちの大きくない方は必ずNの立方根(2×10^6程度)になって、昇順から自然数を見ると割り切れた時点で素因数なのは確定するから素数の判定は実は関係ない(だからp,qが最悪ケースの√N(10^9オーダー)であっても素数判定をする必要はない)っていうのがDのポイントだと思う
2023/01/08(日) 12:23:24.79ID:PLtXzXPr0
>>132
ああ、そこを見積もりできてるならおｋ
2023/01/08(日) 12:24:29.59ID:xVz3ul4wp
>>134
最悪ケースは　p=2,q=10^18程度　だった
2023/01/08(日) 12:33:13.02ID:4xTAT7w0a
>>136
pが2なら最善だろ
真面目に素因数分解するんじゃなくpかqのどちらかになる素因数を一つみつけたら後はO(1)
2023/01/08(日) 12:35:54.01ID:xVz3ul4wp
>>137
もし素数判定をするならこのqがめちゃくちゃ大きい素数のケースが判定出来ない(けど実際は必要ないことを見抜けば良い)って話
2023/01/08(日) 12:40:40.46ID:4xTAT7w0a
>>138
わからん
p=2なら4で割ればqが出るじゃん
最初に一つ素因数を見つけたらその二乗で割り切れるかどうかでそれがpかqか判別できるからそこからO(1)になると最初から書いてるんだが
2023/01/08(日) 12:46:00.22ID:xVz3ul4wp
>>139
素数の判定云々の話をしてそれに対してそれだとアウトってレスがついてたから、アウトな方の方針を書いただけで小さい方が高々Nの立法根になることを見抜けてるなら問題ないってこと
2023/01/08(日) 12:48:17.86ID:4xTAT7w0a
見抜けてるのは最初のレスを見てもらえばわかると思うが俺が見抜けてようが見抜けてなかろうがそれでアウトになるはずなくね？
2023/01/08(日) 12:54:12.01ID:BtN5SsI/r
うんち！ｗ
2023/01/08(日) 12:56:12.81ID:xVz3ul4wp
昇順に素因数を確認する方針を取れば自然と10^6程度までで解が求まるけど、実際にはその方針に辿り着けないような人もいて、正解の方針を取らないで何も考えずにp、qの素数判定をしたりすると間に合わなくなるからそこで篩い落としてるっていう話
別に間違いを指摘してるわけではない
2023/01/08(日) 12:56:42.45ID:lAEXMGQ20
なんか草
2023/01/08(日) 12:57:52.94ID:PLtXzXPr0
>>126,128には計算量の話が全くなかったから突っ込まれてただけだよ
計算量がNの立方根らへんになることがわかってれば良い
2023/01/08(日) 13:09:39.78ID:4xTAT7w0a
なんでわかってないやつが偉そうなんだw
2023/01/08(日) 13:10:29.67ID:4xTAT7w0a
>>131
このアルゴリズムでだめな理由を書いてからいえやw
2023/01/08(日) 13:14:58.62ID:HsiWAu8/a
はいはいすごいすごい
2023/01/08(日) 13:23:07.45ID:4xTAT7w0a
めんどくせえ
2023/01/08(日) 19:02:56.17ID:FA2WmfgIM
レートは寒色なのにIDは真っ赤、と……
2023/01/08(日) 19:35:57.28ID:7H0KKt1L0
レスバするのも煽るのもやめろ
2023/01/08(日) 19:48:45.82ID:PbV2sMf50
初歩的なプログラミングに慣れてきたから、ABCの過去問を解いてるんだけど、解説を読んでも意味不明な場合はどうすればいいんだ？ABC284のC問題が何度読んでもよく分からない 深さ優先探索とか幅優先探索なんてAPG4bになかった気がする頭がどうしようもなく悪いみたいだから競プロやめようかな
2023/01/08(日) 19:52:33.27ID:PbV2sMf50
こんな簡単な問題で詰まってるってどうしようも無いレベルの脳障害よな…、
2023/01/08(日) 19:53:37.12ID:nECg26E4a
p=2の時に最悪になるなんてとぼけたこと言うやつが煽るスレ
こんなアホが複数いるとは思えんから自演だろーなー
悔しかったんだなー
2023/01/08(日) 19:56:51.09ID:nECg26E4a
>>152
これはdisjoint-setを知ってるかどうかだけの問題だから解けなくても何も気にしなくて大丈夫
2023/01/08(日) 20:04:48.91ID:1vMHtyHnp
レスバするつもりはないけどせめてワッチョイ確認しろよ
自演してるのはどっちやねん
2023/01/08(日) 20:06:10.50ID:nECg26E4a
お前だろw
知能でわかるのになぜバレないと思うんだw
2023/01/08(日) 20:07:28.74ID:1vMHtyHnp
129は俺だけど131は別人だぞ
2023/01/08(日) 20:08:26.38ID:nECg26E4a
はいはい
あと全部俺ね
2023/01/08(日) 20:08:41.85ID:nECg26E4a
病気か？w
2023/01/08(日) 20:11:16.79ID:gWSxWaz50
幅優先探索も深さ優先探索もUnionFindも知識的な話で、知らなきゃ理解に詰まるのはしょうがない
解説は基本かなりダイジェスト気味だから、一回もう少し詳しいサイトなり本で勉強すればいいと思うよ
2023/01/08(日) 20:12:44.36ID:4UuUf9f70
桁数が多い平方数の平方根ってどう計算するのが正しいのかな。単に sqrt 取って int にキャストするのだと計算誤差の関係で sqrt の小数点以下が .9999989 みたいになっていたら困るし、だからと言って sqrt に任意の小さい数（0.001 とか）を足してから int にキャストするのも格好悪いし。あるいは元の数が long long で収まる大きさだったら sqrt はピッタリ求まるのかな。
2023/01/08(日) 20:18:18.77ID:4A4PT21lp
>>162
roundすればよくない？
2023/01/08(日) 20:34:40.46ID:4UuUf9f70
>>163
確かに。でも round が安心して使えるなら、昨日の問題とは別に一般の素因数求めるコードで for (int i = 2; i * i <= n; i++) ってよく見かけるけど、for (int i = 2; i <= round(sqrt(n)); i++) と書いたほうが掛け算の回数が減っていいんじゃないかと思ったわ（計算時間の差は微々たるものだろうけど）。鉄則本での配列の宣言にもあった A[100007] とかと同じで競プロ業界のお作法なのかしら。
2023/01/08(日) 20:36:13.61ID:rVivGDpza
>>162
↓の記事にめっちゃ詳しく書いてあるけど、long longに収まる整数でもfloatやdoubleで表せるとは限らない
コンピュータの小数は難しい

https://qiita.com/y-yoshinari/items/76260f6359d5b4418b33
2023/01/08(日) 20:36:51.62ID:MjmTh3T5r
なんでround(sqrt(n))の方が速いと思えるんですか？
2023/01/08(日) 20:40:17.96ID:8iA8H0pf0
浮動小数点数は値がデカいとスッカスカになって、例えば一定以上の大きさの奇数を表せなかったりするのが怖いんだよな
sqrtぐらいならなんだかんだうまくいくのかもしれないけど俺は浮動小数点数と仲良くないからsqrtは二分探索書いてる
2023/01/08(日) 20:54:43.75ID:4UuUf9f70
>>166
そっか、n の値を別の変数 m とかにコピーして、ループ内では m の方を素因数で割っていくイメージだったのですが（その場合 n は不変なのでコンパイラがちゃんと仕事をしていれば sqrt の計算は1回のみ）、i * i <= n で上限チェックをしているコードはループ内で n を変えていく想定なわけですか。
2023/01/09(月) 06:27:27.63ID:NBV9jC+W0
１問ずつ解説動画上げてくのか
2023/01/12(木) 18:08:12.84ID:hau3jnvxM
ARC対策に去年初めのARCの問題を考えてみたら、当時解けたのに今解けなくて笑えない
2023/01/14(土) 20:20:04.00ID:o0xk1/qD0
正月ボケで開催日を間違えて今年最初のABCを見逃してしまいました
昨年末から精進するのを休憩してプログラミングから全く離れていたので
ぶっつけでABC284やってみたらあっさりCまで解けて安心しました

そろそろ参加10回くらいになりますがDの壁が高過ぎると感じているので
灰色のまましばらく解けるものを確実にこなせたらと思います
ずっと毎日精進するのはストレスに感じ始めていたので
コンテスト前などの気の向いた時だけ勉強するようにしてみます

と書いてて今からやる気満々だったABC285は明日じゃん...
ARCは問題見ただけで自分の無能さを思い知るので見ないでおきます
172デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/14(土) 23:01:05.01ID:lOE4TlVsa
C、判定も分割方法もわかったけどそこから回答例出す方法思いつかなかった...
今から説明読んで精進します
173デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/14(土) 23:06:25.55ID:lOE4TlVsa
Bは無理だと思って捨てたけど
1,2の位置だけでわかるのかよ...
なんかそんなに行列が壊れないようなトリックになってそうとは思ったけど、
まさかここまでとは...全然気づかなかった。
174デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/14(土) 23:09:19.49ID:lOE4TlVsa
むしろ、奇数偶数さえ押さえてれば1の場所だけで良いのか。
2023/01/14(土) 23:09:32.98ID:Sr0okIFG0
C後ちょっとだったけど500人近くも解いててびっくり
2023/01/14(土) 23:35:20.12ID:PSuT81xP0
C問題はslopetrick系かな？と思ったけど式書いてみたら本当に単純な一次関数でびっくり
2023/01/14(土) 23:35:51.38ID:PSuT81xP0
>>172
地味に復元めんどくさいよね
2023/01/15(日) 19:37:41.30ID:x61tbRba0
ABC283のキャンペーンで500円当たった
2023/01/15(日) 22:40:11.85ID:d5cspaf50
俺がその場で考え出した超スパゲッティなunion-findでD問題何とか通してやったぜ
ひどいコードだから是非見てほしい、次のレスで
2023/01/15(日) 22:40:40.75ID:hjFyqJMa0
やっぱ日頃から精進してないとABCまででも苦戦しますね
問題文が何を問うているのか理解するのに時間が掛かりすぎるのと
解法のイメージは出来ているのにちょっとした関数を用意してないだけで
わざわざ場当たり的に実装して手間取ったり

C問題解けたのが終わる直前でDは無理だと思ったので順位表見てたら
snukeさんがC解いたのが7分台と知って
自分の無能さを痛感しました
2023/01/15(日) 22:40:49.45ID:d5cspaf50
dic = {}
flag = True


def find(tt, update=None):
if update:
if dic[tt] == tt:
dic[tt] = update
return
cc = dic[tt]
dic[tt] = update
find(cc, update)
return
if dic[tt] == tt:
return tt
p = find(dic[tt])
dic[tt] = p
return p
2023/01/15(日) 22:41:06.05ID:d5cspaf50
for i in range(int(input())):
a, b = input().split(" ")
if a in dic and b in dic:
for temp in (a, b):
find(temp)
if dic[a] == dic[b]:
flag = False
break
new_ = dic[b]
find(a, new_)
elif a in dic:
dic[b] = dic[a]
elif b in dic:
dic[a] = dic[b]
else:
dic[a] = a
dic[b] = a
print("Yes") if flag else print("No")
183デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/15(日) 22:41:25.41ID:C77/nrWVa
D...
サイクルになるとNGとなるようにプログラムが作りきれなかった。
Cの問題を応用すれば良いのはわかるのに、単純に時間内に改良出来ん。
もったいなかったなぁ、、、
2023/01/15(日) 22:44:59.43ID:d5cspaf50
そういえば今度応用情報受験するんだけど、競プロ勢（といっても俺はガチ初心者レベルだが）
にとって午後のアルゴリズム問題って得意だったりするんだろうか
2023/01/15(日) 22:46:26.67ID:d5cspaf50
見づらいからこっちでシェアするわ
https://atcoder.jp/contests/abc285/submissions/38073975

こんなに汚いunion-findでよく通したなって自分をほめたい
186デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/15(日) 22:47:08.29ID:C77/nrWVa
>>179
酷かろうが作ったもの勝ちだよw
dfsにこだわったのは悪くない筈なんだけど、
全探索にして、上書き発生したらNGにするだけなのに、色々脱線して組めなかったわw
最後の最後で初期値1にしてた事に気付いたしw
2023/01/15(日) 22:48:38.06ID:4pwrT8s/0
E解けなくてショック
2023/01/15(日) 22:49:53.12ID:d5cspaf50
union-find自分で実装するのめんどくさかったから最初どこかからコピペしようとしてたわ

けど、通常のユニファイと違って文字列のアクセスだからどうやって応用したらいいかがわからなかった

>初期値１
これはなんのこと？
189デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/15(日) 22:50:56.98ID:C77/nrWVa
>>187
1週間が5000日とか気が遠くなるなw
2023/01/15(日) 22:51:31.11ID:A0weaKjwa
名前ごとに番号つければいいだけ
2023/01/15(日) 22:52:12.97ID:hjFyqJMa0
TOPページの左側に表示されているランキング上位10位に日本の国旗が無いのに気づいてしまった
2023/01/15(日) 22:52:13.73ID:x61tbRba0
終わったあと冷静にやったらE解けた
2023/01/15(日) 22:52:56.31ID:d5cspaf50
>>190
そう思ったけど、改名前と改名後どっちがどうだとかいろいろ考えてたらわけわからなくなって結局自力実装してしまった。
2023/01/15(日) 22:53:56.36ID:d5cspaf50
>>191
ほんまやん
やっぱ日本てITレベル低いんだろうか
195デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/15(日) 22:54:41.45ID:C77/nrWVa
>>188
Cの問題をそのまま利用(大文字小文字だけは違うけど)して英字列を数値に変換したんだよ

最近のdfs絡みって全部初期値が0か1の問題だけだったので、そのまま組んでしまってて、、、
でも例題がそれで通ってたせいで迷走してしまった。
2023/01/15(日) 22:57:50.51ID:d5cspaf50
>>195
なんと。。。。職人技だな、その発想はなかった。
数字に変換したいのなら普通にハッシュ関数とかの方が計算量的に早かったりするんだろうか
197デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-wtyD)
垢版 |
2023/01/15(日) 23:04:31.35ID:C77/nrWVa
>>196
よくよく考えたらグラフに置き換えるのに数値に変換する必要もないですね・・・
グラフ問題出たら最低でもノータイムで解けるようにしとかないといかんですね。
勿体ない時間が多すぎた。
2023/01/15(日) 23:05:19.32ID:ybL1uer8M
Gのドミノ置けるか判定なんてどうせフローでしょ感
2023/01/15(日) 23:07:20.31ID:d5cspaf50
>>197
連続した整数にするできるならまだしも、離散的な数字を生成するのならメリットはあまりないですな

グラフ問題ノータイムか。。。まだまだ練習が必要そう
2023/01/15(日) 23:08:13.12ID:d5cspaf50
そうだ、あとA問題
これの解き方まじでわからんかった

https://atcoder.jp/contests/abc285/submissions/38045467

こんな感じで書いたんだけどもっと効率的な書き方あるんだろうか
201デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-wtyD)
垢版 |
2023/01/15(日) 23:09:14.98ID:C77/nrWVa
>>200
大きい方を小さい方で割った答えが２ならYes
2023/01/15(日) 23:10:20.42ID:d5cspaf50
そうか。。よく見たら下のノードは倍だった。。。。。



いやひどい。。なぜ気づかなかったのか
203デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-wtyD)
垢版 |
2023/01/15(日) 23:12:18.99ID:C77/nrWVa
>>199
＞離散的な数字を生成するのならメリットはあまりない
その通り・・・C問題の後で、これは数値に置き換えると効率よくなるはずだ！
って声に従って変換してました・・・が意味なかったですね。

なんというか、学校等の模試って１問前の問題を応用することが多くて、
それが完全に染みついてるんですよね。
2023/01/15(日) 23:12:58.55ID:ybL1uer8M
Aは完全二分木の頂点を配列上で管理する話で、発展的な知識で思考をショートカットできる系の問題と言ってもいいかもしれんな（これぐらいなら再発明するやついっぱいいるだろうが）
ARC/AGCの低難度で出る一見アドホックな問題もこういう感じだったりするんだろうか
205デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-wtyD)
垢版 |
2023/01/15(日) 23:13:17.67ID:C77/nrWVa
>>202
自分は法則探しに時間使ったので、ある意味力業の方が早かったかもしれません。
2023/01/16(月) 11:42:48.72ID:hJPb0sEP0
>>194
AtCoderは日本で現役最強格の人や、世界的にも最強に近かった日本人選手が運営で作問作業のコアな部分に携わってるから出られなくて、ランキングにいない
それを差し引いても、中国や東欧の方がやや強いけど
2023/01/16(月) 11:45:15.43ID:ufjTVwgaa
中国や東欧の人に問題作らせよう(名案)
2023/01/16(月) 16:21:39.59ID:KeLZ+3YK0
>>204
過去のABの比じゃなく難解だったので飛ばして
C→B→Aの順で解きましたが
全条件を組み込みするのは絶対に嫌だったので
何か法則があるんだろうなと捏ねくり回してたら2倍か2倍+1に気づいたので
if文1行で解けましたが解説見ると知ってる人や上位の方が1-2分で解けるのも納得です

考えて解く問題より知ってるかどうかって問題が多い気がしますが
どちらにしてもD問題の壁が高過ぎるのは変わらないので
DNAとかIQなど持って生まれたもので精進レベルではどうにもならない感が半端無いなと思います
2023/01/16(月) 16:36:42.01ID:8YM4/SqSa
二分木の配列実装を知らないレベルでIQやDNAを云々するのは結論を急ぎすぎ
知識増やしても壁を乗り越えられなくなってから言おう
2023/01/16(月) 17:19:37.05ID:U+wXPFak0
AtCoder青色くらいまでは本一冊程度の知識を身に付けていますか？で終わりなんだよな
典型90問とEDPCを全部解いてて水色以下の人を見たことないし
2023/01/16(月) 17:56:32.76ID:b6PEgRZ5M
努力でどこまでできるかについては諸説あるが、知識がないうちは自分が知識あれば解けるかどうかすらも分からんもんで、最初のレートの伸びが悪くても一旦勉強してみてから考えてもいいんじゃないか
ABCのD突破するのに要る知識だったら普通のエンジニアリングで遭遇するものも多いから、そこまで損はない
2023/01/16(月) 18:00:22.74ID:b6PEgRZ5M
最初天才にしか見えなかった解き方が、有名でありきたりな定石の変種に過ぎなかったなんてよくあることよ
まあもちろん発見者は天才なんだろうが
2023/01/16(月) 18:02:24.18ID:74DJbkLX0
少なくともD問題くらいまでに関しては毎回かなり典型的な知識しか要求されないし問題も素直なものが多いからそのレベルだとセンスとか関係なく訓練すれば迷わず書けるようになると思う
2023/01/16(月) 18:10:09.09ID:b6PEgRZ5M
それとレートの伸びが早くて天才に見える人も、中学受験とか数学オリンピックで競プロの役に立つ思考パターンを予めたくさんインプットされてるのがデカいんじゃないかって話もあるからな
215デフォルトの名無しさん (ﾜｯﾁｮｲ 4a55-sAzJ)
垢版 |
2023/01/16(月) 18:14:52.41ID:YizsHMWj0
AtCoderの社長の人の本を少し読みましたが、アカデミックな香りが全くしません。
そういう人が非常に強いというのが不思議です。
逆にアルゴリズムが専門の大学教授は強いのだろうかと疑問に思ってしまいます。
2023/01/16(月) 18:19:44.82ID:b6PEgRZ5M
弱い相関はあるだろうが、基本別の能力だぞ
極論チェスプレイヤーが数学者として成功できるかみたいな話
逆にアルゴリズムの世界的な研究者がCodeForcesでそんなに強くなかったりな
高齢だからしょうがない部分もあるが
2023/01/16(月) 18:45:28.99ID:6Zqlh15Z0
アルゴリズムや関連理論を知っていることと時間内にアルゴリズムを問題に適用できるかは別だしな
だから研究者でも寒色は全然よくある
まぁ若い頃に精進すればもっと上に行ってただろうけど、それをする必要があるかはさておいて
2023/01/16(月) 19:26:15.35ID:RX3YYcWAa
>>214
作問者はそういう経歴を辿ってるひとだらけだから傾向は偏っている
アカデミックな研究者が作問してたらもっと別な傾向になるだろう。新しく発表されたアルゴリズムを元ネタにした作問とかしそう
2023/01/16(月) 19:41:30.89ID:6Zqlh15Z0
そうなった場合"精進＝アルゴリズム系の論文を読み漁る"になった可能性もあるのか...
そうだったらハマってなかったわ
2023/01/16(月) 21:05:40.99ID:DOxpd2W+M
まあレート競争するのが楽しいって体質なら、そうなったらそうなったで普通に論文も楽しく読めちゃう可能性あるけどな
Kaggleで論文読むの割と楽しいぞ
2023/01/16(月) 21:58:45.57ID:U+wXPFak0
暖色コーダーは割と気軽に論文読んでるしな
競プロ強い人は研究者適正もあるとは思うわ
2023/01/16(月) 22:05:55.89ID:Qlcs6NPMr
983 デフォルトの名無しさん (ﾜｯﾁｮｲ 6f71-0qRf) 2022/10/03(月) 20:26:59.27 ID:lndyBnH50
https://twitter.com/intent/favorite?tweet_id=1516784253656506369
@rui314
さん
あれはSAPIXとか鉄緑会と同じカルチャーだと思う。
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)
2023/01/16(月) 22:14:02.31ID:DOxpd2W+M
リンク先でいいねに誘導するトラップな
2023/01/17(火) 01:36:16.99ID:PP1OxyD+r
>>222
せめてURLくらい直してからコピペしろ
2023/01/18(水) 23:04:40.18ID:+Nvb3/Yi0
https://twitter.com/31415926five/status/1614620071787401217
先週のC問題、この人と同じ状況になってWAが出ます
これ何が原因だと思いますか？
https://twitter.com/5chan_nel (5ch newer account)
2023/01/18(水) 23:06:58.61ID:+Nvb3/Yi0
自己解決しましたdoubleの精度の問題でした
227デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/19(木) 07:34:58.63ID:pYXSCk3La
>>226
解説読んで無いからよくわからんけど26進法じゃないの？
書いてある方法の解き方がよくわからんw
2023/01/19(木) 09:50:28.45ID:yp2D21uT0
全探索とかdoubleとかどう使うんだ
2023/01/19(木) 09:57:14.64ID:yp2D21uT0
26進法ぽいっちゃぽいけど0が無いんだよな
Aが1で26が桁上がり無しのZ
27で桁が上がってAA
単純に前から順にAからZを1から26に変換して26倍して次を足せばいい
2023/01/19(木) 11:58:12.74ID:VmKzUfPXa
c++ならこんだけやで

https://atcoder.jp/contests/abc285/submissions/38146370

触ったことないから詳しくはわかんないけどrubyとかならもっと短くできそう
2023/01/19(木) 12:27:13.37ID:GNmF+z4la
C#は多分こんな感じ
Console.WriteLine(Console.ReadLine().Aggregate(0L,(p,c)=>p*26+c-'A'+1));
2023/01/19(木) 12:47:40.51ID:z/YrvD0n0
>>227
pow関数使って26の累乗を求めるアプローチだと
整数型にキャストしないとWAが出るのです
2023/01/19(木) 12:50:59.12ID:H7hm+dDpa
小数部使わないのに誤差出るか？
2023/01/19(木) 12:51:55.35ID:H7hm+dDpa
Eなら提出前に気づきそうなもんだが
2023/01/19(木) 12:54:15.21ID:z/YrvD0n0
>>233
10の16乗の桁数くらいだと1ずれるんですよね

>>234
3つだけWAになって何これ？ってなりました
2023/01/19(木) 12:57:28.46ID:H7hm+dDpa
>>235
なるほど、いい問題だったんだなぁ
2023/01/19(木) 17:30:26.00ID:4HEHet1z0
その問題特有の性質じゃなくてc++だとpow関数がdouble型を返す仕組みになってることが原因だから問題の本質とは関係ない
pow関数は誤差が怖いから他の方法を使って累乗を求めた方がいい
238デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/19(木) 21:38:50.39ID:+9XmtH7na
225,226の言ってる事が理解できて勉強になった
楽したいが為に使おうとしちゃうけど、関数の使い所って難しいね
2023/01/20(金) 02:33:59.68ID:diHqYdLq0
C++のpowあるあるひっかけ問題だなと察して
場当たり的に自作powぽいものを実装してACしましたが
以前他人様の提出見た時に自作powをテンプレ化してる人が複数人いて
なんでだろうと疑問に思っていましたがこういう時に役に立つのだと思いました

ちょっとしたことですがこういう典型的な自作関数などのテンプレを用意しておくだけで
数秒から数分の節約になるんだなと思いました

教プロやってる人にとっては知ってて当然のことなのかもしれませんし
これを知識と言うのか典型と言うのか分かりませんがテンプレなどの事前の準備が大事なんですね
2023/01/20(金) 08:50:50.07ID:mtsSyn0E0
>>237
いいや、doubleが溢れる桁数を問う問題を兼ねてるからいい問題と言ったんだよ
doubleだけじゃなくlong longでも同じことが起こり得るから本質に気づいてないお前は気をつけとけよ
2023/01/20(金) 11:42:24.05ID:tXcgurvTa
え？
2023/01/20(金) 11:53:34.18ID:2M3lLN52a
>>241
わかんない？
困ったな
doubleは整数部と小数部で計算が違うから整数部のみ使う場合において誤差は発生しないんだよ
ただし整数部が大きくなりすぎると指数を使って下の桁を小数部に回すから誤差が発生するようになる
doubleで扱えなくてlong longで扱える整数の範囲ということを問題から読み取る必要があるってことね

long longも大きくなりすぎると負の数になって計算が狂うから知らなかったなら気をつけなよ
2023/01/20(金) 12:12:55.31ID:Kk0KHPJpp
え？？
2023/01/20(金) 12:13:09.15ID:hTaThntwH
よくわからないんだけど、pow(a, b)は普通exp(b*log(a))で実装されてるから整数の自然数乗だろうが非整数を扱うことになるんだけど、そういう話ではない？
2023/01/20(金) 12:25:06.54ID:2M3lLN52a
>>244
そういう話ではないな
俺はpowじゃなくdoubleの話をしてる
処理系の実装で整数のpowでもわざわざ小数を使ってるせいで誤差が出るとするとそもそも戻り値がdoubleだろうがlong longだろうがpowを使うなという話になるな
つまりdoubleじゃなくpowの実装がザコいせい
2023/01/20(金) 12:43:22.43ID:tXcgurvTa
ここまで堂々と頭の悪いこと言われると反応に困っちゃう
2023/01/20(金) 12:44:49.90ID:mtsSyn0E0
文字は聞き返さなくてもちょっと目を上げれば読み直せるからまあ頑張れ
話について来れなきゃレスしない方がいいぞ
2023/01/20(金) 12:59:28.86ID:EBHG8O+MH
前回のARCのCとDを焼きなましでやってるのを見てAHC初心者から見るとすごいなーと思うばかりなんだけど、こういうのって近傍設計が肝なんだろうか
2023/01/20(金) 17:02:00.07ID:NIAP7Re/0
間違ってることをドヤ顔で言う人ってなんだろう？
2023/01/20(金) 17:24:08.90ID:hUpC7cMkp
間違ってる知識を堂々と書いてるようじゃそりゃC、Dくらいまでしか解けないよ
2023/01/20(金) 17:43:56.53ID:RAkU5h8xM
多分前回のARCのCとDだったら焼くより普通に解く方が簡単だな
2023/01/20(金) 18:45:03.00ID:mtsSyn0E0
字が読めないからどういう話で自分が何を間違ってるかに気づいてないんだろ
2023/01/20(金) 22:31:37.16ID:oRj8j4al0
IEEE754を覚えていないのは百歩譲って許せるとして、誤り指摘された時に調べずに嘘を強弁できるのは精神力すごいわ
競プロには向いてないけど
2023/01/20(金) 22:35:23.59ID:A1AN6ddup
競プロなんかより浮動小数点数の仕組みの理解の方が大事
2023/01/20(金) 23:14:11.93ID:mtsSyn0E0
日本語からまなべばいんじゃね
ひらがなおおめにしてみた
2023/01/20(金) 23:18:09.22ID:hk65WKuDp
前回のD問題でも自分の誤りを認めずに暴言吐いてた奴と同一人物だから無視でいいよもう
2023/01/21(土) 08:14:27.49ID:wMRSxtV+a
そういやそんなやついたな
寒色は人じゃないんだから身の程わきまえろよ
2023/01/21(土) 10:49:09.24ID:uINiby7f0
170cm以下と寒色は人権ないってマジですか？
2023/01/21(土) 12:24:47.69ID:GLf6VXiq0
身長は関係ないだろ！
2023/01/21(土) 20:05:05.68ID:hxfhds9Dd
競技プログラミングの鉄則で勉強してるけど本当に才能ゲーすぎるな
俺みたいな脳障害だと☆3レベルの問題でも初見で解けない
261デフォルトの名無しさん (ﾜｯﾁｮｲ 735f-/r4y)
垢版 |
2023/01/21(土) 20:10:22.78ID:kq0XiZba0
「社員着服のつけ」下請けに 楽天モバイルが契約解除で経営危機
https://news.yahoo.co.jp/articles/d60a8867bdb5c6da90bbed1d8a910d4bff63b23a

さすが楽天グループはトップから末端までクソしかいねえなw
2023/01/21(土) 20:23:40.08ID:jt1r7llwM
みんなが初見で解ける問題なんて本に載せても意味ないやん
2023/01/21(土) 21:37:13.32ID:9dRSa5Al0
無理
2023/01/21(土) 21:40:34.12ID:9dRSa5Al0
なんか毎週こんなことやってる自分が急に虚しくなってきた
生まれつき頭の良い人達だけが楽しめるものなんでしょうね
勉強してどうにかなるようなものじゃないって薄々気がついてたけど
毎回自分の無能さを思い知るだけの罰ゲームは終わりにします
2023/01/21(土) 21:48:06.59ID:9dRSa5Al0
初見で解法が思いつかない
解説を少しづつ見てヒントを小出しにしつつなるべく自力で解く
それでもどうにもならないから写経する

知ってるか知らないか
覚えてるか覚えてないか
テンプレ作ってるか作ってないか
初見で解けるか解けないか

そりゃ流行るわけ無いですよ
極一部の出来る人しか楽しめない
上位も全体も外人だらけ

フェードアウトした人多そう
2023/01/21(土) 21:51:49.04ID:qt3XT5WsM
別にこれ以上流行って欲しいとは思ってないんで……
267デフォルトの名無しさん (ｱｳｱｳｳｰ Saa7-szjb)
垢版 |
2023/01/21(土) 22:43:38.68ID:o/n0Og29a
BとCでつまづいたせいでD解けなかった
Cはもうちょいシンプルに解けるやつにしてくれよw
2023/01/21(土) 22:44:43.48ID:W0WhddGb0
Fまで解けた割にパフォ渋いんだけど参加者数の問題？
順位も青色から見てそんなに悪くないのに
269デフォルトの名無しさん (ｱｳｱｳｳｰ Saa7-szjb)
垢版 |
2023/01/21(土) 22:45:39.87ID:o/n0Og29a
Bはnnのケース忘れてた
Cは最小0円を忘れてた
限られた時間だと短縮しすぎてこういうの漏れちゃうね
2023/01/21(土) 22:46:04.60ID:bO6wwiXS0
Fわかんね
絶妙に110縛りが邪魔くさい
271デフォルトの名無しさん (ｱｳｱｳｳｰ Saa7-szjb)
垢版 |
2023/01/21(土) 22:46:13.44ID:o/n0Og29a
>>268
もうパフォ出てる？
2023/01/21(土) 22:49:17.47ID:hrtV3vjP0
>>268
なんかpredictor変かもしれんね
2023/01/21(土) 22:50:03.50ID:W0WhddGb0
>>272
前回も表示バグってた気がするしそうだと信じたい
274デフォルトの名無しさん (ｱｳｱｳｳｰ Saa7-szjb)
垢版 |
2023/01/21(土) 22:51:36.48ID:o/n0Og29a
>>268
全抜多いからでは？
2023/01/21(土) 22:53:37.02ID:W0WhddGb0
検索したらやっぱり皆も同じ感想っぽいな
2023/01/21(土) 23:01:36.37ID:rZUyyxKK0
まだパフォ出てないぞ
Gができなくて残念
2023/01/21(土) 23:09:02.32ID:hrtV3vjP0
>>260,265
マジレスしておくと、ある程度のレベルまでは間違いなくガチ暗記ゲーだからね
異常な天才は競プロ対策してなくても解けまくれるかもしれんけど、普通のひとにとっては暗記ゲー

そしていろんなことを暗記しまくると(理解度が深まってくると)、応用もどんどん効いて難しい問題も解けるようになる

まあ大学受験とかでも同じだろ
基礎を暗記してからようやく応用ができるようになる
2023/01/21(土) 23:11:45.67ID:3ta99Pbc0
多分200ぐらい低く出てる
2023/01/21(土) 23:20:33.40ID:OgrmMJxO0
なんかパフォ低くない？😐
2023/01/22(日) 02:02:34.60ID:iZYn+tsO0
やっとF自力ACできた
素数である必要がなかった…
2023/01/22(日) 02:25:58.37ID:byEukdaY0
>>277
CD程度の問題を見て解法が思いつかず何やっても無理だと悟って
あまりの自分の無能さに嫌気がして
悪態をついた愚痴にマジレスしてくれる優しさに救われます

暗記ゲーにしては範囲が広すぎるし
勉強することを精進だと自分に言い聞かせてましたが
毎回理解出来ないものを永遠と写経するだけになっていて
初見で解法が思いつかないことが苦痛とストレスになって
病みそうなレベルなので
精神衛生的にも少し教プロから距離をおくつもりです
2023/01/22(日) 03:04:01.89ID:mUOTz0yy0
>>281
まあ、プログラミングというより数学の競技だと思っておけば安心するだろうね

大学受験数学は当然として、中学受験数学で学ぶようなテクニックが活用できたりするし、
そういう受験数学のエリートがさらにアルゴリズムをめっちゃ勉強して競い合うのが競技プログラミングだ

もし中学受験とかやってないのに、そういう連中に追いつき越えたいなら、そういうエリートがやってるよりもはるかな修練が必要だよ
まあそういうエリートは数学的な問題を解くのが大好きだから現時点の瞬間的な修練量でさえなかなか超えられないだろう
アルゴリズムやデータ構造というより数学そのものの勉強も必要になってくるしね
2023/01/22(日) 04:18:00.16ID:PuyRUUPn0
明日のARC早解き大事そうで不安
2023/01/22(日) 09:04:17.31ID:aVfD/yvN0
「競技」プログラミングが十分な勉強と対策をしなくてもできるなら、もうそれは競技じゃないんよ
競技なんだから、勝ちたきゃ多くの対戦相手を蹴落とすだけの努力をしなきゃいけない
2023/01/22(日) 14:02:44.50ID:rNCNoAArM
今日のARCで大事なのは700点の難度だよなあ
maroon回ほど極端に難しくなることはないと予想
2023/01/22(日) 14:12:07.62ID:rNCNoAArM
ABCだったら初見力なんてそんなに大事じゃなくて、ちょっと変形された問題が解けることが重要だと思うんだよな
ちょっとの変形に対応できるかどうかの練習をするのにも、土台としてまず知識が要るので、知識ないうちは才能の有無すらわからんよ
むしろ初見力があっても知識不足だと解けないのがABC
AGCは逆に知識無くても初見で解けるやつもいるから、最初はABCよりAGCの方がパフォーマンス出やすいやつもいる
2023/01/22(日) 14:14:50.28ID:aW5/C6mta
初心者にマウントとるスレは今日も平常運転
2023/01/22(日) 14:17:25.11ID:rNCNoAArM
ただ、瞬発的に解法を発想できないのは仕方ないにしても（知識不足だと発想の引き出しがないからそりゃ無理）、解説を読む段階になったら時間を掛けてでも書いてあることを理解するように心掛けないと類題を解けるようにならないと思うぞ
2023/01/22(日) 15:03:59.25ID:AkwiJ1wn0
800点はブレで結構解きやすいこともあるけど900点はきっちり難しい印象がある
ただ昔の問題だと1000点超えでもそんなでもない問題も稀にあるから決めつけで解けないと思うのもよくないんだろう
2023/01/22(日) 15:33:49.45ID:PuyRUUPn0
昨日のG残り時間少なくて諦めてたけどEかFくらいに置かれてたら印象変わってそう
600点問題の基準が良くわからない
2023/01/22(日) 15:50:37.34ID:AkwiJ1wn0
ABCは自分の中では結構E<F=G<Exみたいな印象があるかなあ
真っ当にGの方が難しいときもあるけど
2023/01/22(日) 15:54:33.00ID:AkwiJ1wn0
それと6問ABC時代のF（600点）は今のGより難しかったような気がするね
2023/01/22(日) 16:49:33.03ID:5wvLt10o0
質問
long long ans＝1ll ＜＜60
このコードのllと＜＜60ってどういう意味なんですか？
apg4bにも載ってなくてわからん…
2023/01/22(日) 16:59:23.70ID:dCKmbyul0
> apg4bにも載ってなくてわからん…

https://atcoder.jp/contests/apg4b/tasks/APG4b_y
https://atcoder.jp/contests/apg4b/tasks/APG4b_ac
2023/01/22(日) 17:00:16.35ID:ZZ5J8M3ga
llは1をlong longとみなすってこと
<<はシフト演算子
2023/01/22(日) 17:01:07.41ID:rNCNoAArM
<<はシフト演算子と言って、数値の各bitをずらす働きがある
例えば5はbitで表すと101だが、5<<2は10100だ
bitを1つ左にずらすごとに数字は2倍になるから、これは1の2^60倍をansに代入してる

ただずらす数字がint型だと、通常32bitだから60もずらしたら溢れるという問題がある
そこで1LLと書くことでlong long型の1であるとコンパイラに教えてやり、オーバーフローが起きないようにしてる
2023/01/22(日) 23:09:41.75ID:iZYn+tsO0
Cまでは速攻で解けた
298デフォルトの名無しさん (ｱｳｱｳｳｰ Saa7-szjb)
垢版 |
2023/01/22(日) 23:09:56.89ID:6Df8qFExa
正解してたんだけど、
Aの問題の99...353で割るタイミングってどこが適当なんだろう？
よくわからなさすぎて10^i全部に99…353で割って、更にA＊B前にも99…353で割って、
最後の出力でも99…353で割ってしまった。
2023/01/22(日) 23:11:11.20ID:PuyRUUPn0
D1見つけてそれ使って比較出来るところまでは気付けたのにマージソートにまで辿り着けなくて勿体ない
300デフォルトの名無しさん (ｱｳｱｳｳｰ Saa7-szjb)
垢版 |
2023/01/22(日) 23:13:05.12ID:6Df8qFExa
お、ナメクジから初めてようやく茶色になれたw
こらからも頑張りますw
301デフォルトの名無しさん (ｱｳｱｳｳｰ Saa7-szjb)
垢版 |
2023/01/22(日) 23:15:38.53ID:6Df8qFExa
>>297
Cまでは解きたかった、、、
遊びがない場合とで分けたかったんだけど、遊びがなくても完全一致のケースもあるし...と考えてたら時間足りなかった
場合分け発生するのによく速攻で出来るね
2023/01/22(日) 23:18:31.18ID:4KBxssT/0
AとCの解説微妙に違う……？
303デフォルトの名無しさん (ｱｳｱｳｳｰ Saa7-szjb)
垢版 |
2023/01/22(日) 23:22:25.50ID:6Df8qFExa
>>302
積を99…353で割ってない事とか？
2023/01/22(日) 23:26:01.92ID:iZYn+tsO0
ソートもちゃんと勉強しておかないといけないなー
2023/01/22(日) 23:43:34.23ID:AkwiJ1wn0
比較的解きやすい回だったはずだけど、Dなんで思いつけなかったんだろう
反省
2023/01/23(月) 00:16:21.13ID:PrcIs1C50
>>299
これ
2023/01/23(月) 00:35:02.59ID:e2sqACGY0
>>303
A
自分が解説の意図を勘違いしてるかもしれないけど、ajとbjを交換することを考えるなら、
aibj+ajbiとaibi+ajbj
ではなく
aibj+ajbiとaiaj+bjbi
を比較するべきでは

Cはいま見返したら問題なかった
自分が初見時に誤読したのか訂正されたのか分からん（圧縮後のBの長さ、って最初から書いてあったっけ）
2023/01/23(月) 00:37:35.71ID:e2sqACGY0
Cは本人が訂正したとTwitterに書いてた
309デフォルトの名無しさん (ｱｳｱｳｳｰ Saa7-szjb)
垢版 |
2023/01/23(月) 08:36:16.47ID:WuUxtsL9a
>>307
自分の認識だけど
Aは解説。
307の言ってるのは解法。
Aの解説を達成するためには307で合ってるけど省略されてるという認識。
2023/01/23(月) 08:48:11.39ID:e2sqACGY0
>>309
ごめんよく分かってない
解説の

ここで、～前者となります。

と、

よって、～最小化できます

の部分がどう繋がってるのか分からない
311デフォルトの名無しさん (ｱｳｱｳｳｰ Saa7-szjb)
垢版 |
2023/01/23(月) 08:50:24.31ID:WuUxtsL9a
2＊4+3＊5と　2＊5+3＊4を比べる時
Aの解説は
2＊4+3＊5、3＊5+2＊4
どっちでも良いけどどっちかに大きい方を寄せると最小だよと言っている

307の計算が前提
312デフォルトの名無しさん (ｱｳｱｳｳｰ Saa7-szjb)
垢版 |
2023/01/23(月) 12:13:39.30ID:WuUxtsL9a
>>311

2＊4+3＊5と　2＊5+3＊4を比べる時
Aの解説は
2＊4+3＊5の2と4が3、5よりそれぞれ小さい(
大きい)なら前者、そうじゃないなら後者だよって話

>
> 307の計算が前提
2023/01/23(月) 13:01:50.68ID:o3gniU0ea
最近このスレって新参ばかりだな
寒色が程度の低い話をするばかりでちっとも面白くない
2023/01/23(月) 13:08:45.38ID:o8k4t/Wba
>>312
そこまでは分かってるけど、そこから次の行の「よって、」以下にどう繋がってるのかが分からない

aibi+ajbj
はどう桁を交換しても作れないから関係なくない？
2023/01/23(月) 15:36:06.70ID:5SV1YLwU0
暖色は分からなくても自力で考える力が高いからこんなところで質問しないんだよな
自分で高度な話題を振っかければ暖色も反応すると思うぞ
2023/01/23(月) 15:53:11.40ID:YKh4Yexo0
できるならやってみなよ
2023/01/23(月) 15:54:19.89ID:P4vFYAWeM
arc154_c って文字列テクニックとかでもっと速くなりますかね？
2023/01/23(月) 16:04:41.32ID:Ht7zbBk9M
本質は文字列 S, T が与えられて、S を rotate して T を（連続とは限らない）部分列として含むようにできるか、かな？
2023/01/23(月) 16:38:20.37ID:f59q5H/xH
何も考えてないけど文字列アルゴが効くのは連続部分列系じゃないの
2023/01/23(月) 17:10:24.74ID:5SV1YLwU0
区間部分列だと遷移ベクトルを考えるのがDISCO!とかにあったけど……今回は種類数が多いから辛いんだよな
種類が多いならAとBの先頭を出現数が最も少ない文字で固定すれば少しは速くなりそうだが、誤差程度だろうし
2023/01/23(月) 17:27:33.65ID:tGExjYo4p
ウェーブレット木/行列って競プロでどれくらい使える？
2023/01/23(月) 17:46:57.36ID:5SV1YLwU0
>>321 2-SATより上、セグ木より下くらいの頻度で使える
正直言ってACLに匹敵する実用性がある
2023/01/23(月) 19:05:17.82ID:w2Ehdp23M
遅延セグ木はもう誰でも知ってそうなデータ構造と化してるけど、WMは有用性の割にまだそんなに広まってないよな
324デフォルトの名無しさん (ﾜｯﾁｮｲ 6301-Jja6)
垢版 |
2023/01/23(月) 20:48:26.48ID:EpAhrFYS0
ABC97 B Exponentialについて教えていただけませんか？
Python3です。

from math import sqrt

x = int(input())
ans = 1

for i in range(1,x+1):
if sqrt(i) % 1 == 0:
ans = i

print(ans)

これを提出するとtest4,6,7だけWAになります。
テストケースは検索したけど見つからず...。
よろしくお願いしますm(._.)m
325デフォルトの名無しさん (ﾜｯﾁｮｲ 6301-Jja6)
垢版 |
2023/01/23(月) 20:50:24.16ID:EpAhrFYS0
for文のインデントがおかしくなってますね(汗)
無視して下さい
326デフォルトの名無しさん (ﾜｯﾁｮｲ 0301-Ed7v)
垢版 |
2023/01/23(月) 21:32:24.11ID:zJTAvzbD0
>>324
pが3以上の場合も考える必要があります
2023/01/23(月) 21:35:37.58ID:5SV1YLwU0
sqrt(i)%1に思うことはあるけど、その前にまず誤読してないか？
試しにsqrt(i)%1==0なるiを全部出力させてサンプル1と比較してみなよ
328デフォルトの名無しさん (ﾜｯﾁｮｲ 6301-Jja6)
垢版 |
2023/01/23(月) 23:43:27.87ID:EpAhrFYS0
>>326
>>327
完全に勘違いしてました(汗)
ありがとうございます。
329デフォルトの名無しさん (ﾜｯﾁｮｲ 6301-DmZS)
垢版 |
2023/01/25(水) 05:47:55.43ID:9HW6STW20
プログラムだかソフトウエアだか忘れたけど、ひろゆきみたいに上から目線で君臨しているやつまだいるの？
たかが一般人のくせになｗ
2023/01/25(水) 09:07:59.22ID:jShEQfK9a
自己紹介かな？
2023/01/25(水) 11:49:43.90ID:mhVwknLc0
>>294
>>295
ありがとうございます
2023/01/25(水) 11:49:51.41ID:mhVwknLc0
>>296
ありがとうございます
2023/01/25(水) 11:55:46.11ID:mhVwknLc0
しゃくとり法について質問
解答例の通りに実装すれば計算量がO(N)で済むと書いてるけど、解答例だとN-1回ループのfor文の中にwhile文が入ってるんだけど、これで本当に計算量がO(N)で済むの？
頭が悪すぎて解説読みこんでもわかんね
https://i.imgur.com/clPvzaA.jpg
https://i.imgur.com/7oJcUMF.jpg
2023/01/25(水) 12:12:47.43ID:n2t3GbXAr
それ読んでわからんなら一生わからんやろ
2023/01/25(水) 12:16:30.97ID:mhVwknLc0
自己解決 俺がただのガイジだった
2023/01/25(水) 12:20:19.29ID:mhVwknLc0
Ri＝nである場合、そもそも増やさないから全体の計算量はO(n)で済むんだね
頭が悪すぎてこの程度のことすら理解するのに時間がかかる
2023/01/25(水) 12:41:49.83ID:Ue7WvS0Xp
まあそんなもんでしょ
どうせ無限時間必要とするから、1つずつ典型を学んでいけばいい
レッドコーダーでも問題文誤読したせいで問題解けないこともある
2023/01/25(水) 12:43:36.96ID:QU6My8oIa
それはそうだが寒色の言うことじゃねえな
2023/01/26(木) 00:53:34.00ID:LOq94Mnx0
蟻本と螺旋本の電子版がセールで500円になってるの神すぎる
紙版しか持ってなかったから即ポチった
2023/01/26(木) 11:52:45.66ID:KRw/YtgyM
螺旋本\蟻本で有用な情報ってなんかある？
2023/01/26(木) 13:05:43.15ID:2N/SJ75Ca
記憶違いでなければ蟻本ってとうの昔に更新しなくなったPKUに則ってたと思うんだけど、新しい版では書き換えられてたりするの？
2023/01/27(金) 15:09:59.38ID:+2RNpRDo0
これ見ると東大生でも大半が緑色以下なんだよな
参加者のレベルがあまりに高すぎてエリートでも灰～緑程度のレベルで燻ってる
これから、AtCoderに参入する人はこの事実を知っておいた方がいいわ
https://i.imgur.com/zfVNSBr.jpg
2023/01/27(金) 15:11:53.02ID:+2RNpRDo0
青より上までいけるのは東大生でも極わずか
1部の数学エリートしか楽しめない娯楽それがAtCoder
俺は恐ろしい世界に入り込んでしまったんだな…
2023/01/27(金) 15:12:19.44ID:BLgn+yb/0
画質糞すぎません？
2023/01/27(金) 15:15:25.25ID:+2RNpRDo0
こっちはまだ少しましかな

https://i.imgur.com/jKZaXCC.jpg
2023/01/27(金) 15:26:17.89ID:+2RNpRDo0
これのほうがいいか
しかも、これは1年半以上前のデータだからな
今は当時よりも参加者のレベルが上がってるから、東大生であっても緑まで行くのは相当苦戦するかも
Fラン大学とかだと茶色も無理なんじゃないか
https://docs.google.com/spreadsheets/u/0/d/1_rtU2geWnkZyOBYXyvPtcyn9GRfucd7GGFQqoGM5fZE/htmlview
2023/01/27(金) 15:30:53.28ID:VQeG/t9u0
東大生が多いのは事実だけど全員が競プロに本気出してるわけではなくて適当にやってる人や合わなくて緑以下で辞めるような人もカウントされちゃってるから競プロに取り組んだ時間も結構重要よ
2023/01/27(金) 15:58:00.21ID:0/TLvchgr
そうだよ
真面目にやって緑とかセンス無いから諦めたほうがいいよ
2023/01/27(金) 17:29:25.91ID:JU+TJ79Xa
ていうか競プロなんて役に立たないんだから、時間を注ぎ込んでないほうが賢くて偉い
2023/01/27(金) 19:58:07.53ID:fqD0WMGRp
競プロと人生くらい両立しろ
351デフォルトの名無しさん (ｱｳｱｳｳｰ Sa47-muL6)
垢版 |
2023/01/28(土) 22:42:28.61ID:zcB4u36+a
前回茶色になれて、今回Dで解けた。
ようやくEの世界と対峙する事が出来そう。
2023/01/28(土) 22:42:57.04ID:GzvxAFRF0
だめだーdpどう使うのか思い付かん
70分お茶飲んでた
353デフォルトの名無しさん (ｱｳｱｳｳｰ Sa47-muL6)
垢版 |
2023/01/28(土) 22:44:30.61ID:zcB4u36+a
Cは楽な方法思いつかなかったから
鬼のように条件縛りしたけど、あれで良かったのかよw
2023/01/28(土) 22:45:29.10ID:96l2/V8G0
自分もFで1時間以上椅子を温めていた
ここ安定して解ければ黄色になれそうなんだけど二乗の木DPなんて知らなかったし経験が足りてない
2023/01/28(土) 22:47:05.23ID:qgxER/Mk0
またCで誤解法でACしちゃったかも？
解説見ると条件3つあるのに
if文2個でダメ元で提出したらACしちゃった

ACLのDSUで入力してmergeして

条件2つだけ

if (d.groups().size() != 1) return false;
if (N - 1 != M) return false;

上記抜けたらYes
return true;

これって正しいですか？
ACしたのに自身が無い
356デフォルトの名無しさん (ｱｳｱｳｳｰ Sa47-muL6)
垢版 |
2023/01/28(土) 22:48:00.90ID:zcB4u36+a
>>342
これ、出典どこです？
357デフォルトの名無しさん (ｶﾞｯｸｼ 06b6-aVnv)
垢版 |
2023/01/28(土) 22:50:49.59ID:ah21+Up06
>>355
4 3
1 2
1 3
1 4
とかはNoだけど、それだとYesになるかな
2023/01/28(土) 22:52:36.25ID:v1F80BgW0
>>355
次数が3以上の頂点を含む木だとダメだから嘘解法では
2023/01/28(土) 22:53:07.92ID:5uR0b9AVM
>>355
木だったらだめだな
というかこれ落とすテストケースないのか…
360デフォルトの名無しさん (ｱｳｱｳｳｰ Sa47-muL6)
垢版 |
2023/01/28(土) 22:53:14.42ID:zcB4u36+a
>>355
解説の1つ目の例で間違いなのになんで通るのかw
2023/01/28(土) 22:53:41.85ID:5uR0b9AVM
>>359
×木だったら
○一般の木だったら
2023/01/28(土) 22:55:37.76ID:5uR0b9AVM
EとかはSAISしたあとにLCPテーブルとセグ木を組み合わせる例の典型知ってればすぐ思いつくし、知識ゲー感あるな
2023/01/28(土) 22:56:20.81ID:qgxER/Mk0
あちゃー
また誤解法やらかしちゃいましたかね
ラッキーACの方が後でメンタル凹むのでWAにしてください
ダメ元とはいえテストケースで全部通ったから提出したけどやっぱり罠だったか
2023/01/28(土) 22:57:41.57ID:96l2/V8G0
C次数3以上の頂点を含む木のテストケースすら入ってないってガバガバすぎる
2023/01/28(土) 22:58:00.26ID:v1F80BgW0
>>362
ABCはいつも知識ゲーだぞ
例えばセグ木とかローリングハッシュとかをコンテスト中に自分で発明できるひとなんてほとんどいないし
2023/01/28(土) 22:59:17.24ID:5uR0b9AVM
Gみたいに座圧とデータ構造組み合わせる問題は思い付いてから書ききるまでが長くてストレス貯まる
2023/01/28(土) 22:59:36.80ID:5uR0b9AVM
Gみたいに座圧とデータ構造組み合わせる問題は思い付いてから書ききるまでが長くてストレス貯まる
368デフォルトの名無しさん (ｶﾞｯｸｼ 06b6-aVnv)
垢版 |
2023/01/28(土) 22:59:50.70ID:ah21+Up06
他の解法何も理解してないけどEはTrieが一番楽だと思ってる
2023/01/28(土) 23:01:27.73ID:5uR0b9AVM
Trieの方を先に思いついたがポインタアクセスの定数倍が怖くてやらなかった
2023/01/28(土) 23:01:42.36ID:96l2/V8G0
Eはソートすると両隣と比較するだけで済むけどTrie解法の方を知らない
2023/01/28(土) 23:04:32.64ID:u83RSs7NM
>>364
それを落としたい問題かと思ったのにな
372デフォルトの名無しさん (ｱｳｱｳｳｰ Sa47-muL6)
垢版 |
2023/01/28(土) 23:06:52.79ID:zcB4u36+a
>>371
解説に載ってるケースだから落としたいに決まってる
2023/01/28(土) 23:07:17.13ID:YAariq7ma
ワイもtrie木の存在を知らないまま再発明してた
もっと勉強しないとダメだな
374デフォルトの名無しさん (ｱｳｱｳｳｰ Sa47-muL6)
垢版 |
2023/01/28(土) 23:09:01.81ID:zcB4u36+a
今週は
将棋→atcoder→将棋→atcoderだけの休みw
2023/01/28(土) 23:09:31.14ID:pq/HO6/C0
Gを自作平衡二分木でやったらTLEしてしまった
2023/01/28(土) 23:09:39.07ID:aPfQHBSur
チラ裏
2023/01/28(土) 23:09:48.10ID:pq/HO6/C0
Gを自作平衡二分木でやったらTLEしてしまった
2023/01/28(土) 23:10:16.89ID:pq/HO6/C0
エラーで二重書き込みしてしまった
379デフォルトの名無しさん (ｱｳｱｳｳｰ Sa47-muL6)
垢版 |
2023/01/28(土) 23:10:33.81ID:zcB4u36+a
今週は
将棋→atcoder→将棋→atcoderだけの休みw
380デフォルトの名無しさん (ｱｳｱｳｳｰ Sa47-muL6)
垢版 |
2023/01/28(土) 23:11:17.15ID:zcB4u36+a
なんかサーバがおかしいね
2023/01/28(土) 23:11:26.35ID:u83RSs7NM
なんかエラー起きてるよな
サーバー不調か
2023/01/28(土) 23:13:35.66ID:96l2/V8G0
>>371
連結じゃないパターンとかはちゃんと入ってるのに解説の図にも載ってるようなシンプルな例外が含まれてないの謎だよね
2023/01/28(土) 23:24:23.55ID:fIsxhqrm0
Exって小さい方から追加してワーシャルフロイド的にやればできるよなーって思ってそこから進まなかったけど、そのまんまなんだね
bitsetでの高速化という発想がいつも頭から抜けてしまう
2023/01/28(土) 23:27:22.96ID:Kf8aKMUta
まあ次数の方の条件はあんまり見逃さないと思うけどな
自分も連結の判定拾えず1wa だった
2023/01/28(土) 23:29:46.89ID:fIsxhqrm0
参加者がミスりやすい連結判定ではあるけど、解説で必要十分条件を整理しているのにテストケースに反映されていないのを見るとうーんとなってしまう
2023/01/28(土) 23:30:23.85ID:fIsxhqrm0
ミスりやすいのは
2023/01/28(土) 23:47:00.96ID:u+A6uiDqM
ExはGにあったらもうちょっと気づきやすい感ある
2023/01/29(日) 09:03:53.81ID:MIUMphiq0
極端なテストケースを含めてない問題って意外とあるのかな
過去問を埋めてたんだけど、想定解では平方根で計算量を抑えるパートがあったのに普通にそこを全探索して通ってしまった
具体的にどの問題かとは言ってないからアレだけど自分で極端な場合を試してTLEすることは確認してる
2023/01/29(日) 11:25:47.61ID:qYdfKoIBa
C++なら通るってのは珍しくない
望ましいことではないけど大騒ぎするほどレアなことでもない
2023/01/29(日) 11:38:30.50ID:57gL/0v0a
ABCのC以下なら有り得るがD以上でそんなことあるか？
2023/01/29(日) 14:53:32.40ID:0HFOdqfjM
昨日のExもbitset高速化が本質なところを、C++で愚直にO(N^3)やっても通るらしいし（勝手にコンパイラがベクトル化してくれてbitset高速化と等価な処理をしてくれる）、後半の問題でも非想定愚直解が通ることは普通にある
2023/01/29(日) 14:55:09.47ID:0HFOdqfjM
そういうのは大体コンパイラが運良く賢い最適化を適用できたときだから、狙って出すのはそんなに簡単じゃない
2023/01/29(日) 19:04:35.25ID:Jc2Sgmhq0
コンパイラの気持ちになればベクトル化効きそうなコード書くのはそんなムズくないと思う
2023/01/29(日) 22:06:29.55ID:pu2XClQU0
他で類題が出たときにAtCoderはテストケースが弱いとよく言われている気がする
2023/01/29(日) 23:03:39.53ID:BP2z62OT0
終了2分後にC解けた…
2023/01/29(日) 23:03:56.11ID:MIUMphiq0
このwriterのARC-A問題毎回めちゃくちゃ難しくない？
Bすぐ気づけたから一命を取り留めたけどAの場合分けでごちゃごちゃさせすぎてWA量産してたから初めの一時間くらいは絶望状態だった
2023/01/29(日) 23:11:21.90ID:vpxmJyQa0
Aを未証明で通したけど解説見たら全然違うことやってたから自分の解法が正しいのか分からん
2023/01/29(日) 23:11:43.07ID:M39Yv40i0
今日難度調整する気あった？
悪ノリ勘弁してくれよ
2023/01/29(日) 23:16:45.73ID:0HFOdqfjM
Aはたしかに難しめだったけど、ARCで類題を見たことある気がする
2023/01/29(日) 23:26:35.43ID:4YZrQTY50
コンセプトだけならAよりCの方が簡単な気がする
Cは無限場合分けがキツいけど、天才的発想が要るタイプじゃない
2023/01/29(日) 23:32:43.87ID:0HFOdqfjM
Aも天才って感じの問題じゃないけどな
ただ回文って頭壊れるよな
2023/01/29(日) 23:34:37.09ID:0HFOdqfjM
Bがやたらと解きやすかったからAのやりにくさが際立ったのもある
2023/01/29(日) 23:51:53.28ID:MIUMphiq0
A問題diff1500超えは笑う　ARC最高記録かな
実際AGCって言われても違和感無かった
2023/01/29(日) 23:58:11.53ID:4YZrQTY50
前半も難しかったけど、任意色コーダーもお手上げのEFもすごい
500-500-700-900-1000↑-1000↑ぐらいの配点のAGCでも違和感がないね
ARCは定期的にこういう回が来る
2023/01/30(月) 00:26:54.26ID:DHQTrTSya
このまま開催が少ないと文句言われてるagc にすれば良かったよね
2023/01/30(月) 00:34:49.18ID:I07fAhlgM
TwitterのTLに昨日のABCの感想が混ざってるせいで、E問題F問題解けたみたいなツイートがたまに流れてきて驚く
2023/01/30(月) 00:47:36.97ID:AryvhmI6r
最新ツイート表示にしろ
2023/01/30(月) 15:34:29.73ID:o+SVBtiS0
Twitterで解決しなかったのでここで質問
昨日のARC-Cを手元でテストケース生成する時、値域は1≦A_i≦4で十分？
重複順列を全部生成しなくてもこれで網羅できてると思うんだけど、証明に自信が持てない
2023/01/30(月) 16:18:46.19ID:OdxjIVkkH
十分ってどういう意味？
2023/01/30(月) 16:34:57.65ID:NXr6DkIHM
解答の場合分けを全部網羅できるかって話ならまあできてそうじゃないか
偶数も奇数も種類数は3以上いらないはず
コンテストジャッジのテストケースとして十分かという話だと、微妙な嘘解法とかに弱そうな予感がするが
2023/01/30(月) 16:38:59.08ID:NXr6DkIHM
コンテスト中に実験や検証の目的で手元でテストケースを生成するという話なら、そこまで条件絞れてる時点でもうテストケース生成要らんレベルで解けてるだろ感あるが
2023/01/30(月) 18:06:00.04ID:o+SVBtiS0
仮に無限個のテストケースを一瞬でジャッジできるとして、1≦A_i≦2e5で作った2e5^N通りのテストケースと1≦A_i≦4で作った4^N通りのテストケースは任意のコードに対して同じAC/WAの結果を返すという主張です
2023/01/30(月) 18:08:07.48ID:o+SVBtiS0
任意の、は流石に過激主張か(57が入力に含まれているとpanicするコードなんかは落とせない)
場合分け系解法なら常に同じになる、程度で
2023/01/30(月) 18:19:02.93ID:NXr6DkIHM
想定解の場合分けをするコードの出力なら一致する
しょうもない話をするが、57を見たら常にYesを出力も場合分け解法だと思うので、場合分け解法なら常に一致するとは限らない
2023/01/30(月) 18:25:48.00ID:o+SVBtiS0
そりゃ想定解を書きゃ一致するだろ
そういう揚げ足を取って欲しい訳じゃないんだが
2023/01/30(月) 18:26:57.35ID:NXr6DkIHM
まあ偶数が奇数の種類数が3以上ある場合に挙動が変わって不正解を吐き出すような嘘解法って特に思いつかんよな
2023/01/30(月) 18:30:03.28ID:NXr6DkIHM
>>415
意図が不明瞭なんだが、要するにコンテスト中のテストケースとして十分か知りたいのか？
すなわち自然に生えてくる嘘解法を落とすには十分かみたいな
任意の場合分け系解法に対して、みたいな話なら一致しないコードをいくらでも構成できるから偽だが
2023/01/30(月) 18:30:45.18ID:o+SVBtiS0
あれだわ、こっちで証明書くから正しいか正しくないかだけ教えて欲しい

今回の問題は、Aの各要素の偶奇を定めた時、どの二要素が交換可能かという関係が1位に定まる
この時にAをBに一致できるかという問題はソーティングネットワークであるから、0-1原理より二値のみ見れば正当性が判定できる
各要素の偶奇もいるから、結局{1, 2, 3, 4}の4元のみで場合分けの正当性が判定できる
2023/01/30(月) 18:40:13.31ID:NXr6DkIHM
>>418
場合分けに偶奇いずれかの種類数が3以上のときに生じるような情報を使っている場合は、4元に置き換えた時点でYes/Noの出力が変わることがあるので偽なんじゃね
場合分けに使っていい情報をある程度制限すれば真になりそうだが
2023/01/30(月) 19:12:29.53ID:qb9bFNFJd
まだ全然理解してないけどプログラムを入力からソーティングネットワークへの関数だと思ってる？
2023/01/30(月) 19:21:19.32ID:M6Z3pSeYM
>>418
偶奇は要素に対する条件だからソーティングネットーワークは話が違う気がする
位置に対する条件だったらわかるけど
2023/01/30(月) 19:29:00.95ID:T038um/B0
プログラムは全ての(i,j), 1<=i<j<=Nに対し「最初位置iにあったものと位置jにあったものが交換可能」かを定め、それを元に判定を行うものであるという仮定がある？
2023/01/30(月) 19:33:31.82ID:T038um/B0
ソーティングネットワーク知らなかったけど面白そう
2023/01/31(火) 11:48:36.09ID:8ETcs3iMH
全然話についていけてないけど、場合分け系解法の定義がはっきりすればもうちょっと議論しやすくなりそう
2023/02/01(水) 10:33:12.46ID:rrqH0vUw0
多次元のデータを扱う過程でvectorだとMLEするのに全く同じサイズで代わりに生配列を使ったらメモリ制限余裕でクリアしたんだけど、これってvectorの方がより多くの情報を保持してるってこと？
軽く調べてみた感じvectorの各次元のサイズの順番次第でも変わってくるらしいんだけどもしかして生配列の方が地雷少なかったりする？
2023/02/01(水) 10:54:25.86ID:1VPsFaLs0
vectorは配列サイズより大きな領域を確保してpush_backに備えるから
push_backした時に現在のサイズじゃ足りないと二倍の大きさのメモリを確保してそこに既存データをコピーする
2023/02/01(水) 12:13:43.49ID:5KNYyuv90
多分だけど、
二次元の配列を生配列でやるとメモリ上は連続に並ぶけど
vectorでやるとそうではないので、その分のロスはあると思う
2023/02/01(水) 12:25:44.63ID:rrqH0vUw0
要素数を保持するメンバ関数.size()も悪さに加担してそうだけど色々原因が絡んでそうだな
生配列って変数を要素数に使えないのと初期値に気をつける以外に何か注意すべき点あったかな
2023/02/01(水) 13:47:00.53ID:ntrbSJFPM
vector<vector<T>>は多次元配列じゃなくてジャグ配列だよ
2023/02/01(水) 14:39:57.27ID:1VPsFaLs0
ジャグ配列という言葉を覚えたてでドヤりたいのか知らんけどC++で区別する意味ねーぞ
そもそも配列じゃないし
2023/02/01(水) 16:23:28.28ID:nE5IsTk9M
？
現にパフォーマンスに差があるって話してんだから区別する意味あるに決まってる
2023/02/01(水) 16:25:26.10ID:G8geOuCTa
よく「C言語に多次元配列はない、あるのは配列の配列だけだ」なんて聞くけど、じゃあ「真の多次元配列」ってなんなのさ
a[1,2,3]みたいに所定の個数の添字を使わないとコンパイルエラーになるような配列とか？
2023/02/01(水) 16:28:00.66ID:lgst1CuMa
>>431
日本語苦手？
2023/02/01(水) 16:35:05.84ID:lgst1CuMa
一般的な多次元配列というのはこれ
https://e-words.jp/w/%E5%A4%9A%E6%AC%A1%E5%85%83%E9%85%8D%E5%88%97.html
C言語で昔から多次元配列と呼ばれてたやつだ

ところがもう一種類の多次元配列を持つ言語が現れて区別の必要が出てきた
そのため片方を多次元配列、片方をジャグ配列と呼ぶようになった

ジャグ配列のジャグとはギザギザという意味で要素である各配列の要素数がバラバラという意味だな
C++の配列(vectorは配列に非ず)では区別の必要はない
2023/02/01(水) 16:46:12.82ID:G8geOuCTa
はえ～、じゃあジャグ配列ってのはいわゆるレトロニムだったのか
サンクス
2023/02/01(水) 17:19:44.17ID:Xxk6iIQM0
そうだね、レトロニムではある
C言語の初期から「配列へのポインタ」の配列を使うなんて当たり前だし

しかしメモリレイアウトがシーケンシャルになる多次元配列と、ポインタの配列は必要に応じて区別するもんだけど
2023/02/01(水) 17:42:02.48ID:lgst1CuMa
どこのメモリをどのように割り当てるかで用途やコードは変わるけどそれは特に「呼び分ける」必要はないってことだよ
他の言語のように文法から違うならともかく
たとえば二分木を配列にマップしてもそれは二分木だろ
2023/02/01(水) 18:12:59.33ID:5UExoC6r0
全く何が言いたいのかわからん
int A[3][5]は多次元配列でジャグ配列（配列のポインタの配列）じゃないと思うが
2023/02/01(水) 18:13:09.99ID:tEOpIEztM
C++のvector<vector<T>>はジャグ配列であって、当然多次元配列としても使えるがパフォーマンスは落ちるよね？ってだけなんだがそんなに変か？

要素数が動的な多次元配列（に機能を絞ってパフォーマンスを追求したもの）はC++にはなくてだからこそmdspanが提案されたりしてる
2023/02/01(水) 19:18:23.03ID:lgst1CuMa
>>438
大丈夫か？
ポインタの配列の話なんか誰もしてないぞw
多次元配列は一種類しかないから区別の必要はないと書いたよな？
2023/02/01(水) 19:20:20.77ID:lgst1CuMa
あ、そうかそうか
配列が第一級オブジェクトだと思ってるのかw
ちげーよw
442デフォルトの名無しさん (ﾜｯﾁｮｲ 1a55-5T4A)
垢版 |
2023/02/01(水) 19:23:36.17ID:zBkVwI+K0
レッドコーダーの人は、プログラミング言語についても詳しい人ばかりですか？
2023/02/01(水) 19:42:37.94ID:wHSgCyOm0
いいえ
2023/02/01(水) 19:53:24.92ID:5UExoC6r0
第一級オブジェクトじゃないと何が起きるの？
ポインタの配列をジャグ配列って呼ぶことにしていい？
2023/02/01(水) 20:30:34.21ID:bcQxhzDjM
抽象的なデータ構造としての配列の話をしてるのにC/C++の配列と混同してないか？
2023/02/01(水) 22:04:49.45ID:1VPsFaLs0
どうして寒色はこうも見苦しいのか
2023/02/01(水) 22:12:17.12ID:5UExoC6r0
ちな黄色
2023/02/01(水) 22:44:43.03ID:uzGFw6kGr
ソースは？
2023/02/01(水) 23:07:53.04ID:1VPsFaLs0
言語無関係な抽象的データ構造で多次元配列とジャグ配列を区別する意味なんてなおさら無いだろ
C/C++の話をしてるところにトンチンカンなこと言って割り込んできた言い訳がそれかよ
2023/02/02(木) 01:35:53.36ID:wNS591RpM
要件違うんだから区別する意味あるだろ
その調子だと配列もハッシュ関数がidなハッシュマップだから区別する必要ないとか言い出しそう
2023/02/02(木) 04:19:39.15ID:EnNL+Dwm0
元の話って速度の話じゃなかったのか？
ジャグ配列か多次元配列かは明確に速度が変わるから、考える意味はあると思うぞ
あとAtCoderはvector<vector<int> >をジャグ配列と呼んでる https://atcoder.jp/contests/APG4b/tasks/APG4b_t
2023/02/02(木) 08:03:13.54ID:unc+efpM0
抽象的なデータ構造だそうだからどちらが速いかはその言語によるぞ
2023/02/02(木) 10:49:56.77ID:EnNL+Dwm0
抽象的ってのは言語仕様に依存しない程度の意味じゃないんか
どの言語のジャグ配列も多次元配列より遅い、は真だと思うけど(もちろん多次元配列が無い言語はあるので、一次元配列で代用するものとして)
2023/02/02(木) 10:54:31.00ID:Yo++vCH+0
C#の多次元配列はジャグ配列より遅いよ
直感を信じずに速度が重要ならちゃんと検証しよう
https://zenn.dev/tremendous1192/articles/333df9cf3c0170
2023/02/02(木) 11:24:59.40ID:EnNL+Dwm0
>>454 検証結果マジか、シーケンシャルアクセスできるなら掛け算必要な方が遅いということかな
添字が範囲内なのかのassertなども含めると逆転しうるのか……
検証出してくれるのは助かる
2023/02/02(木) 11:27:29.66ID:EhYbzGf6a
んじゃそろそろイミフな言い訳やめてくれんかな
2023/02/02(木) 11:30:46.69ID:MROcVxaUM
不思議だな
どういう理由なんだ
2023/02/02(木) 11:34:06.46ID:EnNL+Dwm0
https://docs.unity3d.com/ja/2018.3/Manual/BestPracticeUnderstandingPerformanceInUnity8.html
この辺とか見た感じ、C#だと関数呼び出しで実装してるから遅いってことなのかな
速さを気にする言語じゃないし、こういうこともあるんだなぁ
2023/02/02(木) 11:34:22.95ID:MROcVxaUM
にしてもそもそもvector<vector<T>>をジャグ配列と呼ぶことに噛みつくこと自体がイミフじゃね？
2023/02/02(木) 11:37:52.38ID:MROcVxaUM
>>458
なるほどな
こういうのがあるから速度比較は難しい
2023/02/02(木) 11:48:18.09ID:EhYbzGf6a
>>459
え？w
2023/02/02(木) 11:53:17.19ID:QTnso+y6M
>>454
流し読みしたけどこの記事クオリティ低いから鵜呑みにするのはちょっと早計かな
3x2と2x3とかいうクソ小さい行列で実験してなんの意味があんのかよくわからんかった
2023/02/02(木) 12:00:46.82ID:eC04hXzt0
どこにUnityでC#動かしてる競技プログラミングサイトがあんだよ
「速さを気にする言語じゃないから」じゃないとか知ったかぶりはやめよな
2023/02/02(木) 12:02:39.09ID:Yo++vCH+0
>>462
それはそうだね、この記事だけじゃ微妙

でもまあ
"C# 多次元配列 ジャグ配列 速度"
とかでぐぐればいろんな検証結果出てくるし、いくつか見れば「多次元配列」は早いというわけじゃないのはなんとなくそれっぽいと思えるっしょ
2023/02/02(木) 12:05:07.71ID:bj9DDTEpd
C#は速さ気にしまくってるけど多次元配列は誰も使ってないし、あえて高速化するならSpan<T>で1次元扱いしたらいいから多次元配列は永遠に遅そう
2023/02/02(木) 12:06:06.09ID:EhYbzGf6a
自演きっついなこのスレ
なんだろう黄色を騙る茶色無職が常駐してんのかな
2023/02/02(木) 12:20:17.80ID:F3tsLQBup
ワッチョイがｱｳｱｳｳｰSaで文体が単芝使いの奴ってD問題で間違いを指摘されて暴言吐いてかつ浮動小数点数の話でも自分の間違いを一向に認めなかった奴と同一人物っぽいんだけど、もうスレのテンプレにNG推奨として追加した方が良くない？
前まではこんな奴居なかったし
2023/02/02(木) 12:22:50.20ID:Gzkf2uCba
だから無理矢理移住させると治安悪くなるって言ったのに
2023/02/02(木) 12:25:52.15ID:F3tsLQBup
端末使い分けてるか飛行機飛ばしてるっぽいんだけど、単芝使う+煽り文体+(今回の件でどっちが間違ってるかは置いといて)自分の間違いを絶対に認めようとしないって時点で同一人物なんだよなあ
2023/02/02(木) 12:31:31.89ID:ZUpBuKrwM
明らかに煽ることが目的のやつがいると思ったら個別にNGすればいいと思ってて、スレとして誰かをパージするようなことはしなくていいと思うんだよな
技術的な話に全く関係のないことを連投するやつが現れたらちょっと考える必要はあるが、全然まだそういうレベルじゃないだろ？
2023/02/02(木) 12:38:11.53ID:vof/cCRF0
議論になるなら良いんだけど、前例からもわかる通り間違ってることを堂々と発言した挙句に明白な根拠有りで誤りを指摘されても自分の誤りを認めず暴言を吐き始めるのが厄介だと思った
まあ今回の言い争いには直接絡んでないけどNGしとくわ
2023/02/02(木) 12:54:28.61ID:Ppl7cpkKa
ハッシュおじさんと同じ臭い腐臭
2023/02/02(木) 13:14:43.01ID:EhYbzGf6a
また論破されるから追い出すってかっこ悪すぎない？w
2023/02/02(木) 13:21:22.74ID:WNB2UXmap
前回で茶色になるようなレベルって自分で書き込んでるのにどこからそんな自信が湧いてくるのやら
それでいて寒色煽りしてるのも謎
2023/02/02(木) 13:55:09.74ID:unc+efpM0
論破されて自作自演で嘘の噂流すのかっこ悪すぎない？w
2023/02/02(木) 13:56:42.34ID:EnNL+Dwm0
このスレ、発言から青～黄が5人くらいは確定で居るからなぁ
某レッドコーダーも見てるっぽいし、下手な煽りは返り討ちにあう
2023/02/02(木) 13:57:36.22ID:unc+efpM0
返り討ちにあって追い出そうとするのかっこ悪すぎない？w
2023/02/02(木) 19:49:43.06ID:8e/EbPC1M
くんerのほうが知能高そうなのヤバいやろ
2023/02/02(木) 20:12:24.50ID:unc+efpM0
こいつより頭悪いやつなんていないだろ
2023/02/03(金) 21:24:06.48ID:ztTrwLKk0
明日のABCはARCよりかあ
やっぱり企業コンオンサイト予選はARC-likeな問題で選抜したいという思想はありそうだね
2023/02/03(金) 22:01:20.08ID:qVKOoofIp
中盤はいつもよりも難し目らしいからギリギリDが解けるかどうかみたいな層は明日厳しいかもね
キーエンスのD青EF黄程にはならないと思うけど
2023/02/03(金) 23:16:24.28ID:3wOaiFyt0
緑から水色の初心者から中級者の間の層が狩られそうね
2023/02/04(土) 00:15:56.94ID:5HHfxRG3M
「終盤は難しくない＝普段のABCと一緒」って意味だと仮定すると、中盤がARCで後ろはマニアック高度典型という、ただの昔の企業コンARCなんだよな
だったらU2800 ratedでもよくね？って思ってるけど、そこまですると初心者層が萎縮して参加しないかもしれなくて怖いんだろうか
2023/02/04(土) 00:18:39.84ID:5HHfxRG3M
企業コンは参加者数も稼がなきゃいけなくて大変だなって話
2023/02/04(土) 01:50:55.48ID:XT9wb8Pda
早解き苦手緑なんで明日は棄権しますわ
2023/02/04(土) 02:37:15.31ID:11TJ16Po0
ライバルを減らそうと必死で草生える
2023/02/04(土) 04:02:38.09ID:VlutLTNz0
高度な情報戦
2023/02/04(土) 20:49:46.88ID:DuPn66LGM
ちょくだい先生結婚マウントやめてください
2023/02/04(土) 21:45:26.38ID:qwiiBCAF0
週1回コンテスト前の30分～1時間だけ過去問題Bを1～2問解いて本番するだけにしてから苦行ストレスがほとんどなくなりました
今日はC初見問題だけど自力で考えて30分台でC解けたので満足

C問題最速で45秒でACとかテンプレ用意しててコピペレベルなのでしょうか？
Dなんて一応毎回問題だけはチラ見するけど何やったって自力で解法思いつかないから
もう開き直って毎回Cまで解いていつか茶色に成れればいいや
2023/02/04(土) 22:20:10.55ID:5scjLUe90
コンテスト中は順位表から読み取れる内容以外は他言に無用らしいから掲示板にはあんまり書かないほうがいいぞ
2023/02/04(土) 22:40:34.13ID:qwiiBCAF0
D嘘解法ぽいけど閃いたと思って暇つぶしに提出したらAC3TLE40WA3ってことはそこそこいい線行ってたぽい？
2023/02/04(土) 22:41:27.74ID:VlutLTNz0
ABCFの4完
やっぱりDに手を出さなきゃ良かった
2023/02/04(土) 22:43:35.14ID:YxTB5YYsp
キーエンスの再来だった
494デフォルトの名無しさん (ﾜｯﾁｮｲ 3f10-4O5A)
垢版 |
2023/02/04(土) 22:50:22.13ID:l8ebE2EL0
あと少しで国内200位入れなかった
層が厚すぎる
2023/02/04(土) 22:51:01.60ID:ZgVy8P1Na
>>491
問題外
496デフォルトの名無しさん (ｱｳｱｳｳｰ Sa93-/68i)
垢版 |
2023/02/04(土) 22:58:09.16ID:mQgt/9sra
>>489
ヒントになった途端通報されるかもしれないので注意
今回の場合、試験中に「Dが難しい」と叫んでいると取られかねない
497デフォルトの名無しさん (ﾜｯﾁｮｲ ffe2-Cjv8)
垢版 |
2023/02/04(土) 22:59:01.54ID:/q0XctAl0
なんでこれをDの位置におこうとおもったんだ
2023/02/04(土) 23:04:37.21ID:6AvE22Ut0
400点以上だと体感Fが一番簡単だったな
2023/02/04(土) 23:05:57.02ID:6AvE22Ut0
>>489
コンテスト中にSNSとか5chにコンテストのこと書き込むのは真面目にやめた方がいいよ
2023/02/04(土) 23:11:58.81ID:qwiiBCAF0
D問題で区間総和÷K=0で閃いたと思ったけど条件が足りなかったみたい
501デフォルトの名無しさん (ﾜｯﾁｮｲ cf01-EJkl)
垢版 |
2023/02/04(土) 23:14:05.17ID:366SNyz60
C問題で当たり前のようにunion findとかが出てきてビビった
勉強せんとなあ
2023/02/04(土) 23:15:42.29ID:qwiiBCAF0
解説見たらやっぱり何やってもこんなのコンテスト中に解けないやってなりますわ
おとなしくCまでを確実に解く練習を毎週末するだけでいいや
2023/02/04(土) 23:17:46.82ID:qwiiBCAF0
先週もだけどC問題で出るグラフ問題はACLのDSUに慣れさせようとする作問者の意図を感じます
解説もACL使ったら軽いと露骨に明示されてたから多分普及させたいんだろうなと
2023/02/04(土) 23:20:09.21ID:qwiiBCAF0
もう来週の問題も作成済みでACL使うグラフ問題シリーズが来週も出そう
とか言ってると来週はグラフ出すのやめたりするかな
ここ見てる？
2023/02/04(土) 23:20:54.02ID:ZgVy8P1Na
そんな当たり前のことを得意げに言われても…
506デフォルトの名無しさん (ﾜｯﾁｮｲ ffe2-Cjv8)
垢版 |
2023/02/04(土) 23:26:03.10ID:/q0XctAl0
unionfind、初中級のアルゴリズムの本にのってない気がする、atcoder高度すぎ
2023/02/04(土) 23:26:58.45ID:qwiiBCAF0
参加回数が規定数に満たないってことなんですが
今回ABCまで解けてレート380点とパフォーマンス７40点で差が360点くらいあるんですが
規定回数超えたら茶色に成れますかね？
茶色に成れたらもう満足なんですが
2023/02/04(土) 23:41:16.52ID:qwiiBCAF0
C問題で下記のようなコードで提出してACだったのですが
解説と違ったのですが解法として合ってますか？

（事前にいつものACLのDSUで入力済みとして）

　sum = 0;
foreach (g, d.groups()) { sum += g.size() - 1; }
cout << M - sum;
2023/02/04(土) 23:53:19.75ID:IojJ2/cf0
あってる、もっというと以下でいい
auto g = uf.groups();
int ans = m - (n - g.size());
2023/02/04(土) 23:59:17.63ID:6AvE22Ut0
UnionFindは、中身の理解と計算量解析自体は簡単ではないかもしれないけど、ブラックボックス化して使う分にはとても単純だから、まずはそういうものだと思って把握しといて損はないよ
2023/02/05(日) 00:01:06.52ID:L8nGaYgK0
Gはゼータ変換メビウス変換の要領でやれると思ったけど毎回頭がこんがらがる
いつかのARC-Dでもこういうゼータ変換メビウス変換の変種が出てた気がするけど、そのときもきつかった
2023/02/05(日) 00:13:05.03ID:zXAayJwsM
Eを最初セグ木でmin取ろうとしたらTLEして致命傷で済んだ
2023/02/05(日) 00:16:42.68ID:+Je3j6OX0
>>509
ありがとうございます
また嘘解法だったかと不安でしたが安心出来ました

ただDは解説配信見てもさっぱりでした
2023/02/05(日) 13:32:12.10ID:E/3apluda
union find は「プログラミング・コンテスト・チャレンジブック、第2版、2012」に載っていたような？
2023/02/05(日) 14:39:10.64ID:BCHcg2ZAM
競プロ本じゃなくて一般的なアルゴリズム本には載ってなさそうではある
516デフォルトの名無しさん (ﾜｯﾁｮｲ 3f55-zLlH)
垢版 |
2023/02/05(日) 14:44:21.92ID:bw48TasH0
>>515
セジウィック＆ウエイン
CLRS
浅野孝夫
の本に書いてありました。
517デフォルトの名無しさん (ﾜｯﾁｮｲ 3f55-zLlH)
垢版 |
2023/02/05(日) 14:45:43.39ID:bw48TasH0
>>515
Kleinberg & Tardosの本にも書いてありました。
2023/02/05(日) 15:24:54.49ID:TzydnmM+M
ありがとう
よく考えたらクラスカル法をまともに実装すりゃセットで出てくるから普通の学術書でバンバン出てくるものか
すまん、適当なこと言ったわ
2023/02/05(日) 15:35:59.28ID:TzydnmM+M
昨日のEx見てるがそれぞれのパーツはそんなに難しくなくても、コンテスト中に詰めるのは相当な情報処理能力要るなこれ
最上位は既に知ってる部分が多いから思考をショートカットして解けてる（部分問題はKUPCで既出）のか、初見でも化け物みたいな処理能力があるから解けるのか
2023/02/05(日) 23:56:53.84ID:L8nGaYgK0
enumerative combinatoricsで式クソデカ数え上げの練習をしよう
2023/02/06(月) 14:57:07.46ID:tLnW5713M
ちょくだい暇空信者だったのか…
2023/02/06(月) 17:17:12.74ID:CC5umvVS0
信者では無くないか？
どっちについても炎上するから関わりたくない、が直接反応されたから返答はしたように見える
AtCoderユーザーは暇空寄りだから、どちらかと言うと暇空側の立場を取るのが正解だし
本当は無反応が最善のはずだから、リプ返した時点で暇空応援の気持ちはありそうだけどな
2023/02/06(月) 17:28:55.79ID:5KzQx2I0M
＞AtCoderユーザーは暇空寄り
そうなんだ…ショック
2023/02/06(月) 17:55:26.95ID:8VwvYIdS0
誰やねん
2023/02/06(月) 18:05:31.15ID:atEmb0ZA0
誰だよ(´・ω・`)
2023/02/06(月) 18:34:28.57ID:vCbzFpDWM
chokudai定期的にいらんことに首突っ込むよな
2023/02/06(月) 19:09:41.21ID:P7WNzTvaa
最近やたらとイキってる陰謀論界隈の教祖様だろ
中立っていうならリプ返さないでほしい
心底気持ち悪い
2023/02/06(月) 19:29:13.93ID:TL/Aw+TK0
なんでミュートじゃなくてブロックするんやろなぁ。SNSの使い方下手すぎん
2023/02/06(月) 19:30:02.45ID:TL/Aw+TK0
ブロックした理由を解説して死体蹴りしてるのも謎
2023/02/06(月) 19:31:39.97ID:mjq9iwD6M
暇空応援公言は普通にショックだわ
あの界隈を胡散臭いと思わない感覚は怖い
2023/02/06(月) 20:23:50.09ID:7jgjd4tm0
ブロックにしても暇にしても弁解必死過ぎて草
2023/02/07(火) 12:48:26.37ID:Gs46GCc3M
ABC232E Rook Pathなんだけど、
解説だと、ゴール(x2,y2)の位置で場合分けしてるんだけど、
スタートとの位置関係で分かれるんじゃないの？
シミュレーションしてみたらそんな挙動。

計算は同じになるんだろうけど
533デフォルトの名無しさん (ﾜｯﾁｮｲ 3f55-zLlH)
垢版 |
2023/02/07(火) 13:08:37.18ID:TWDaaH+/0
↓上級編がでますね。

アルゴリズム実技検定　公式テキスト［上級〜エキスパート編］
中村謙弘、ｔｓｕｔａｊ
2023/02/07(火) 13:38:15.54ID:zZYboOb2a
>>532
値が同じところで分けるとそうだけど、
多分解説は値が同じところで分けてるわけじゃなくて答えが計算しやすいように分割してるだけ
（集合内のfの和でgを定義してる）

このあたり確かに文章の流れがミスリーディングだね
2023/02/08(水) 19:11:20.77ID:2gR5KQQeM
公金の使われ方とか言って暇空は応援するのに
五輪談合で逮捕者出てる電通から金貰ってるのはいいの？
私女だけど男の人のダブスタ悲しい
2023/02/09(木) 18:50:48.66ID:g9RtUNgNa
ロシアと強いつながりがある競技プログラミングコミュニティ
2023/02/09(木) 21:38:31.53ID:qp4RAwsP0
ロシア批判に消極的に見えるのは
男子校理系的なキモさの極地って感じ
2023/02/09(木) 23:54:08.08ID:KDi1Xk2qr
>>535
今ホットなのは暇空の方だしなぁ
話題性のある方に言及するのは普通でしょ？
2023/02/10(金) 07:46:52.03ID:W3KrKL2I0
競プロに関係しそうなq-類似の中国語記事
https://zhuanlan.zhihu.com/p/202494934
https://www.cnblogs.com/amagaisite/p/16475758.html
540デフォルトの名無しさん (ﾜｯﾁｮｲ 3f55-zLlH)
垢版 |
2023/02/10(金) 12:38:57.68ID:GORLgW5U0
アルゴリズム実技検定　公式テキスト［上級〜エキスパート編］
中村謙弘、ｔｓｕｔａｊ

↑予約注文しました。
2023/02/10(金) 15:45:03.21ID:4TIGievXM
q類似って情報量増やすシリーズですか？
2023/02/10(金) 18:12:43.91ID:ajYYAE4c0
情報量増やすシリーズって何
2023/02/10(金) 21:35:37.67ID:oC8O9KZEM
https://codeforces.com/gym/102978/problem/A
なんか、こういう総数は簡単なんだけどもうちょい細分化したものを数えたいときに新しい変数とかを導入するテクニック的な
2023/02/11(土) 00:45:13.40ID:v67POrgW0
まあ情報増やす感じよね
自然数の代わりに、[n]_q = 1+q+...+q^(n-1)というqの多項式を考えみる
そうすると普段の数え上げで出てくる概念についてもq-類似というものを考えることができて、q-類似はオリジナルより細かい情報を持っている
例えば普通の階乗は順列の数え上げだけど、そのq-類似であるq-階乗[k]_q! = [k]_q [k-1]_q ... [1]_qは、r次の係数が転倒数rの順列の数え上げになっている
どうしてそうなるかは挿入DPの要領だね
1を代入する、つまり係数の総和を取ればオリジナルの階乗を復元できもする
2023/02/11(土) 00:45:52.02ID:v67POrgW0
さらにq-二項係数というのもあって、binom(n, k)_q = [n]_q/([k]_q [n-k]_q)なんだけど、r次の係数が、r個の区別できない球をk個の区別できない箱に分ける（箱の容量は最大n-k個の球を収容可能）場合の数になってる
同じ意味だけど「grid上のpathで区切る領域の面積がrのpathの場合の数」の方が直感的にわかりやすいかな
https://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1194&context=hmc_theses
すぐに役に立つ概念かわからないけど、数え上げの精密化と考えると面白い
2023/02/11(土) 00:47:23.46ID:v67POrgW0
>>545
訂正：path→lattice path
2023/02/11(土) 00:49:35.69ID:v67POrgW0
>>543
とかいろいろ書いておきながら普通にこれ俺にとって難しくて解答読んでも自信ない
まずVを無視した数の割り振りが、境界線の数え上げに対応してて、それぞれの境界線を適宜微妙にずらすことで非交差路の数え上げに帰着してLGV公式で解ける
さらにLGV公式で使う行列の各要素（すなわちある始点からある終点への行き方の数え上げ）を改造して、ある点pより右下を通過することが確定するところを通ったらx倍、点p自体を通ったら0倍みたいなルールでxの一次式を作り、Lagrange補間の要領で行列式の多項式を計算してV次の係数が答え的な感じ？
比較的典型性の高い数え上げを多項式で細かく分けて、係数から欲しい情報取り出すというのはまさにって感じに見える
2023/02/11(土) 17:12:01.33ID:rBS0t6wJM
どちらかというと、q-二項係数がFq上n次元ベクトル空間からk次元部分空間を選ぶときの数え上げになってるって話の方で存在を認識してたな
係数を見るというより、何かを代入して情報を取り出すタイプ
2023/02/11(土) 17:15:03.20ID:rBS0t6wJM
実装には詳しくないが、(1-q^n)/(1-q)みたいな疎な多項式の除算にできることを利用して高速化できる感じなのか？
2023/02/11(土) 19:05:11.90ID:Avc4ARa4M
q-二項係数を分割の数え上げで解釈する話も部分ベクトル空間の数え上げで解釈する話も証明見たら見たらせやな感あるが、この2つのどこがどう対応づいているのかあんまよくわからんな
2023/02/11(土) 19:35:59.54ID:DstcEta5H
またAGCやばそうな配点だ
endagorionってどんな問題出すんだ？
2023/02/11(土) 20:31:02.43ID:ht8bMudq0
C++17が多数派だと思うのですが
C++20が未だに対応されない理由って何なのでしょうか？

本業が忙しすぎてそこまで手が回らないとか？
費用対効果が低くて恩恵を得られる人が少ないとか？
過去問まで対応させるとなると多すぎて単純に面倒だからとか？

上記全部当てはまりそうだから仕方ないか・・・
2023/02/11(土) 20:50:07.00ID:H4oosVmb0
>>552
AtCoderなら、近いうちに言語アップデートが入るからそこで追加されるのでは？
2023/02/11(土) 20:59:47.47ID:ht8bMudq0
>>553
そうなんですか？
知らなかったです
ありがとうございます

もしよろしければ言語アップデートのソース元ってありますか？
2023/02/11(土) 22:41:03.83ID:ht8bMudq0
Bは面倒そうなので飛ばしてC
解法はすぐに思いついて実装に手間取って30分で提出したが
1つだけREになるコーナーケース？が分からずに時間切れ

残り15分くらいで一瞬Bやりかけたけて問題見たけど
CのREが分からないイライラを引きずって萎えたやる気出ないので
順位表見てたけどやっぱ今回のBCは難易度高かったぽい？

毎回こんなの1分2分で解いてる人いるけど
どんだけテンプレ用意してるんだろう

最速AC時間からすると自分のテンプレから探してコピペする時間としか思えない
2023/02/11(土) 22:42:57.96ID:T7V722zO0
Eまで脳死で解いていく問題セットでしたね(´・ω・`)
2023/02/11(土) 22:45:13.25ID:EnOI2f+w0
Convex hull trickEDPCで調べたばかりだったのに存在を忘れてた
2023/02/11(土) 22:46:55.58ID:MMfnVwYs0
5完でまったり
2023/02/11(土) 22:49:04.63ID:Avc4ARa4M
Fえらく簡単だなと思って実装してみたら想定の数倍厄介な問題だったな
2023/02/11(土) 22:50:22.19ID:8B7uiFw80
>>555
基本的にはみんな普通に問題文読んでコード書いてるだけだ

極まってる赤色のひとだとこれぐらいの考察速度でコードを書く
（まあ、このひとに限っては更にコードゴルフもしてるからかなり変態っぽいけど）
https://www.youtube.com/watch?v=su1QrfVkZK4
2023/02/11(土) 22:53:21.26ID:ht8bMudq0
>>560
A問題ならまだ見て書くで分かる気がしますが
B,C問題をコピペじゃなくて1分,2分台で読んで書いてACって既に人間と思えないんですけど
上位様方達は凄いんですね
2023/02/11(土) 22:53:39.17ID:Avc4ARa4M
Bは読解めんどくさいけど、レ点の存在を知ってればだいぶ思考節約できるし、ある程度上級者ならソラで書いても1, 2分で解けるんじゃないか
2023/02/11(土) 23:04:09.59ID:ht8bMudq0
C問題でACが28/29でREが1つだけ残ってて分からないのですが
コードのどこがおかしいか分かりますか？
テストケースが公開されていないので思いつかなくて・・・

自作関数などは省略してます
https://i.gyazo.com/58576b7851ef6038272e7cb78af48707.png
https://i.gyazo.com/e14f6e1124bfff6c2f117f807dbff63b.png
2023/02/11(土) 23:05:29.61ID:EnOI2f+w0
今回のGみたいな出現頻度低めの高度典型忘れた頃に出題されるから中々身に付かない
2023/02/11(土) 23:06:39.24ID:Ps6JrzP7r
>>563
あたま
2023/02/11(土) 23:07:40.96ID:Avc4ARa4M
Exは除原理で立式して母関数使って整理するときれいな除算になるのか
Exは結構な数の問題がFPS講座になっている気がする
2023/02/11(土) 23:08:45.56ID:W6Ts6djNM
Bってグラフの説明いるの？
あれをまじめに読んじゃったせいで時間無駄にした
2023/02/11(土) 23:11:50.37ID:Avc4ARa4M
厳密に書くにはあれが一番なのかもしれないが、それはそれとして、やる操作に対して記述量が多すぎて驚く
2023/02/11(土) 23:13:14.69ID:ht8bMudq0
>>565
ありがとうございます
ヒントが冒頭って意味でしょうか？
ヒントじゃなくて頭が悪いってことならそのとおりなので異論はありません
2023/02/11(土) 23:17:15.33ID:Avc4ARa4M
>>563
vectorの宣言だけどvst(N)じゃなくてvst(M)にすべきなんじゃないか
逆にRE1個で済むんだな
2023/02/11(土) 23:18:47.90ID:ht8bMudq0
>>570
＞＞あたま
のヒントで気づいて
それでACなりました
572デフォルトの名無しさん (ﾜｯﾁｮｲ c6e2-lZ4L)
垢版 |
2023/02/11(土) 23:21:04.95ID:lZkIj9hH0
Fが黄色。Fが青色上になったらノーカンにすべき。
2023/02/11(土) 23:22:15.58ID:ht8bMudq0
思い込みと言うかこんな些細なミスに気づかずに1時間半も悩んでてて1完でメンタル壊れますね
REが解決できなくてドツボにハマる典型だと思いますが
すぐにBに着手してればもしかしたら解けてたかと思うと残念です
今日はBを今から解いてみて寝ます
2023/02/11(土) 23:25:03.24ID:glz4wAHkH
確かにF青、G黄ぐらいが理想ではあるけど、一色上振れぐらいはいいんじゃないかな
FもGも難問って感じはしなかったけどやっぱりあの場合分けはキツいのかな
2023/02/11(土) 23:34:21.84ID:0pKJqIeQ0
来週またTOYOTAだからABCの難度壊されるのか
オンサイトの枠なんかARCで好きに争っといてくれ
2023/02/11(土) 23:43:36.37ID:Avc4ARa4M
昔の企業コンARCの問題と比較すると普通にトヨタはARCでいい気がするんだよな
2023/02/11(土) 23:54:48.28ID:ht8bMudq0
>>573
無事B問題30分ぐらいで解けました
予想通りACLのDSU使えました
3回連続は無いだろうと思ってたのに
やっぱこっち先にやればよかったトホホ
2023/02/12(日) 00:15:48.81ID:V1WHF7OO0
AGCの配点5-8-8ってA問題から青〜黄色の激重セットになりそうだな
579デフォルトの名無しさん (ﾜｯﾁｮｲ a751-t1ev)
垢版 |
2023/02/12(日) 00:20:22.77ID:ulhmgCnx0
>>554
AtCoderの言語アップデートに関して 2023年版
https://atcoder.jp/posts/966
です　アップデート自体がいつになるかはわかりません…
2023/02/12(日) 00:22:33.59ID:clMPTfPu0
>>579
ありがとうございます
丁度今さらっとシート見終わってここに戻って来たとこでした
2023/02/12(日) 00:24:27.27ID:clMPTfPu0
アプデ前後にC++20で使える便利情報などが出回りそう
2023/02/12(日) 01:22:02.99ID:icQYZybb0
>>549
そうだね、1-q^nは性質がよくてありがたい
たとえばq-二項係数なんかはbinom(n,r)_q = Π_{i=1}^{r} ((1-q^(n-i))/(1-q^i))と表せてlogを取ると

log binom(n,r)_q = Σ_{i=1}^{r} log (1-q^(n-i)) - Σ_{i=1}^{r} log (1-q^i)

なわけだけど、log (1-q^i) =　- Σ_{k=1} q^ik / k（ここで疎であることが効く）を利用し、
log binom(n,r)_qをN次まで求めるのならばO(NlogN)で求められる（調和級数）
binom(n,r)_q = exp(log binom(n,r)_q)もexp取る操作がNewton法でO(NlogN)でできて、最終的にはO(NlogN)
2023/02/12(日) 01:30:42.49ID:icQYZybb0
(1-q^n)/(1-q)で定義されたq-数の積で表されるようなものならこの方針でほぼ対応できるんじゃないかな
2023/02/12(日) 01:40:39.16ID:C1wEjrCY0
>>581
https://qiita.com/Chippppp/items/620d2e5229f5c7e93f0c
もうまとめてくれてる人いるね
競プロでよくお世話になりそうなのはnumbers,bit,autoあたりかなの印象
2023/02/12(日) 09:16:26.52ID:un5eNNRqd
言語アプデでGoとか相当良くなるんじゃないかな
Generics使えるようになるし
2023/02/12(日) 14:42:18.02ID:CSrZ4laXM
これもq-二項係数の言葉で説明できたりしますかね？

https://yukicoder.me/problems/no/986
2023/02/12(日) 14:54:27.27ID:CSrZ4laXM
例のQiita記事覗いたけど20代の主婦ってワードでちょっとびっくりしちゃった 周りにそういう生き方してる人いないので
2023/02/12(日) 17:03:52.39ID:icQYZybb0
>>586
最後のはもろにq=2のq-二項係数だね
Π_{i=0}^{N-1} (2^M-2^i)/Π_{i=0}^{N-1} (2^N-2^i)
= Π_{i=1}^{N} (1-2^(M-i+1))/(1-2^i)
= binom(M, N)_2
丁度>>548に書いてある話かな、q=2以外のF_qでも同じような議論ができる
問題の誘導がお手本のようなq-二項係数の導出方法になっていると思う

あとすまん、>>582は指数ミスってるね、 Π_{i=1}^{r} ((1-q^(n-i+1))/(1-q^i))が正しい
2023/02/12(日) 18:43:07.51ID:clMPTfPu0
>>584
それ見てatcoderはC++20対応まだなのかなって思ったんですよね
以前C++やる前にpython触ってたのでrangeなどの配列操作に慣れてたので
なんでC++こんな面倒なんだろうって思ってました
自分はC++20のrangeが便利そうだなって思ってます
テンプレで自作関数用意しちゃえばなんでも大差ないんでしょうけど
やっぱSTLや標準機能で動いてるって安心ですよね
2023/02/12(日) 23:32:43.82ID:0sfCeSzya
今日のwriterロシアの人みたいだけどなんでatcoderでの出題なのかな
2023/02/13(月) 00:05:27.27ID:WRIz5JLb0
実験したらパスカルの三角形が出てきたから色々調べて何とかlucasの定理まで辿り着けたんだけどこれA問題で知識として要求されるレベルなのか
2023/02/13(月) 01:21:21.02ID:vDWSczYhM
Lucasって言うと大袈裟に聞こえるけど再帰的な構造を見つけてくださいねってだけじゃね？
2023/02/13(月) 01:24:37.51ID:vDWSczYhM
>>589
競プロだとコード長制限の観点からも嬉しいですね
テンプレもりもり書いてると結構すぐ超えちゃうので
2023/02/13(月) 21:58:26.16ID:OIki8MNs0
>>590
海外でも難問と言えばAGCという評判だから、難しいセットをAGCに投稿しようと思う外国人はいると思う
2023/02/13(月) 22:36:59.14ID:+IUsA8sLM
普通にtourist AGCとかあるしな
2023/02/13(月) 22:49:24.44ID:LZG8araOd
こういう人を見ると凄く勿体無く感じる
何故、中卒なのかは分からないけど1年ちょいで青コーダーになれるだけの地頭があるなら、勉強をすれば東大や京大にだって余裕で受かるだろうに

【AtCoder】中卒の主婦が青コーダーになったおはなし【競技プログラミング】
https://qiita.com/mayocorn/items/4edff486428240864808
2023/02/14(火) 00:21:59.23ID:ZFw6lJcb0
主婦に東大目指せと？
2023/02/14(火) 01:29:58.32ID:VKT916IkM
どういう学歴を辿るかは本人の自由だろうし、余計なお世話ではないか
2023/02/14(火) 01:32:50.93ID:VKT916IkM
>>588
あーこれだこれ
俺が知ったのはABCのEx問題かなんかだったが、解説でこのゆきこの問題と同じような感じで導出してた覚え
2023/02/14(火) 01:46:29.47ID:5DlOZ5Hp0
>>598
本当これに尽きる
2023/02/14(火) 02:20:57.01ID:Wz7VKY2h0
東大生が～とか中卒が～とか何を話すにもわざわざ学歴を書いてイキらなきゃいいだけだぞ
2023/02/16(木) 01:26:12.31ID:3p1Q75Q90
ガチのフルコミットする奴(子なし主婦やニート)が増えれば青＝東大の相場は崩れる気がする

まあ子供育てる予定があって自分が東大レベルの学力を狙える根拠が1つでもあるならとりあえずやってみる、というのは子育て戦略として面白いし普通に優良
2023/02/16(木) 08:10:30.22ID:w6YN+jFIr
青=東大なんて言ってるの学歴厨しかおらんよ
マ板のゴミみたいな文化をこっちに持ち込むな
2023/02/16(木) 10:41:54.29ID:+t6ZDN8fa
青って蔑称だろ
2023/02/16(木) 21:15:09.06ID:rkG4MAfkd
凄いのは凄いって言えばいいのに他所から「勿体ない」って言うのは傲慢よ
2023/02/17(金) 06:48:56.83ID:UHXTRGs00
ABCの3完が精一杯でBやCが解けないこともたまにある灰色なのですが
ARCって参加して0完でもパフォ少し出ることあるから参加したほうが良いって本当ですか？

ARCのAすら解けないから毎回参加してなかったのですが
なんかスコア稼ぎみたいでズルっぽいので躊躇するけど
もし本当なら0完参加もありかも？
2023/02/17(金) 12:37:56.14ID:RI5g/O/Qa
何もせず稼げるとしてそれが嬉しいなら自分でやってみたらいんじゃね
2023/02/17(金) 14:06:14.64ID:zgzLkC5Da
某所で見かけた問題（どこの問題かは規約の関係で言えない）なんだけど、いくら考えてもわかんなかったから誰か教えてほすぃ

N 個の正整数 L_1 ～ L_N が与えられる。ここで以下の二つの「操作」から好きな方を選ぶことを繰り返す。

・L の要素を任意に一つ選び、X 減らす。
・L の要素を任意に Y 個選び、それぞれ 1 減らす。

L の全ての要素を 0 以下にするには最低何回の操作が必要か？

1 <= N <= 100000
1 <= L_i <= 100000
1 <= X <= 100000
1 <= Y <= N
（制約条件はこれであってるはずだけどもし記憶違いだったらゴメン）
2023/02/17(金) 14:19:41.06ID:KfAjW7Cn0
出展不明の問題には解答してはいけません
不正に荷担することになるかもしれません
2023/02/17(金) 14:22:27.12ID:NWP5oZ6I0
それがどこの問題か知ってるけどその問題を公開することは許されてるわけ？許されててもダメだと思うけど
2023/02/17(金) 14:26:54.61ID:zgzLkC5Da
マジか、伏せとけば大丈夫かと思ったわ
じゃあ諦めるわ
2023/02/17(金) 15:36:51.10ID:oH3qhdRZM
かなりムズい気がするな
このスレではどのみち解けなさそう
2023/02/17(金) 16:40:00.47ID:NWP5oZ6I0
や、俺は解けたけどな！
2023/02/17(金) 17:24:12.44ID:lUBsB8PI0
そんなに難しくはないけど、確かに解答したくはないな……
自力で頑張ってくれ
2023/02/17(金) 17:36:44.85ID:RyB0R6hga
簡単すぎて草
2023/02/17(金) 20:35:59.16ID:36NScQFi0
マジでこれが難しいって言ってるのか？
茶色？
2023/02/17(金) 20:39:57.57ID:KfAjW7Cn0
diff1600くらいはあると思う
2023/02/18(土) 03:39:57.25ID:z42F5xKlM
Lは昇順にソート済みとする
まず後者の操作だけ考えるとmax(L_N,ceil((L_1+...+L_N)/Y))が下界で実は達成可能（この値は1回の操作で必ず1以上減らせる）
となると前者の操作は値の大きい方からやるべきで前者の操作回数を全探索することにすると二乗logにはなるがこの先がわからん
2023/02/18(土) 06:27:43.34ID:DSkO7LYG0
難しいじゃん 黄Diff以上はありそう
2023/02/18(土) 12:46:27.04ID:O1Eq2rH/M
>>618
シミュレーションの際に同じ値はまとめれば毎回最大値が1以上減るからステップ数抑えられるか
その間の算数はk個に操作するとして
k+max(m,ceil((s-x*k)/Y))
という式の最小化
面倒だから雰囲気だけだけど多分最小と最大とmaxの中身が丁度等しくなるとこくらいを調べれば十分なはず
2023/02/18(土) 14:52:45.65ID:BcR09etJ0
ドヤりたいのわかったからヒント出すな
2023/02/18(土) 18:29:18.45ID:RCps3ZLd0
>>606
レーティングって長期的推移でみるものだから高々1個実力外で稼げたものは所詮あぶく銭にすぎないしパフォ目的ならオススメはしないかな
チャレンジしたい！って心意気ならすご〜くいいと思います
2023/02/18(土) 20:05:46.57ID:m1tWkkPx0
>>622
ARC過去問覗いて見てそっ閉じしました
問題文や解説すらさっぱり理解出来ないので
せめてA問題が理解出来るくらいまでは参加は諦めます
2023/02/18(土) 20:35:51.39ID:7rS3BtILr
誤爆見たぞ
2023/02/18(土) 23:19:15.25ID:uCZODILj0
Cまではとっつきやすかったね
chineristさんの回だからまた相当な難問が来るかと恐れていたけど
2023/02/18(土) 23:24:56.87ID:aJr9M57cM
B問題は実家DP的ななにかを予想して遷移考えたけど、思ったより普通の算数で解けたな
Cは制約がゆるすぎて逆に解きにくかった
こんなこと言うと競プロに過学習してるっぽくてよくないんだが
2023/02/18(土) 23:35:35.53ID:uCZODILj0
Cの制約ってジャッジの都合なんかね
2023/02/19(日) 00:05:31.17ID:QIU8wOlZM
>>624
見たぞ2
少なくとも3人factorioスレ見てるやつが居るな
2023/02/19(日) 06:03:20.76ID:zi/avb6A0
寝起きでARCのA問題見たらちょっと閃いた気がしたので
20分くらいですぐにサンプルACしたので提出したら見事にWAでしたｗ

流石にARCだからコーナーケースが仕込まれてるとは思いましたが
考えても何も思いつかないのですぐに解説見たけど理解するのに1時間くらい掛かりました
多分本番やってたらWAにドはまりしてストレスでメンタル壊れてたと思うので
精神衛生的に不参加で良かったです

最速提出で2分台の方のコード2つ見ましたが
まるでコーナーケースを知ってるかのようなコードでしたね

問題を読んでコーナーケースまで把握したコードを2分台で提出してACするってことは
典型問題として類題知ってるってことでしょうか？
本当に初見で直感で2分台なら凄すぎます

でも5分以内ACも20人くらいいるからわかる人には分かるのかな
2023/02/19(日) 12:49:58.63ID:+vmWHN9sM
類題知ってるとかではないと思うよ
2023/02/19(日) 13:34:36.91ID:ndErR/0m0
2分はともかく、30分かけて良いなら解けなきゃダメだと思うよ
長さ15くらいまでのテストケース全生成は幅優先探索やるだけABC-Cくらいの難易度なので、これを作って手元で確かめれば条件なんて自明
2023/02/19(日) 14:04:10.80ID:wF9NNslx0
想像しているようなそっくりな問題を解いたことがあるみたいな話ではないけど（多分上位層は初見でも2分で解ける）、何個かの要素に分解できるところはあるかな

・偶奇に注目、二つ裏返すということは1は偶数個じゃなきゃダメ
・自明な下界を考える、2つ以上離れた1のペアを作れれば達成できる
・1が2個のときはコーナーケースっぽい、特に小さいケースについてはなるべく注意した方がいい

こういうのをできる人は無意識に一瞬でやってるから、何をいまさら言語化しているんだって感じだろうけど
2023/02/19(日) 14:13:36.32ID:wF9NNslx0
ある意味ARC典型みたいなところがあるかな
Cも自明な下界を考える問題だったし、Bは貪欲にある数まで下から埋めたあと分配する問題で、賢い筋を一つ見つけて他の筋を枝刈りするタイプの問題が多い
634デフォルトの名無しさん (ﾜｯﾁｮｲ 4501-H9O3)
垢版 |
2023/02/19(日) 15:26:29.04ID:6ltfFQqY0
AはARC-Aに置かれてると条件は基本的にシンプルになるけどたまに場合分けを要求されるみたいな雰囲気を感じ取れる(いつかのこどふぉで全く同じコーナーケースに注意すべき問題もあった)し、Bも条件の厳しいものからあらかじめ決めておいて残りは重複組み合わせ等で簡単に処理するっていう考え方をARCで何回か既に見たからARC典型みたいなのは問題を解き進めてるうちに身につくと思う
Aのパリティとか不変量とか上界下界に注目するみたいな典型考察も含めて(鉄則本とかにも書かれてるくらい典型だからもう既に知ってる人の方が多そうだけど)
2023/02/19(日) 16:44:56.04ID:zi/avb6A0
>>634
貴重な情報ありがとうございます

ARC-Aクラスの難易度はまだ無理ですが
ABC-Cならなんとか解けることもあるので

＞＞問題を解き進めてるうちに身につく

ことを信じて自力で解ける範囲で少しづつやってみます
636デフォルトの名無しさん (ﾜｯﾁｮｲ 1be2-LwiH)
垢版 |
2023/02/19(日) 17:45:36.48ID:4PdnTZn50
緑だけどARCは不出場になった、青以上じゃないと時間の無駄になる気が
2023/02/19(日) 18:07:28.78ID:9mvO2Aur0
昨日のC、類以度いくつ達成できそうかは手元で実験してすぐ分かったけど、
すべてのケースで条件満たす構築が結局コンテスト中にできなかった
どうやって思いつくのあれ
2023/02/19(日) 18:34:54.00ID:Lpep47s30
類以度が2以上になるのはどういうときかを考えたら思い付いた
2023/02/19(日) 19:58:25.28ID:62Qdm88BM
パスの場合1通りしか答えないからその理由考えて適当に一般化
2023/02/19(日) 20:02:27.76ID:1mDvNRVXM
パス上でオリジナルの数字とPで変換して出てくる数字で被りがあるとうざそう→適当に木を二分割して移し替えればよくね？→頂点数の偏りが少ない分割がほしいから重心を使う
パス上でオリジナルの数字とペアとPで変換して出てくる数字のペアの相対的な前後関係が一致してるとうざそう→重心からの位置関係がオリジナルと反転してればよくね？

想定解はちゃんと読んでない
2023/02/19(日) 20:04:27.80ID:1mDvNRVXM
>>636
今回のAは解ける問題だった気がするが
2023/02/19(日) 20:10:26.59ID:1mDvNRVXM
400点のARC-Aは厳しい問題な可能性が高いな
なんなら500点のARC-Bより人によってはとっつきにくい
300点のARC-Aはそこまで異常問題ではないことが多いはず
ABC-Cよりはずっとムズいけど
2023/02/19(日) 22:40:53.59ID:hD2KB5kP0
5完
Dでバグりすぎた…
644デフォルトの名無しさん (ﾜｯﾁｮｲ 4501-H9O3)
垢版 |
2023/02/19(日) 22:43:01.55ID:6ltfFQqY0
Eまで早解き出来てFもO(N)で求められる式の導出までは出来たのにそこからの式変形がダメだった　勿体無い
2023/02/19(日) 22:46:42.14ID:wF9NNslx0
FよりGの方が簡単かな
2023/02/19(日) 22:52:00.36ID:1mDvNRVXM
Gは貪欲でよさそうなことにさえ気付ければ実装も楽でかなり解きやすいな
2023/02/19(日) 22:55:52.45ID:wF9NNslx0
Fもいわゆる自明な上界問題っぽいし、今回も結構ARCチックだった
地味にDもこの位置では難しいのかも？と思ったけど結構みんな解けてるね
2023/02/19(日) 22:57:21.27ID:wF9NNslx0
そしてExがかなりの難問っぽいね
2023/02/19(日) 22:59:11.51ID:Lpep47s30
Gの貪欲が証明できん
これしかないだろと思って投げたから通りはしたが
2023/02/19(日) 23:02:45.64ID:1mDvNRVXM
俺も証明してない
とりあえず、深さ2ぐらいまでf(x,n)（n個の部分木と接続したままxを作るときの最小コスト）みたいなのを考えたらnがなるべく小さいほうがいいことに気付いて、またxで単調減少しそうだから、どうせ親にも性質が伝播するんだろうなあみたいな考えでやった
651デフォルトの名無しさん (ﾜｯﾁｮｲ 4501-H9O3)
垢版 |
2023/02/19(日) 23:03:01.88ID:6ltfFQqY0
F非想定解とはいえ畳み込みやらFPSやらをやればO(N)の式を高速化出来たっぽいしちゃんと履修すべきだったな
自分は普段はFくらいまでしか解けないからまだ要求されないもんだと思って後回しにしてたけどこういう時に殴れないの勿体ない
2023/02/19(日) 23:04:53.51ID:zi/avb6A0
DのサンプルだけACしたけど
そりゃ提出しても愚直解だとTLEですよね
解説見たけどこんな条件気づける気がしない
考え方の方向性は間違ってないけどここまでが自力の限界ぽい
2023/02/19(日) 23:06:53.95ID:1mDvNRVXM
知識を取り入れてABCでレート上げるのはARC/AGCでレート上げるより楽なので、どんどん高度な知識を取り入れていいと思うな
2023/02/19(日) 23:09:33.70ID:wF9NNslx0
>>652
Dは典型ではあるからこれを機に知っておくといいと思うよ
(N/GCD(N,D))*Dで初めてNで割ったときあまり0のところに戻ってくる
こういう操作はかなり頻出だと思う
655デフォルトの名無しさん (ﾜｯﾁｮｲ 4501-H9O3)
垢版 |
2023/02/19(日) 23:14:10.61ID:6ltfFQqY0
OEIS使う裏技は知ってたけどwolfram alpha使う裏技もあるんだな
wolfram alpha の計算式にはガンマ関数とかsqrt(pi)が出てきたから自分で更に式変形する必要はあるけど今度から使えそうな場面では試してみよう
2023/02/19(日) 23:15:02.27ID:zi/avb6A0
ありがとうございます
解説見ても頭に入ってこないというか難解過ぎて咀嚼出来ない？ので
時間のある時に落ち着いてじっくり考察してみます
657デフォルトの名無しさん (ﾜｯﾁｮｲ 1be2-LwiH)
垢版 |
2023/02/19(日) 23:22:11.62ID:4PdnTZn50
D、解説が難しいし何の役にも立たないので理解する気力がわかない・・・
2023/02/19(日) 23:22:37.30ID:wF9NNslx0
wolfram alphaを使うプレースタイルだとΓ(1/2) = √πみたいな知識も役に立つのかな
総合格闘技感があって面白い
2023/02/19(日) 23:34:24.39ID:wF9NNslx0
Dは例えばN = 15, D = 6としよう
〇××××××××××××××
一旦、x+1に移るルールを無視して、4移動してマーキングするというルールで考える
〇×××××〇××××××××
〇×××××〇×××××〇××
〇××〇××〇×××××〇××
〇××〇××〇××〇××〇××
〇××〇××〇××〇××〇××
〇××〇××〇××〇××〇××

と、間隔3の場所を延々と巡ることになる
NとDが他の値でも似たようなことが起きて、この間隔が実はGCD(N,D)で簡単に出せる
660デフォルトの名無しさん (ﾜｯﾁｮｲ b5bd-HtMB)
垢版 |
2023/02/19(日) 23:35:10.23ID:wF9NNslx0
>>659
ミス、4移動じゃなくて6移動

で、実際のルールでは、マーキング済みのところについたら1ズレるわけだけど
実はいつも最初は0に戻ってくることが分かって、
〇〇×〇××〇××〇××〇××
って感じ
上のと同じ動き方で1と間隔3で離れている場所が全部埋まる
〇〇×〇〇×〇〇×〇〇×〇〇×
全部埋まった後に1に戻ってきて今度は2に移って同じことをする
2023/02/19(日) 23:40:08.29ID:wF9NNslx0
何の役に立つかというと、直接的に役に立つ気はしなくて、頭の体操感あるかなあ
でもこういう比較的複雑ではない方のアルゴリズムに慣れておくと、複雑なアルゴリズムを頭の中ですぐイメージできるような気がするね
662デフォルトの名無しさん (ﾜｯﾁｮｲ 4501-H9O3)
垢版 |
2023/02/19(日) 23:42:32.81ID:6ltfFQqY0
Dのax-by=0みたいな式を立てた上でgcd(a,b)で全体を割ることで互いに素であることが利用できるようになって一般解が求まる、みたいなのはABCのD、Eくらいで何回も出題されてるだけでなく受験数学でも典型ではありそう
663デフォルトの名無しさん (ﾜｯﾁｮｲ 4501-H9O3)
垢版 |
2023/02/19(日) 23:44:04.64ID:6ltfFQqY0
例えば今回のEまではパターンマッチングで瞬殺だけどそれだと寒色止まりだしつまりはそういうことだ
2023/02/19(日) 23:44:43.08ID:wF9NNslx0
>>661
あ、すまん、文章のパースミスってて、D問題が何の役にも立たない話かと思った
解説で理解できないって話ね
2023/02/19(日) 23:46:01.21ID:wF9NNslx0
Gも貪欲でいいという点で確かにARCっぽいのかな？
666デフォルトの名無しさん (ﾜｯﾁｮｲ 1be2-LwiH)
垢版 |
2023/02/20(月) 00:48:04.55ID:fGKXGDUx0
微積分も知らずに青まで行ける方がヘンだと思うので特殊関数も出すべきじゃ
2023/02/20(月) 20:17:16.00ID:PxqX9j8n0
>>659
分かりやすい解説ありがとうございます

こういう図解が解説に無い時に
解説の文章にある数式（今回だとgcd(n,d)など）から
自力で何をしているのかシミュレーションを想像するまで辿り着けないんですよね
時々図解がある解説見るとスッと頭に入ることあるのでそういう時は助かります
単純に競プロや難易度に必要な基礎学力や経験が足りてないんだとは思います
2023/02/20(月) 20:19:39.00ID:PxqX9j8n0
過去問題だとほぼ解説動画あるので大体解説動画見てますね
2023/02/20(月) 23:07:52.80ID:0Cmnf2dqM
Dは@kyopro_friends氏がtwitterに図説を上げてるよ
あと解説放送も今やってるよ
最近はコンテスト翌日ぐらいにやってることが多い
2023/02/23(木) 07:31:29.61ID:1grYshwD0
>>669
ありがとうございます

＞＞最近はコンテスト翌日ぐらいにやってることが多い
それは知りませんでした
お忙しいので動画無いのかなとか思ってました
あと@kyopro_friends氏さんってatcoder内部の方ですか？

やっとAB問題埋め全完了して
C問題を順番にやろうと思ったけどテーマがバラバラなので集中出来ないと思ったので
鉄則本を少しづつ進めつつそのテーマに沿ったtagに集中するようにしたら
勉強がやりやすくなった気がします

ただ時間が中々取れないので週末だけだと覚えたと思ってたこともすぐに忘れてしまう
生まれつき記憶力のある人が羨ましい
2023/02/23(木) 15:59:11.87ID:+RIqqxOF0
フレンズさんは作問バイトの一人のはず
内部の人ではないけど作問には関わってる
2023/02/23(木) 21:26:34.11ID:+C77Ee77a
バイトは内部の人とちゃうの
2023/02/23(木) 22:20:45.10ID:1C5iFFW5M
バイトも雇用契約を結んでる従業員なんだから、立派な内部のひとだろ
バイトを外部のひと扱いにしたら世の中が大変なことになるぞ
2023/02/23(木) 22:42:49.92ID:e18jgvu00
必要なのはAIのエンジニアであって、競プロerなんて時代遅れだよ
今後は機械学習を開発する力を面接でも重視する
そういう方針にするからこそレガシーエンジニアのレイオフを思い切ってやれてる
675デフォルトの名無しさん (ﾜｯﾁｮｲ 1be2-LwiH)
垢版 |
2023/02/23(木) 22:51:30.93ID:licQP1K00
chatGTPに使われてるtransfomerは全く教プロと関係ない。
強化学習はヒューリスティックで活用できる人がいるかもくらいで、ノーマルコンテストには縁がない。
2023/02/23(木) 23:01:59.48ID:E/62bCTqM
誤爆ですごめんなさい
2023/02/24(金) 17:34:08.73ID:Vhm6qXev0
>>671
やはりそうでしたか
解説動画が出る前に要点がまとめられていて図解があって分かりやすくて良いですね
これ見てすぐに理解できないならまだその問題を解くレベルに達していないと判断しやすいです
2023/02/24(金) 17:45:00.38ID:Vhm6qXev0
GCJが無くなるってことはどういうことなんでしょうか？
Googleが教プロは将来的に継続する程の費用対効果が得られないと判断したという解釈とか？
上位入賞者に米国人がいなくて海外勢特に中国人だらけだから面白くないとか？
ChatGPTに対抗する為にコストやリソースをそっちに集中したいとか？
2023/02/24(金) 18:05:59.77ID:+ha2KkIh0
すべてありえそうだけど最大の理由は「そもそも採用に力を入れていない」でしょうね
レイオフしまくってるし
2023/02/24(金) 19:02:57.49ID:Vhm6qXev0
>>679
なるほどですね
昨年からだと世界的に数十万人レイオフですか
上位数%の優秀な人しかいらないってことなのかな
2023/02/24(金) 20:55:11.73ID:nnH412iY0
コロナ禍にIT投資が過熱して採り過ぎちゃったし
いまは急に市況が悪くなって人件費と今後しばらくのリターンが見合わないから、解雇するんすよ

日本にいるとそれほど意識しないかもしれないけど
世界的にはこれから長い長い不景気に突入する空気感
2023/02/24(金) 21:47:19.51ID:iatI3MYQ0
寂しいけどGoogleがもう普通に兢プロに価値見出してないだけだと思うよ
2023/02/25(土) 00:41:17.79ID:limy/30G0
フレームワークとライブラリが充実してきたので
あまりレベルの高い仕事はなくなってきたという感じか
2023/02/25(土) 23:00:26.14ID:nWmUkLp60
ARCギャンブル初参加して約50分くらいでまぐれのA解けてラッキー
最速の人1分20秒と毎度のことながら驚愕

Bも行けそうかと手を付けたけどやはり難解過ぎて頭から湯気が出そう
残り時間も無いし解法も思いつかないので順位表見てたら
B飛ばしてCやってる人が多かったから多分Bは考えて解くのは難しいのだろう

Cも覗いてみたけど典型のテンプレ持っていれば解けるんだろうな
準備してなかったけど迷路探索のテンプレで
全探索してY隣接の最大値更新して間に合うのかな
でも流石にARCだから高速化を考えないと解けないようになってるのかな

時間切れまで暇つぶしの感想書いてみた
2023/02/25(土) 23:04:01.00ID:a6k9O4fx0
C、Bよりも簡単だった気がする(Bは罠が多すぎてWA複数回踏んだ)
Cの上位互換みたいな問題が数ヶ月前のABC-Gで出題されてたしそれ思い出したらすぐだった
2023/02/25(土) 23:13:22.62ID:5auW8s5PM
普段のARCと比べると解きやすいが、AとBはコーナーケース踏んで死んだ
2023/02/25(土) 23:14:19.32ID:5auW8s5PM
Cの解法は典型的な思考法ではあるが、典型のテンプレ持ってるから解けるみたいな話じゃないぞ
2023/02/25(土) 23:16:03.43ID:4osFE3lg0
むずいよー
2023/02/25(土) 23:19:38.16ID:nWmUkLp60
>>687
おっしゃる通りでございますね
解説見て無理だと悟りました

これはどんなに勉強しても理解出来るレベルに達する内容じゃないです
解説見て理解出来ないんだから本番で思いつくはずがない
2023/02/25(土) 23:19:52.87ID:0J3LFvp60
ARC二連続で爆死して橙が遠退いた
2023/02/25(土) 23:32:25.54ID:nWmUkLp60
やっと入茶出来たみたいです
まぐれARC1完で+60以上出てラッキー
直近がABC3完でも+5前後とかだったからびっくり
なんかもう入茶出来たから満足しちゃった
2023/02/25(土) 23:40:02.41ID:lAuJViPq0
writerの人の印象から勝手にグラフアルゴリズムや最適化回になるかと思ったけど、数え上げメイン回だった
Fがそういうものなのかな？
2023/02/25(土) 23:41:12.36ID:lAuJViPq0
>>691
おめでとう
典型パターンに習熟していないうちはARCの方がパフォーマンスが跳ねやすいと思う
2023/02/25(土) 23:49:34.61ID:5auW8s5PM
鬼のように数え上げを出してくる某writer以外は出題分野そんな偏らない気がする
なんとなく個性は見えるけど
2023/02/25(土) 23:52:25.38ID:nWmUkLp60
>>693
ありがとうございます
まぐれギャンブルで貰った+60なので
ABCずっと参加してC落としたりすればすぐに適正に収束すると思いますので
400切らないように頑張ります
2023/02/25(土) 23:56:17.38ID:Wvdh4FAba
こいつの日記になっとるな
2023/02/26(日) 00:29:44.52ID:KteJNFXu0
>>695
今日のA解けたんならABC-Cは慣れれば安定して解けるようになると思う
2023/02/26(日) 01:15:14.28ID:RLqrz5us0
Bの全てXかつK=0のケースが3つも入ってるっぽいんだけど注意力勝負すぎるしK>=1でも良かっただろとは思う
全てXとYを例外とさせるのはまだわかるけど
2023/02/26(日) 08:38:18.60ID:P5+y9Ehh0
>>697
ありがとうございます
色々な勉強法あると思いますがマイペースが大事ぽいので
ストレスにならない程度に気長にコツコツやってみます
2023/02/26(日) 10:43:52.85ID:zsK8B1uM0
前半はコーナーケースを詰める力そのものを聞いてるんだろ、それ無かったらやるだけだし
自分もBは4ペナしたけど、この問題のコンセプト自体は否定しないぞ
好きか嫌いかなら嫌いだが
2023/02/26(日) 13:58:36.43ID:aJFdfs9NM
シンプルな問題設定と非自明なコーナーケース、もはやARC典型
2023/02/26(日) 14:00:40.00ID:aJFdfs9NM
2、3分でスモールテストケースでの愚直実験一通り回せるぐらいの腕力が欲しいところだな
2023/02/26(日) 22:41:20.91ID:yj4g0aG10
6問早解き大会だった
2023/02/26(日) 22:41:34.84ID:P5+y9Ehh0
ABC3完は出来ましたがみんなAC速すぎてパフォーマンスが出ないですね
参加してる人のレベルが高いというか
諦めて参加しなくなった人が多いのかな
参加人数も1万人いた頃に比べたら今アクティブ7千人弱くらいだし

Dって過去問か他コンステストで類題ありましたか？
C飛ばしてD速い段階でACしてるのにその人達がC解けないって意味が分からないから
もしかしたら有名な典型問題だったのかなと
2023/02/26(日) 22:45:10.92ID:RLqrz5us0
Fまでの早解きゲーになっちゃったけどF1100人近くも通すもんなんだな
下振れた時が怖いしこれくらいの正答数のG、EXなら解ける域に早く達したい
2023/02/26(日) 22:47:09.49ID:KteJNFXu0
Exでこんなにきれいに重心分解がそのまま出るとは意外だった
2023/02/26(日) 22:49:22.15ID:KteJNFXu0
Gの方が考察の難易度的に難しいと思うけど、重心分解は知識レベルとしては高度という判断なのかな
2023/02/26(日) 22:51:29.63ID:FFsIOXN5M
今回のFはEと同じくらいの難易度だな
500点同士と600点同士で同程度の難易度の珍しいコンテスト
2023/02/26(日) 22:56:31.58ID:KteJNFXu0
>>704
Dはかなり典型的なDPの問題だから類題はたくさんあるけど、Cより解きやすくなるってことはない気がするかなあ
まあでも問題の相性はあるからね
2023/02/26(日) 23:00:00.31ID:FFsIOXN5M
こんなん重心分解でしかないやろで投げたけど、ちゃんと証明してなかったな
2023/02/26(日) 23:07:18.29ID:P5+y9Ehh0
>>709
そうなんですね
DPはチラ見したことありますが数問やって全く理解出来なかったので保留してます
まだ累積和とか二分探索すらよく分からないので鉄則本が全然進まない状態です
気長に理解できそうなとこからやってみます
2023/02/26(日) 23:08:10.19ID:KteJNFXu0
xorやandやorの相互変換もたまに効く典型の印象
あと1bitの場合andが普通の積と一緒になるのも畳み込みと併用することを考えるとありがたいね
2023/02/26(日) 23:10:24.52ID:KteJNFXu0
>>711
EDPCというコンテストの一番簡単なやつから理解していくのがいいかな
DPは慣れるまでが結構難しくて、慣れたらABCだとそんなに頭使わなくて済むようになる
2023/02/26(日) 23:14:40.03ID:FFsIOXN5M
Fって一般DAGでも解けるのか
2023/02/26(日) 23:16:04.01ID:EjsCh+nAp
D問題最初誤読して「全てのカードの表面に書かれてる数が異なる」って思って一瞬焦ったけどこの場合も解けたりする？既出っぽい気もするけど
2023/02/26(日) 23:20:28.91ID:P5+y9Ehh0
>>713
ありがとうございます
今やりかけのもの終わったらまた少しDP覗いてみます
2023/02/26(日) 23:28:04.31ID:FFsIOXN5M
>>715
とりあえずグラフを考えて、カードをA_iとB_iをつなぐ辺とみなす
このグラフの各連結成分を見て、なもり木なら閉路部分の割当で2通り、木になってるんなら木DPでうまく数え上げて、それ以外は0通りみたいな感じにして、総積を取る感じか？
なんか既出感がすごいな
2023/02/26(日) 23:30:03.03ID:FFsIOXN5M
なもり木って書いたがなもりグラフか
2023/02/26(日) 23:37:20.19ID:x0T0FVaip
>>717
カードの表裏をグラフの辺に帰着させて連結成分ごとに頑張るみたいな考え方で確かに出来そうだし典型的な考え方な気もするからこの設定の場合もABC-E、Fくらいに置いてあれば違和感無いな
今回はABC-Dだったからすぐ誤読に気づけたけど
2023/02/26(日) 23:39:18.11ID:KteJNFXu0
Fで出て青diffのどこかって雰囲気の問題に見える
2023/03/02(木) 21:21:27.03ID:krvD26HF0
DP練習問題などいくつか試してみましたがほとんど理解出来ませんでした
シンプルな典型問題を解説写経ACするだけの繰り返しになっていて
初見の問題を見る都度解法が全く思いつかないしDPを全く組めません
コピペしても通るような典型くらいしかAC出来ませんので
本番初見問題では役に立たないと思います

EDPCは解説の入力が省略されていたり
写経してもDPや入力の配列の添字が分からずその間違いでWAやRE多発してしまいます
解説をコピペしても通らないものもあってかなり時間ロスしました
アルゴ式は導入問題くらいは図解も毎回あって分かるのですが
応用問題になると解説が概要とコードだけなので何故そうなるのかさっぱり理解出来ませんでした

多分相当長いこと典型をやり続けてひたすら慣れるしか無いのでしょうが
時間対効果というか達成感が全く無くストレスが貯まる一方でモチベが続かないので
やはりDPは後回しにすることにします

DPが理解できずに苦労したとか覚えるの大変とは聞いていましたが
やってみてそのとおりだと痛感しました
2023/03/02(木) 21:42:44.71ID:spiXxYvqr
そうなんだおじさん「そうなんだ」
2023/03/03(金) 00:13:18.97ID:mfKjEfhRa
いちいちここで報告する必要ないんだよカス
2023/03/03(金) 01:13:35.32ID:ZUR2cvxRM
いや、無駄に煽って荒らしたいやつのほうがカスだろ
2023/03/03(金) 01:29:49.23ID:mfKjEfhRa
カスを擁護するカスまで現れた
自演かもしれんが
2023/03/03(金) 01:42:44.95ID:o7jNKaWI0
解説を見ても理解できないDP練習問題ってなんだ？気になる
2023/03/03(金) 02:43:36.86ID:RMDCzs1h0
「判りませんでした。私は頭が悪いです。わーんわーんわん」って泣き言いう前に分からないとことか問題を貼ろう
728デフォルトの名無しさん (ﾜｯﾁｮｲ 5a10-UQ7i)
垢版 |
2023/03/03(金) 03:46:50.79ID:CKnG+JfY0
多分初めのうちは、どういう時にDPを使ったら良いのか分からないって感じだと思うんだけど、
自分は昔「2^nの全探索が無理ならDP」って覚えた(最近だとABC291Dとかもこれ 他にもたくさんあると思う)
2^nの全探索の処理を考えたら、添字に何持たせたら良いのか出てくる気がする
bitDPとか区間DPなどの○○DPは初めのうちにやると混乱するから、まずは↑を出来るようにすると良いと思う
あと、dp配列の定義をきちんと決めることが大事で、ふわふわしたままコードを書くと当然上手くいかない
例えば「dp[i][j]: [0, i)でj個選んだ時の最大値」みたいにコードを書く前にきちんと決める
(dp[i]は「[0, i](閉区間)の答え」とするよりも「[0, i)(開区間)の答え」とした方がコードが綺麗になることが多い)
後は問題をたくさん解けば慣れるはず
729デフォルトの名無しさん (ﾜｯﾁｮｲ 6951-wWxq)
垢版 |
2023/03/03(金) 06:19:46.91ID:2nUF2qs80
DPは、状態をまとめて管理したり、操作した結果部分問題に帰着するって考えるとわかりやすいと思う
たとえばそれぞれについて選ぶか選ばないかで 2^N 通りあると、選ぶ・選ばないを決めると 2 つの新しい部分問題に分かれて、
その結果を合成する必要があるけど、結局見るべき「状態」の種類は少ないからメモ化して突破できる～って感じ
添字はfor文の端っこを意識するとバグりにくくなると思う
2023/03/03(金) 06:51:28.66ID:cgS4S0K80
EDPCはHがクソ簡単だからそこから始めるのも手だと思う
部分問題の合成結果が最終的な答えになるって感覚がわかりやすいし
2023/03/03(金) 09:26:45.13ID:gIW+HSjV0
わかるまで考える習慣がないだけじゃないの
2023/03/03(金) 12:17:26.75ID:qJ9yKeqra
おちんぽこぴーーーーーーーーーー
2023/03/03(金) 12:46:35.40ID:synOrNZV0
>>726
EDPCだとA～Iまで試してみて自力で解けたのはCとHの2問だけでした
他の練習問題などでやった記憶があってそれをコピペしたら動いたってだけでした
なので何故そのようなDPを組んで正解が出るのか理解してるとは言えない状態です
つまりEDPCほぼ全てで解説を見ても理解できないということです

>>728-730
丁寧なアドバイスありがとうございます
2023/03/03(金) 12:48:06.16ID:synOrNZV0
せっかく丁寧なアドバイス頂いていて恐縮なのですが
NGして無視してるとは言えどうしても目に入ってしまう非人間的な誹謗中傷もストレスになってますし
自分は頭が悪くて理解できないこと自体がストレスになっているので
DP含めて競プロ全般理解出来ないものは素直に諦めることにします

それでも解けそうで解けないものが解けた時は嬉しかったり
分かる範囲のものを勉強している時は楽しいので
マイペースで出来るものだけでも少しづつ試してみます

あと知人が誹謗中傷で亡くなっています
昨今のニュースなどでも誹謗中傷で亡くなる方も多いと見聞きします
誹謗中傷してる方は軽い気晴らしのつもりなのでしょうが
間接的に殺人に加担してることを理解して欲しいです
2023/03/03(金) 13:25:43.57ID:KvE4f0GAa
このカスなに被害者ぶってんだろね
自分が荒らしと自覚してないんだな
2023/03/03(金) 13:45:39.68ID:+mc9SOeYa
喧嘩するなって
ここは競プロスレだろう？
競プロの話だけしようや
2023/03/03(金) 14:28:51.14ID:o7jNKaWI0
このスレの荒らしは高度アルゴリズム関連を一切呟かず、延々と他者を下げるから分かりやすいのよな
個人的にはDPは漸化式、が高校数学の延長になって一番分かりやすかった、配る方が立式できないのがネックだけど……
貰う方なら、例えばEDPC-Bならdp(0)=0, dp(i)=∑[j=max(0, i-K), i-1] dp(j)+|h_i-h_j|と書けば後はコードにするだけだし
2023/03/03(金) 22:34:24.89ID:XfM0EojcM
貰うってf(x)をaだけ平行移動するとf(x-a)的な添字の難しさを感じる
2023/03/03(金) 22:38:28.74ID:caemo4Qqp
自分も「貰うDP+累積和」よりも「配るDP+imos法」の方が添字ミス減る気がする
2023/03/03(金) 23:21:34.43ID:3ciSJAS40
俺はプログラマだから、DPは順番が違うだけでメモ化再帰とほぼ同じ、ってのが最初にしっくりきたな
関数型言語をやってると再帰はごくごく当たり前に理解できてるからね
まあ漸化式だとか再帰だとかいろんなイメージ付けをしていくことでDPへの理解が深まっていろんなのが解けるようになっていくもんだと思うわ
2023/03/03(金) 23:29:36.68ID:1hMfTn3h0
俺も再帰でシミュレーションすれば答出るけど時間足りないって時に
配列に答置いとけばいいんだっていうのが最初だったな
2023/03/04(土) 00:16:45.91ID:12eSXtYNp
自分は更新順序とか何の値が既に確定してなくちゃいけないかとかを考えるのがだいぶしっくり来たかな
2023/03/04(土) 00:21:42.50ID:12eSXtYNp
基本は漸化式(特に受験数学の確率漸化式)みたいな気持ちだけど更新順序が非自明な時はメモ化再帰でやると楽みたいな
2023/03/04(土) 03:48:50.15ID:7GCZL+pYM
EDPCで初見で解ける問題があるだけ上等じゃねえの
ただ、解説読んで理解できないのは今後あらゆる問題で差し支えるから、それはどうにかした方がいいな
まずEまでは理解できるようにした方がいい
2023/03/04(土) 14:44:05.85ID:BpTmjwzWr
メモ化再帰は普通自分で再発明するよね
2023/03/04(土) 15:17:22.32ID:K6gP6y8f0
お前らずっとマウント取ってるな
寒色の癖に
747デフォルトの名無しさん (ｵｯﾍﾟｹ Sr45-4pPF)
垢版 |
2023/03/04(土) 16:18:10.94ID:mfmYzmTvr
安倍ちゃんですら黄色なのにな……
748デフォルトの名無しさん (ﾜｯﾁｮｲ 1355-QeO8)
垢版 |
2023/03/04(土) 19:09:59.50ID:gYn7OIv60
安倍ちゃんって誰ですか？
2023/03/04(土) 21:07:09.47ID:XAdL2dlO0
vscodeがバグってて何も出来ない
急になんでだろ
2023/03/04(土) 22:43:31.90ID:+svXFhc70
幾何が分からなさすぎてExに逃げてしまった、競プロ脳……
2023/03/04(土) 22:53:55.86ID:XAdL2dlO0
Cは典型でしょうか？
典型だとして何というジャンルになるのでしょうか？数学の典型？
これ知らずに初見で考えてわかる人凄いですね
2023/03/04(土) 22:53:56.10ID:Y7UnjEky0
Fは気合いでO(1)
2023/03/04(土) 22:56:55.74ID:yGMb+RWK0
結局6完
久しぶりの幾何でπをcos(-1)とかしてて時間ロス
2023/03/04(土) 23:00:47.56ID:OQrMsS1R0
Fだけ意味わかんね(´・ω・`)
2023/03/04(土) 23:02:35.00ID:4/7hcXX60
Gみたいな細かい要素はそんなに難しくないけど複合してめんどくさくなってるタイプのDP好き
2023/03/04(土) 23:04:57.32ID:4/7hcXX60
>>751
何か二つの積がN以下みたいな条件の時に、片方は√Nまでしか探索しなくて済むというのはかなり頻出の典型だよ
2023/03/04(土) 23:10:57.18ID:XAdL2dlO0
>>756
ありがとうございます
2023/03/04(土) 23:11:59.93ID:4/7hcXX60
Eは推移閉包の問題だったけど、これに関連する発展的な話題で思い出すのはDilworthの定理かな
他には何かあったっけ
2023/03/04(土) 23:12:16.41ID:53hV4Kxfa
C問題、手元で動かしてみたら明らかに2秒越えてるのにダメ元で提出してみたら500msで通った
2023/03/04(土) 23:13:27.02ID:OQrMsS1R0
A * Bの結果を数え上げておくとN - (A * B)を利用してすぐ答えがでるからそう解いた
2023/03/04(土) 23:14:18.60ID:KuhIh+bI0
Fは受験数学思い出して鬱病だった
2023/03/04(土) 23:23:47.86ID:KuhIh+bI0
今回のDiff体感よりも0.5〜1色低いくらいな気がするんだけどやっぱり環境が整ってきて参加者の実力がインフレしてるのかな
2023/03/04(土) 23:26:28.07ID:XAdL2dlO0
挫折して離れる人がいて
残って実力が伸びる人がいるので
どんどん濃度が濃くなってる気がします

新規はすぐに離脱して強い人しか残らないスパイラルみたいな感じ？
2023/03/05(日) 00:08:17.62ID:KLgsW+HB0
ぶっちゃけそれはあるよね
新規の人が来ないとある色に上がる難易度が上がっていくと思う
ただ、現状のABCだったらまだ時間を十分にかければ特殊な才能がなくてもレートを上げていけるゲームではあるかな？
2023/03/05(日) 00:19:06.70ID:2J+JlFQp0
うわあ～
AB2完で灰色に降格ｗｗ

vscodeバグって40分ロスしたとはいえキツイですね
時間あってもこの問題じゃ解法思いついてないか

まぁARCのラッキーボーナス+60貰ってたのでこれが適正帯ということでしょう
一瞬でも茶色になって茶色の実力があると勘違いした自分が恥ずかしいです

毎回ABC3完でも+5前後なので
たまにC落としてAB2完でガクっと削られることを繰り返すようなペースだと
一進一退で茶色に成れないかもしれない
2023/03/05(日) 00:21:04.48ID:2J+JlFQp0
>>764
灰色→茶色は努力でなんとかなると信じてやってますが
それすら厳しいかもしれないんじゃないかなと思い始めています
2023/03/05(日) 00:29:23.01ID:KLgsW+HB0
そんな卑屈になることはないと思うけど、コーディング環境とかの問題は再発防止して平均的なレートを上げていこう
2023/03/05(日) 00:52:57.39ID:2J+JlFQp0
＞＞再発防止

IntelliSenseが効かなくなって何度再起動しても数分後にエラー吐いてPC暴走気味で意味不明でした
IntelliSenseが効かないだけでコードは書けたのでABはそれで提出しました
その後急にまたIntelliSenseが効いていたのでコンテスト終了まで使って今再起動何度しても大丈夫なのですが
原因不明なので様子見するしかない状態です

＞＞平均的なレートを上げていこう
そうですね
マイペースでもコツコツやるしか無いですね
まずはC問題までを確実に解けるように数をこなすようにします
DPや苦手なものは後回しにして解るものだけやってみます
2023/03/05(日) 12:06:06.58ID:qK/s259X0
最悪に備えてエディタは2つは用意しておくといいかもね
2023/03/05(日) 12:22:19.66ID:W8PCnpO50
端末2つとか回線2つとか家2つとかに拡張できそう
2023/03/05(日) 14:01:29.11ID:Z11rw7p50
体2つもアリ
2023/03/06(月) 02:07:59.12ID:IMTAa66y0
体2つは規約に反しそう
2023/03/06(月) 20:14:35.30ID:GwbNz+dV0
繰り上げり連絡きたけど最高でも6完までの人がToyotaコンの決勝に行ってもいいものかしら
2023/03/06(月) 21:11:51.99ID:pGNY7lCA0
特定しました
2023/03/06(月) 21:23:10.81ID:q41/a1BC0
俺はヴィーガンが諦めるまで肉を食うよ
2023/03/06(月) 22:29:16.06ID:lXUe4Tg6M
決勝イベントって何しに行くの？
2023/03/08(水) 12:06:12.57ID:Pvw6Vf/L0
俺とえっちするんだよね
2023/03/08(水) 12:21:39.73ID:PpYMQDcgM
やっぱオフパコ目的か
2023/03/09(木) 16:51:49.14ID:0rBAUemd0
ホモ祭りってこと？
2023/03/09(木) 18:42:38.65ID:u1SLlFkxr
ホモじゃないんだなァ……
お前がメスになるんだからなぁ
2023/03/11(土) 22:41:50.81ID:lSh5LMLL0
今回いつにも増して知識問題で笑った
特にEとG
2023/03/11(土) 22:42:57.49ID:lSh5LMLL0
というかパフォ予測渋いけど前みたいにバグってるだけだよね？
2023/03/11(土) 22:43:50.50ID:0te2Mpv80
ABCDEG6完
持ってて良かったライブラリ
784デフォルトの名無しさん (ﾜｯﾁｮｲ 0eca-L2/A)
垢版 |
2023/03/11(土) 22:45:15.03ID:OCLTPK230
難しくなりすぎ、３完
2023/03/11(土) 22:45:15.83ID:RFB9Zjn2M
predictorはバグっとるな
2023/03/11(土) 22:46:47.19ID:RFB9Zjn2M
やっぱりMoやるだけだと、かなりの人が解けるようになってるな
2023/03/11(土) 22:55:20.20ID:6tpkFNrCa
正解数見る限りむしろ簡単回では
788デフォルトの名無しさん (ﾜｯﾁｮｲ 0eca-L2/A)
垢版 |
2023/03/11(土) 23:09:18.64ID:OCLTPK230
D,方針はすぐわかったけど色のインデックスつけたグラフを探索して１時間以上通せなかったり罠が・・・
2023/03/11(土) 23:17:12.24ID:21MPESrtM
Dは色いらんのかーい！ｗってところが逆に解きづらい可能性がある
2023/03/12(日) 00:28:02.32ID:JKM4V2Et0
全く使わない入力がある問題を見たのはABC126以来かな
2023/03/12(日) 00:53:45.24ID:5bUKmC3Q0
こどふぉとかだとまあまあ見かける気はする
まあカモフラージュとしては良い案だと思う
2023/03/12(日) 02:58:21.52ID:BK530g0z0
本番ではCをDPだと思い込んで苦戦して結局時間切れのAB2完で-4ポイント
HW左上から右下への全通りの作り方が分からず
DFSとbitとnext聞いたことあるけど本番で実装に使うという発想が湧かないのが痛い
いつまた出題されるかわからないけどこいうものを随時テンプレ化することをみんなやってるのかな

本番後D問題は見てもさっぱり分からないので解説動画でDSUでも解けると聞いたので
自分の提出済みのグラフ関連のコード漁ってたら先週の問題の応用でいけそうと思って
先週のD問題に追加3行の計算とロープの色入力追加だけで解けちゃった

ただ解説見るとあっけなく解けることもあるけど
初見の問題だとまず解法が思いつかないし
何を勉強すれば良いのか分からないのはいつものことで
ひたすら過去問解いてコンテストに参加するしか無いの繰り返しなんだろうな
成長の実感が無い期間がしばらく続きそう
2023/03/12(日) 09:25:04.97ID:+XiJVNUi0
>>792
> DFSとbitとnext聞いたことあるけど本番で実装に使うという発想が湧かないのが痛い

全探索の時はその2つを真っ先に思い浮かべればいい
C問題までは計算量考えない全探索でほぼほぼ行ける

問題をたくさん解くというのはこういうことを学ぶことで別に別にたくさん解かなくても学べる
今日は2つ学んだから成長したぞ
今まで時間内に解けなかったC問題がいくつか解けるようになったはずだ
2023/03/12(日) 10:10:16.92ID:kO4IbZOj0
制約から全探索が間に合うかどうか確認しておくといいよ
実装については類題解いて慣れるしかないと思うけど
2023/03/12(日) 10:36:02.54ID:BK530g0z0
>>793-794
ありがとうございます
このスレにいる方って本当にポジティブな方が多くて励みになります
2023/03/12(日) 11:03:35.64ID:NGnXWmzma
>>794
Cでアップアップしてるやつにそれができないことを知りながら誰でもできるみたいな感じでマウント取るんじゃねえよ寒色のくせに
2023/03/12(日) 11:39:08.26ID:0uSJS7hH0
>>792
今回のC問題みたいなのについてはテンプレ化は難しいと思う

とはいえ、DFSによる全探索は大体どれも似たようなパターンでは書けるから、何個か類題解いてみて自分に合った型を身に付けられるといいかな
2023/03/12(日) 13:20:46.12ID:NGnXWmzma
ChatGPT昨日の問題全部解きやがった
2021年までのデータしかないんじゃなかったのかよ
2023/03/12(日) 15:49:18.88ID:bJsXlPlwM
どこまで行っても補助輪がついてる競プロ界の中でテンプレがどうこう言う話なのかなあ？
800デフォルトの名無しさん (ﾜｯﾁｮｲ f951-S+nL)
垢版 |
2023/03/12(日) 17:15:31.72ID:JeedQz+W0
テンプレというか、この手の移動が「W-1回の右移動とH-1回の下移動」の順列と一対一対応するのが典型では（ABC034-C とか）
2023/03/12(日) 20:06:45.55ID:BK530g0z0
ありがとうございます

>>797
これを機会にDFSに触れてみます

>>800
本質を言語化して頂いて助かります
2023/03/12(日) 23:05:04.03ID:J7t2DN8P0
3完
いつか800点解きたい
2023/03/12(日) 23:14:16.32ID:Gruze9YMp
B問題未証明で適当に通した人多そうだしあまり好きじゃない
誤差とかも嫌だし
2023/03/13(月) 00:42:27.93ID:tAERM5Ax0
DFSで解けるらしいというヒントだけで初見のC問題をDFSで実装して解けたけど4時間半掛かりました
すぐに分からないものを出来るまでやった方が良いみたいなことをどこかで見聞きしたので試してみたけど
もの凄い疲労感とちょっとだけ達成感
さっさと解説ACでどんどん数こなすのとどっちが効率良いんでしょうね
問題やその人の好みってことだと思いますが・・・
2023/03/13(月) 16:05:40.89ID:7mT2rAwv0
解説ACするかは、記憶力に自信があるかじゃないかな
頑張って自力で解いた経験が無いと覚えられないならちゃんと取り組むべきだし、解説を次々開いても一読しただけで暗記できるなら解説ACの方が効率が良い
まぁ解説ACつっても典型要素のエッセンスはちゃんと復習してるけどな

あなたの場合、そもそも解説を読むだけではどこが典型か理解できないみたいだから、ちゃんと問題に取り組む時間を設けないとダメだと思う
2023/03/13(月) 17:01:54.47ID:jAvU5ud0a
明らかに向いてなさそうだが競プロやってる理由はなんなんだ？
807デフォルトの名無しさん (ﾜｯﾁｮｲ ce5b-lsaJ)
垢版 |
2023/03/13(月) 23:46:41.51ID:vLo5AekE0
この界隈、全体的にネット上の立ち回りが下手くそ
特にトッププレーヤー
2023/03/14(火) 00:37:56.19ID:oPoU3rtzM
おぼえると言う意味が分からない


考えられない、理解してないと言うことだろ
809デフォルトの名無しさん (ｱｳｱｳｳｰ Sa89-6iC+)
垢版 |
2023/03/15(水) 10:30:29.06ID:62k5ZXIga
ガイジスレ終了
2023/03/15(水) 11:04:08.82ID:6RV0HXN90
293C、どうやって書いてもREが出ます。
サンプルの2題だけ通ってあとは全部REになります。

何が原因だと思われますか？
他の提出車を見てもREばっかりで
2023/03/15(水) 11:29:42.07ID:cgh9EpJX0
ここが次スレということです
みなさんよろしくお願いいたします
2023/03/15(水) 12:42:04.84ID:S/2xoj/O0
>>810
プログラマーが問題
2023/03/15(水) 12:53:32.24ID:u1R9CLzqr
うんち！w
814デフォルトの名無しさん (ｱｳｱｳｳｰ Sa89-6iC+)
垢版 |
2023/03/15(水) 12:58:17.83ID:rDrD5Ip8a
ここはガイジスレの次スレって聞いたんですけどガイジがいないように見えます
私がファーストガイジになっていいですか？
2023/03/15(水) 13:23:52.74ID:aPY7VYJua
ざわ…ざわ…
2023/03/15(水) 13:41:28.37ID:JhssFxDz0
>>810
サンプル以外全部REってレベルで通らないときは、自分で適当な入力を手で作ったりランダムな入力を生成するプログラムを書いたりしたら手元で再現できる確率が高い
2023/03/15(水) 14:15:10.53ID:ftmGj05c0
>>796
普通にまともなアドバイスじゃね？
2023/03/15(水) 14:22:27.42ID:ASdLGojG0
>>810
HとW間違って配列外参照してないか確認してみるとか
サンプルはH=Wしかないし
2023/03/15(水) 16:56:24.62ID:cgh9EpJX0
次はここけ
2023/03/16(木) 01:34:31.97ID:lxZ//rd7r
なんかあっちヤバい人来ちゃったね
2023/03/16(木) 09:12:30.37ID:oNWKTGjNM
こっちにヤバいひとを集結させよう
2023/03/16(木) 09:54:41.38ID:coFKYGG/0
>>817
これをまともだと思ってるやつがいるあたりこっちも相当ヤバい
2023/03/16(木) 13:14:47.88ID:tTuGCwYP0
制約から全探索が間に合うかどうか確認しておくといいよ
実装については類題解いて慣れるしかないと思うけど

普通にまともじゃね？
これで「この文章は出来て当然だと言わんばかりに煽ってる」って思うか普通？
2023/03/16(木) 13:22:17.64ID:k5zGeUtMa
Cすらできない初心者に言うならどう見ても煽りだろw
2023/03/16(木) 13:28:57.67ID:tTuGCwYP0
C問題辺りからループの計算量を把握する必要がある問題が出始めるのでC問題で苦戦している層に対してのアドバイスとして1文目はまぁ妥当
実装が難しいって言う書き込みに対して実装はいろんな問題をやりながら慣れるしかないって回答してるから2文目は妥当
やっぱ普通じゃね？
2023/03/16(木) 13:30:51.01ID:tTuGCwYP0
Cでアップアップしてるやつにそれができないことを知りながら誰でもできるみたいな感じでマウント取るんじゃねえよ寒色のくせに

プログラマーが問題

つかこいつのほうが煽りカスだろ
ブラウザ一致してるから自演だし
2023/03/16(木) 13:32:57.23ID:7egMyHWVr
わかるなぁ
2023/03/16(木) 13:34:29.87ID:k5zGeUtMa
C問題ができないってことは灰色だぞ？
それに計算量ができて当然みたいな言い方を妥当と言い張るのはどう誰が見ても煽りだよw
意図的に言ってるやつに何言っても無駄だがな
アドバイスするなら見積もり方くらい教えてやれや
寒色の癖にマウント取ってんじゃねえよ
2023/03/16(木) 13:36:47.05ID:tTuGCwYP0
当然って言い方そもそもしてないだろ...
〇〇したほうがいいよ(〇〇出来て当然って読み取るのはおかしいでしょ)
2023/03/16(木) 13:37:17.11ID:tTuGCwYP0
当然って言い方そもそもしてないだろ...
〇〇したほうがいいよ(〇〇出来て当然)って読み取るのはおかしいでしょ
カッコの位置ミスった🤗
2023/03/16(木) 13:46:38.50ID:tTuGCwYP0
レスなし、っと
また勝っちゃたか
敗北を知りたい
2023/03/16(木) 14:11:11.28ID:5yHkm1Rj0
マウント、とか寒色のくせに、とかは大抵自己紹介だから、つまり煽りカスなんでNGしておくと良いぞ
……と思ったがレスバが最初から目的っぽいな、5ch内なら氏名特定攻撃も来ないだろうし
2023/03/16(木) 14:35:56.62ID:k5zGeUtMa
アオラーの本性出てるぞw
2023/03/16(木) 14:51:33.30ID:RuPNdDms0
効いてて草
2023/03/16(木) 14:53:29.11ID:coFKYGG/0
効きすぎて笑う
いくら言葉を繕って逃げ道を用意しても本性が隠せないやつはすぐ尻尾出すから意味ないぞw
2023/03/16(木) 15:49:35.67ID:tTuGCwYP0
自演下手だなぁ
2023/03/16(木) 16:13:33.78ID:U2dnMLSBa
やっぱこれくらい殺伐としてないと居心地悪いわ
ワッチョイ付きだからって妙に行儀良かったからな
2023/03/16(木) 16:24:13.65ID:UPEBZhkEr
IP透視草
2023/03/16(木) 17:25:03.67ID:/7JPrwhgr
つーか携帯回線と家回線切り替えたくらいで自演に望むなよ
家回線chrome+携帯回線mateってかんじで回線とブラウザ両方変えたほうが自演通るぞ
2023/03/16(木) 17:25:43.32ID:tTuGCwYP0
>>839
これ俺ね
2023/03/16(木) 17:28:48.86ID:coFKYGG/0
一度に出てくるから自演とバレバレなの笑うわw
2023/03/16(木) 17:28:58.10ID:tTuGCwYP0
ﾜｯﾁｮｲ←回線会社固有、回線ごとに変化しない
初めの2文字←携帯だとあんまり変わらない
次の2文字←固定回線だとあんまり変わらない
最後の4文字←ブラウザと端末の種類による、過疎スレだとここが一致=自演
2023/03/16(木) 17:29:16.96ID:tTuGCwYP0
だから末尾Aoo2で自演しないほうがいいぞ
2023/03/16(木) 17:37:02.07ID:tTuGCwYP0
あとsoftetherを使うと5-ipくらい併用できるからもっと自演できるぞ😉
今回は俺の勝ちだったがお前がレスバレベルを上げたらまた戦おう
2023/03/16(木) 17:45:05.45ID:coFKYGG/0
自演の仕方をドヤ顔で講義してるのウケるw
2023/03/16(木) 17:45:53.25ID:U971uBUdp
ﾜｯﾁｮｲの仕組みすら知らないのを見るにどうせ普段から例のID無しスレで自演してるような奴だろうし相手にしなくても良いよ
2023/03/16(木) 17:55:45.50ID:coFKYGG/0
もしかしてお前の言う自演って、wi-fi使える場所と使えない場所でワッチョイ違うこと言ってんの？

自演慣れしてることを自白していくスタイル笑うw
2023/03/16(木) 18:01:14.39ID:tTuGCwYP0
まぁそれはどうでもいいとして>>830に反論くれや
849デフォルトの名無しさん (ﾜｯﾁｮｲ 4ed7-6iC+)
垢版 |
2023/03/16(木) 18:02:49.01ID:xrZiXpyi0
効きすぎだろ
2023/03/16(木) 18:37:50.10ID:coFKYGG/0
>>848
自演君何言ってんのw
お前がアオラーだってことは証明されたじゃん
まだ言い逃れできると思ってんのヤバくね？w
2023/03/16(木) 18:38:13.08ID:dGJRHg7p0
俺が馬鹿になればなるほどみんな理知的で輝いてるように見える
2023/03/16(木) 18:45:00.58ID:Vl48IBXt0
なにがしたいの
2023/03/16(木) 19:52:56.73ID:tTuGCwYP0
アオラーっていう謎造語言い出して話がどんどん自演と煽りの方向に行ってるけど俺の主張は最初から794は悪意的に解釈されないってだけだけど
2023/03/16(木) 20:24:05.49ID:U2dnMLSBa
マジで効いてて草
2023/03/16(木) 20:28:10.90ID:BFfi9igq0
次スレはIPありだな
2023/03/16(木) 21:48:24.70ID:o9puvlr9a
喧嘩はやめようね🤜🤛
2023/03/16(木) 22:36:16.57ID:coFKYGG/0
大暴れだなw
2023/03/17(金) 17:20:21.67ID:3E0jHgrBM
ア辞典やデ辞典もテンプレに追加してもいいかもな
https://github.com/noshi91/algorithm-encyclopedia
https://scrapbox.io/data-structures/
2023/03/17(金) 17:21:15.88ID:3E0jHgrBM
デの方の名前はデwikiだった

ア辞典の本体のリンク
https://noshi91.github.io/algorithm-encyclopedia/
2023/03/17(金) 17:46:19.41ID:1LwxApLT0
ガイジはこっちにこいよ
びびってんのか？
2023/03/17(金) 19:57:33.86ID:lBJjgNhe0
ガイガイガイガイガイガイガイガイガイガイガイガイ
おはようございます😃
2023/03/17(金) 19:59:48.30ID:UJ/qBGEar
画像作り直せや！
863デフォルトの名無しさん (ﾜｯﾁｮｲ faad-OF0a)
垢版 |
2023/03/17(金) 21:49:57.99ID:v6DwInoP0
早稲田大学　Twitter名さかえまな　atcoder 名　na_kombu 真中紗枝
教育学部　25歳
2023/03/17(金) 21:51:34.42ID:0+MSGGBcr
超えちゃいけないライン考えろよ
2023/03/17(金) 22:15:37.75ID:lBJjgNhe0
それデマだろ？
2023/03/17(金) 22:17:43.22ID:1LwxApLT0
デマかどうかはガイジが決めること
2023/03/17(金) 23:19:19.63ID:at7fQjzyM
こっちで全部やれよガイジどもめ
2023/03/17(金) 23:28:07.44ID:LfP8zWCca
ググッてもなんも出てこないな
869デフォルトの名無しさん (ﾜｯﾁｮｲ 13ad-gGwk)
垢版 |
2023/03/18(土) 02:40:41.68ID:cnAFfKbu0
早稲田大学　Twitter名さかえまな　atcoder 名　na_kombu 真中紗枝
教育学部　25歳
2023/03/18(土) 07:44:40.74ID:Htw9fZ/00
競プロスレなんてレートが高い方が正義だから、レスバで勝ちたかったらレートの高さを証明すれば終わりなんだよな
まぁ灰色アオラーには無理だろうけど
2023/03/18(土) 09:16:13.01ID:Udgld9Z70
会場のSSID、4.2Ghzと書き間違えてるのを二重線で消して2.4Ghzに書き直してて草
印刷し直さないのかい
2023/03/18(土) 09:43:38.07ID:TCHG5/U6p
イベント辞退したけどイベントって何やるんだろう？
2023/03/18(土) 09:56:26.15ID:mfH5XsN2a
せっかくタダで東京に行けるから行ってみる
2023/03/18(土) 18:52:57.45ID:w8aA8ydna
数百人もいるのに無限に飲み物食べ物が補充されるのが太っ腹でいいね
2023/03/18(土) 18:55:30.18ID:RydViEgTp
競プロやってる知り合いもいないしイベントも興味ないから辞退したけど飯だけ食いに行けば良かったか
2023/03/19(日) 11:55:56.46ID:iFCAbZGm0
ちいかわガイジもこっちのスレにこいよ
2023/03/19(日) 16:13:19.25ID:iFCAbZGm0
電通ガイジもこっちこい
2023/03/19(日) 22:41:25.76ID:7B5cvRcC0
全然だめー
よく東京呼んでもらえたな
2023/03/19(日) 22:42:50.25ID:y82GOv10p
今回Gまで簡単というか典型めで良かったけどオイラーツアーのライブラリ持ってなくて一から書いてたら橙パフォ逃しちゃった
というかGこんなに解かれるもんなんだインフレしすぎ
2023/03/19(日) 22:46:49.93ID:m7o/mGJn0
Gはかなり既出感の強い問題だからね
vaidation用の問題みたい
2023/03/19(日) 22:47:42.92ID:m7o/mGJn0
Ex、指数時間アルゴリズムのスライドに何か載ってないか探しに行ったけど、特に収穫はなく
2023/03/19(日) 22:55:37.60ID:y82GOv10p
Fは例の食塩水の問題が結構印象に残ってたからすぐ方針に辿り着けたけどABCだとやっぱりほぼ既出問題ばかりになるから精進が大切だな
2023/03/19(日) 23:29:06.01ID:7B5cvRcC0
Eでバグりまくって見てなかったFやったら5分で解けた…
884デフォルトの名無しさん (ﾜｯﾁｮｲ d98c-d7tS)
垢版 |
2023/03/20(月) 00:08:10.86ID:gKXpc2uz0
Eバクりまくって4完。カス
885デフォルトの名無しさん (ﾜｯﾁｮｲ 9bca-aXiD)
垢版 |
2023/03/20(月) 00:29:14.29ID:1RFbVmDh0
multisetを使うDがレート380とか信じられないんだけど・・・
2023/03/20(月) 00:32:44.72ID:g1SKJTkh0
>>885
multiset使わなくても解けるよ
ACしたほとんどの人使ってないんじゃない？
2023/03/20(月) 01:55:57.10ID:68Uj2Hdyp
Eまでほぼ愚直に実装する問題だったのはだいぶ珍しい気がする
Eみたいな問題はバグが怖いからあまり好きじゃないけど
2023/03/20(月) 02:28:36.69ID:5BGtS5x50
WA出しまくりの6完ですわあ...(´・ω・`)クエリ処理で前も同じミスしたのよね
2023/03/20(月) 12:46:23.78ID:zKz8nZXUr
もともと寒色になんの価値も無いのでGPT使われようがなんの問題もないね
2023/03/20(月) 16:04:08.72ID:xeR+NXGlM
GPT4で5完水パフォか
これは使ってる人が水だからあんま意味ないけど
茶ぐらいの人が使ってもパフォ上がるんだろうか
2023/03/20(月) 16:08:18.71ID:BTFdTO690
https://qiita.com/autotaker1984/items/2929937cd1fea6137d1f
AtCoder終了のお知らせ
前回は質問を工夫して何度かやり取りと手直ししたら3.5でも一時間で7完だったからお前らよりよほど優秀
2023/03/20(月) 16:11:40.54ID:+nyIRXU90
ガイジスレのみんなもこっちにおいで
2023/03/20(月) 16:17:14.20ID:5BGtS5x50
優先度付きキューとか今日日灰色でも標準装備だろうし余裕でAIに指示出せるな
AtCoder崩壊近しなのか？(´・ω・`)
2023/03/20(月) 16:19:36.96ID:hAgeSbvHp
寒色diff程度の簡単めな問題なら解法分かってる状態で質問繰り返してしかも手直しまでしたら解けるに決まってるんだよな
解法が分かってない状態でも自分よりも高いパフォが出せるようになるかが問題
2023/03/20(月) 16:20:39.56ID:+nyIRXU90
GCJとTCOが終わったり、ABCで大半のユーザがAIに負けるようになってもまだみんながんばってね
2023/03/20(月) 16:21:44.91ID:AhWhyU3m0
灰とか茶の人が実際に使ってみたレポートが欲しいんだけど、自分がガチでやるより良い成績が出る可能性があるとなるとなかなか使いたくないのかな
2023/03/20(月) 16:36:48.13ID:AhWhyU3m0
ARCのA問題も解けるのかな
2023/03/20(月) 16:38:45.12ID:272mASSPp
AGCのA安定して解けるようになったらヤバいけど考察不得意そうだからまだ大丈夫そう
ABCのド典型問はどんどん解かれそうだけど
2023/03/20(月) 17:04:45.56ID:3TQ5vmXOM
GPT4もそのうちAPI公開されるし
誰かが完全自動化ツール作って放流したら終了だね
2023/03/20(月) 17:26:39.70ID:S2Sybo+q0
逆に機能のGなんかは一発で解けてもおかしくない気がするけど、意外とまだ典型習熟度高くないね
2023/03/20(月) 19:49:00.37ID:VHv5ydSaa
>>894
なんで解けるに決まってんだよw
問題読ませただけで「ここではMoのアルゴリズムが使えます」とか「答えを固定して二分探索します」なんて言うAI他にあるか？
2023/03/20(月) 20:03:11.57ID:VSzCgxP6p
>>901
そうだから質問を繰り返してAIを導く必要があって、導き方を既に知ってるなら最早AIじゃなくて人間が解いてるのと変わらないのではって話をしてるんだけどどういうツッコミ？
2023/03/20(月) 20:05:57.80ID:VHv5ydSaa
>>902
日本語読めないのか？
AIが問題解決に最適なアルゴリズムを提案してんだよ
人間じゃなくてだな
2023/03/20(月) 20:13:25.50ID:XjAZ8zEkp
>>903
上の方で貼られた記事のE問題までの話をしてんのね
社長のchatGPT縛り配信の話かと思った
2023/03/20(月) 20:17:33.98ID:VHv5ydSaa
>>904
何を言ってるんだ
7完達成しやがったという話を先週ここに書いたんだよ
今週5完の記事が出たから蒸し返した
2023/03/20(月) 20:19:39.32ID:VHv5ydSaa
蒸し返したらそんなの当たり前とか言うトンチキが出てきたから呆れてるとこだ
当たり前のわけねえだろ
2023/03/20(月) 20:27:08.93ID:JGpTxGZup
>>906
当たり前っていうのはAIを適切な解き方に誘導したらそれに沿って解いてくれるのは当たり前って話をしていたつもりだった(3.5の時はこうしないと簡単な問題以外は解けなかった)

chatGPTがバージョン4になった今どういう風に解いてくれるのかは把握してないし先週のABCで7完したという話も初耳
2023/03/20(月) 20:44:01.94ID:AhWhyU3m0
Moのアルゴリズム提案してくれたやつは問題を読ませた“だけ“ではなくて質問である程度誘導してたとは思う
（もちろんそれで提案してくれるのはめちゃくちゃ凄いが）
2023/03/20(月) 20:46:48.04ID:BTFdTO690
>>907
まだ誘導とか言ってるのか
100回読むか小学校からやり直せよ
2023/03/20(月) 20:58:26.01ID:enr3USaTr
すまん、GPT4より弱いやつおる？w
2023/03/20(月) 21:06:12.87ID:S2Sybo+q0
レスバしたいだけのｱｳｱｳｳｰの人、結構みっともないからやめた方がいいよ
2023/03/20(月) 21:21:05.85ID:6NGESZufa
ほんと、そういうくだらないのはツイッターでやれよな
2023/03/20(月) 22:00:28.84ID:p6MhJ7dBa
お前いつも論破されてそれだな
2023/03/20(月) 22:45:45.31ID:g4VcAGMh0
すまん
初心者なんだがIQが低すぎてこの問題が解けない
一つだけクリア出来ないテストケースがあるみたい

N以下の自然数でXの倍数またはYの倍数であるものはいくつあるか？

入力
N X Y
制約
1≦N≦10^6
1≦X＜Y≦10^6

コード

#include<bits/stdc++.h>
using namespace std;

int main() {
long long n,x,y;
cin>>n>>x>>y;
if(y%x==0) cout<<n/x<<endl;
else cout<<n/x+n/y-n/(x*y)<<endl;
}
2023/03/20(月) 22:46:24.96ID:g4VcAGMh0
誰かどの辺が間違ってるか教えて
なんでACできないんだろ
2023/03/20(月) 22:49:06.83ID:g4VcAGMh0
お願いします
2023/03/20(月) 22:50:00.28ID:g4VcAGMh0
For文書いたら出来たけどなんか釈然としないよね
2023/03/20(月) 22:52:12.36ID:/KHjyqT50
ヒント：最小公倍数
2023/03/20(月) 22:54:12.33ID:6NGESZufa
最後x*yじゃなくlcmでどうや？
2023/03/20(月) 22:55:07.63ID:6aqreXsg0
総当たりして誤るテストケースを自分で見つけるスキルを身につけることも重要
2023/03/20(月) 22:56:59.35ID:g4VcAGMh0
ありがとうございます
たしかに、最小公倍数でいいですね
IQがゴミすぎるんで競プロ止めます
2023/03/20(月) 22:57:42.29ID:g4VcAGMh0
止める→辞める
2023/03/20(月) 22:58:49.74ID:g4VcAGMh0
止めるでいいか
2023/03/20(月) 23:52:08.09ID:0oNeBZFb0
コドフォ…
2023/03/20(月) 23:53:18.04ID:Lo04kl5hp
コンテスト開始前に突如延期は酷いやサーバーの問題だから仕方ないけど
926デフォルトの名無しさん (ﾜｯﾁｮｲ 9bca-aXiD)
垢版 |
2023/03/21(火) 01:06:39.53ID:WiAWCQDG0
おそらくGTPにヒューリスティックを除くatcoder的なスキルはほとんど使われていない、使われてるのはニューラルネット、内積、最適化、強化学習など。何故か整数ばかりのパズル最適化は見当違いも良い所。
競プロは役に立たない。
2023/03/21(火) 01:20:29.80ID:W35aCdkdp
役に立つと思ってやるもんじゃないって既に無限回言われてるだろ何を今更
2023/03/21(火) 10:22:30.40ID:ayGaCmzS0
AtCoderJobsのランクがほぼ無意味になるな
2023/03/21(火) 11:38:58.42ID:IeqWtZWC0
何も変わってないじゃん
2023/03/21(火) 12:36:35.41ID:eYzPE6ipM
>>926
> ニューラルネット、内積、最適化、強化学習

この並列笑えるな、内積はセンスある
2023/03/21(火) 13:35:42.22ID:BiuFHUvxp
競プロ以前に高校数学すらまともに勉強してなかったんだろうな
AI開発に全く従事してないような奴の妄言
932デフォルトの名無しさん (ﾜｯﾁｮｲ 9bca-aXiD)
垢版 |
2023/03/21(火) 13:55:08.65ID:WiAWCQDG0
>>930
トランスフォーマーの核なので強調してみたのじゃｗ

>>931
DSだけどどう温かい目で見てもABCの問題の大半は役に立たない。ガチ。
2023/03/21(火) 13:59:58.54ID:3NbTT7XB0
お前がディープステートだったのか
ついに正体を表したな
2023/03/21(火) 14:35:19.64ID:2zmgamhJ0
内積でqueryとkeyのある種の類似度を計算して重みとして利用するのはそうなんだけど、まず磨くようなスキルではないのではないかという
離散最適化が主なのはそうだけど、実質的には連続緩和して解くような問題もままあるので、連続最適化をしてないとも言えないし
935デフォルトの名無しさん (ｱｳｱｳｳｰ Sa95-lF85)
垢版 |
2023/03/21(火) 15:06:25.17ID:icU0z8mba
Winnyの金子ですね判ります
2023/03/21(火) 17:35:53.57ID:1DnfyNWD0
問題
N 枚のカードが横一列に並べられています。左からi 番目のカードには整数Ai​が書かれています。
カードの中からいくつかを選んで、合計がちょうどS となるようにする方法はありますか。
制約
1≦N≦60
1≦Ai,S≦10000
入力は全て整数
入力
N S
A1…AN
2023/03/21(火) 17:44:43.69ID:1DnfyNWD0
質問です
これって動的計画法を使う問題ですよね
dp[i][j]をiまでのカードのなかで合計がjとなるようなカードの組み合わせが存在するかと考えても上手くいかないです
ほとんどのテストケースではACが取れるので全く検討違いというわけではないと思うのですが、有識者の目から見て間違ってる部分はありますか？
#include<bits/stdc++.h>
using namespace std;

using ll = long long ;
using bl = bool ;

#define Rep(i,a,b) for(ll i=a;i<=b;i++)

int main() {
ll n,s,A[69];
bl dp[69][10009];
cin>>n>>s;
Rep(i,1,n) cin>>A[i];
dp[0][0]=true;
Rep(i,1,s){
dp[0][i]=false;
}
Rep(i,1,n){
Rep(j,0,s){
if(dp[i-1][j]==true) dp[i][j]=true;
elif(dp[i-1][j-A[i]]==true) dp[i][j]=true;
else dp[i][j]=false;
}
}
if(dp[n][s]==true) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
2023/03/21(火) 17:46:15.85ID:1DnfyNWD0
自分でテストケースを作成して色々とやって見たのですが上手くいかないです
2023/03/21(火) 17:49:03.50ID:8HipxHLW0
>>937
全然ちゃんと確認してないんだけどj-A[i]で範囲外参照してそう

環境にもよるけど、　#define _GLIBCXX_DEBUG を入れると範囲外参照関連のデバッグはしてくれるから便利だよ(実行時間が遅くなる場合もあるから提出する時は外れるようにすると良い)

まあこういう遷移はめちゃくちゃ良くあるし慣れたらデバッグしないでも殆どミスらなくなると思う
2023/03/21(火) 17:54:56.33ID:wykVgs8rr
>>937
elifが間違ってる
2023/03/21(火) 17:59:28.32ID:1DnfyNWD0
>>939
ありがとうございます。
Ai＞jであるときとそうでないときで場合分けしたら上手く出来ました。
2023/03/21(火) 18:01:08.70ID:1DnfyNWD0
>>940
ありがとうございます
elifの部分もまちがえていましたか
2023/03/21(火) 18:04:55.14ID:1DnfyNWD0
配列外参照の仕様に関してはまだちゃんと理解していませんが、939のレスをヒントにして解決することが出来ました。
2023/03/21(火) 18:06:38.67ID:2/Nqgm+N0
j-A[i] < 0 にならない？
2023/03/21(火) 18:07:25.41ID:2/Nqgm+N0
寝てたら解決しとる
2023/03/22(水) 14:54:15.97ID:XBvF4hES0
質問
N個の正整数の最小公倍数を求める問題で分からない部分がありました。

コード1ではACが取れなかったのですが、コード2に変えてみたところACを取ることが出来ました。
数学的にはコード1もコード2も違いがないと思うのですが、何がいけなかったのでしょう。
頭を捻っても全く分かりません。
2023/03/22(水) 14:54:42.44ID:XBvF4hES0
コード1
#include<bits/stdc++.h>
using namespace std;

ll Gcd(ll a,ll b){
while(a>=1 && b>=1){
if(a>b) a=a%b;
else b=b%a;
}
if(a!=0) return a;
return b;
}
int main() {
ll n,A[100009],g,l;
cin>>n;
Rep(i,1,n) cin>>A[i];
l=A[1];
Rep(i,2,n){
g=Gcd(l,A[i]);
l=(l*A[i])/g; ←変えたところ
}
cout<<l<<endl;
}
2023/03/22(水) 14:55:09.27ID:XBvF4hES0
コード2
#include<bits/stdc++.h>
using namespace std;

ll Gcd(ll a,ll b){
while(a>=1 && b>=1){
if(a>b) a=a%b;
else b=b%a;
}
if(a!=0) return a;
return b;
}
int main() {
ll n,A[100009],g,l;
cin>>n;
Rep(i,1,n) cin>>A[i];
l=A[1];
Rep(i,2,n){
g=Gcd(l,A[i]);
l=(l/g)*A[i]; ←変えたところ
}
cout<<l<<endl;
}
2023/03/22(水) 14:56:01.64ID:XBvF4hES0
行数制限のためテンプレートは省いております。
2023/03/22(水) 15:11:18.73ID:9X0hpeOca
多分問題文の省略したところに原因が書いてある
2023/03/22(水) 15:20:25.39ID:9X0hpeOca
次スレ

競技プログラミング総合スレ 66
https://mevius.5ch.net/test/read.cgi/tech/1679465982/
2023/03/22(水) 15:52:00.88ID:AvapjKF+d
l*A[i]がlong longの最大値を超えてオーバーフローするのでは
2023/03/22(水) 15:58:55.16ID:lb80FTnL0
今度からChatGPTに聞けよ
質問丸々手直しせずコピペして聞いたらこんなふうに答えたぞ

コード1とコード2は、最小公倍数を求めるアルゴリズムとしては等価です。しかし、2つのコードは演算の順序が異なります。

コード1では、(l*A[i])/g という式を用いて最小公倍数を更新しています。これは、 l と A[i] の積を g で割った商を最小公倍数としていることを意味します。

一方、コード2では、 (l/g)*A[i] という式を用いて最小公倍数を更新しています。これは、l と A[i] の積を g で割った余りを最小公倍数に加えたものとしています。この操作により、 l と A[i] の積が l と A[i] の最小公倍数になるように調整されています。

なぜコード2がコード1よりも正確であるかは、データ型の問題に関係しています。コード1では、(l*A[i])/g という式を用いることで、最小公倍数が ll 型で表現可能な範囲を超えてしまう可能性があります。一方、コード2では、 (l/g)*A[i] という式を用いることで、最小公倍数が ll 型で表現可能な範囲内に収まるようになっています。つまり、コード2は、最小公倍数が大きな値になる場合でも正確に計算できるようになっているということです。

以上のような理由から、コード2がより優れた実装方法と言えます。
2023/03/22(水) 16:10:47.83ID:psQ7vQwG0
別に元々質問が多くて困っているようなスレではないし、ここで聞く分には構わないと思うけど、ChatGPTの性能すごいね
ただ、誤ったことも自信満々に言うから、まだまだ初学者向けのサービスではないと思う
2023/03/22(水) 16:14:44.26ID:lb80FTnL0
ここで聞いたら「省略したところに原因が書いてある」と言うやつがいるから書いたんだよ
原因は書いてないな
書いてあるのは制約だ
2023/03/22(水) 16:18:21.55ID:9X0hpeOca
制約が原因やん
2023/03/22(水) 16:23:05.26ID:lb80FTnL0
ちなみにbingで「N個の正整数の最小公倍数を求める問題はAtCoderのどれ？」と聞いて返ってきたのが次の返事

AtCoderの「数学とアルゴリズム」コンテストにある「017 - Least Common Multiple of N Integers」¹が、N個の正の整数A_1, A_2, ..., A_Nの最小公倍数を求める問題です。制約は、2 ≤ N ≤ 10^5, 2 ≤ A_i ≤ 10^18で、問題の答えは10^18以下です。¹

この問題は、AtCoderの「数学とアルゴリズム」コンテストにあるもので、N個の正の整数A_1, A_2, ..., A_Nの最小公倍数を求める問題です。¹¹:[AtCoder](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_q)

ソース: Bing との会話 2023/3/22(1) 017 - Least Common Multiple of N Integers. https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_q アクセス日時 2023/3/22.
(2) AtCoder 版！マスター・オブ・整数 (素因数分解編) - Qiita. https://qiita.com/drken/items/a14e9af0ca2d857dad23 アクセス日時 2023/3/22.
(3) AtCoder 版！マスター・オブ・整数 (最大公約数編) - Qiita. https://qiita.com/drken/items/0c88a37eec520f82b788
2023/03/22(水) 16:23:49.71ID:lb80FTnL0
>>956
制約は原因じゃないぞ
むしろ制約があるためllに収まるから真逆だ
2023/03/22(水) 16:31:30.64ID:9X0hpeOca
口論したいわけじゃないんだが
制約が原因という表現で別に間違ってないやろ
2023/03/22(水) 17:23:43.33ID:XBvF4hES0
>>952
>>953
ありがとうございます
理解出来ました
次からはchatgtpに質問して解決できなかったらここで質問します
2023/03/22(水) 17:34:10.54ID:lb80FTnL0
>>959
間違ってる
電車が来てる時に線路内に入ってはいけないという制約があるとする
それを見ずアホが線路内に入って死んだとする
そいつが死んだ原因は制約か？
違うだろ

この質問の場合も制約があるから間違ったんじゃなく、制約がなくても間違ったんだぞ
10^9までの自然数という制約が無かった場合は条件分岐が必要になるがあるためにそれはしなくていい
制約は問題を簡単にしてるだけで難しくはしてない
2023/03/22(水) 17:39:14.74ID:+5G5XKDn0
その議論はいったいなんの意味があるの
2023/03/22(水) 17:46:21.59ID:9X0hpeOca
制約次第では上のコードでもあってるんだから制約が原因だろ
まあほんとに意味のないやり取りなんでこれ以上は相手しないが
2023/03/22(水) 17:59:23.68ID:lb80FTnL0
日本語わかんないやつはChatGPTより下だぞ
議論じゃなくお前の間違いを教えてやってんだから口答えすんな
2023/03/22(水) 18:07:59.02ID:lb80FTnL0
ChatGPTはお前らより賢いから正しく言葉を理解して正しく答えたぞw

成約を見ないことで不正解になった場合、それは成約が原因と言える？

制約を無視してしまったことによって誤った結果が生じた場合、それは制約ではなく主にあなた自身が原因です。制約は、現実的な制限を示すものであり、それらを考慮しないことは、問題を引き起こす可能性があるためです。ただし、制約が明確でなく、十分に説明されていなかった場合は、誤解が生じる可能性があります。その場合、制約を理解しようと努力する必要があります。結局のところ、誤りを修正するためには、問題を引き起こす可能性のある要因を正確に特定し、それを修正する必要があります。
2023/03/22(水) 18:18:52.57ID:2usK+X1Z0
こっちは自分のことをガイジだと認識してないガイジが湧くから大変だねえ
2023/03/22(水) 18:42:32.05ID:lb80FTnL0
お前いつも論破されていつもそれだなw
2023/03/22(水) 18:47:43.32ID:lb80FTnL0
自分が正しいと思ってる間は無茶苦茶な強弁するのに証拠を突きつけられたら自演して人格攻撃に移りなおかつ自演のやり方の講義までするというガイジはいつになったら自分をガイジと認識できるんだ？w
2023/03/22(水) 19:16:24.27ID:AM4tOKKV0
効いてて草
2023/03/22(水) 19:28:06.30ID:I3ioWv5uM
制約上オーバーフローしうることがWAの原因なんだから、制約も、その制約によってオーバーフローするようなコードを書いたことも、それぞれ原因と言っても別にいいだろ
マジでしょうもねえ…
2023/03/22(水) 19:39:59.04ID:FZyO6fDta
アホなのか？
回答の制約じゃなく質問の制約だそ？
原因はそれを考慮しなかったことに決まってんじゃんw
日本語読めないのかよ
ChatGPTですら読めるのにw
972デフォルトの名無しさん (ｱｳｱｳｳｰ Sa95-puZl)
垢版 |
2023/03/22(水) 20:09:59.70ID:B0eWQ6KXa
ほんとに何言ってるのかわからんわ
自分の中では理屈が通ってるんだろうけどどう通ってるのか想像することさえ難しい
2023/03/22(水) 20:11:09.38ID:FZyO6fDta
何言ってるのかわからんのは自分の頭が悪いからと早くきづけるようになれるよう祈ってるよ
わかんなきゃChapGPTに聞け
正確に理解してるから
2023/03/22(水) 20:11:39.38ID:FZyO6fDta
まあ要するにお前の言語能力は原始的なAI以下ということだ
2023/03/22(水) 20:33:08.15ID:RXktniz50
ガイジスレはひとつだけにしてくれないか？
2023/03/22(水) 21:28:24.75ID:AM4tOKKV0
みんな集合だ
2023/03/23(木) 09:08:18.69ID:lPGuvOFY0
読解力でAI未満てそれ何ならAIに勝てるの？
もしかして数学で勝てるつもりなのか？
2023/03/23(木) 10:15:35.12ID:jVJKu0via
https://qiita.com/uynet/items/e700a4adf5263e4c1904
ChatGPT一人でレスバする
2023/03/23(木) 13:17:46.25ID:WdGFfLtNa
暴れてる奴もChatGPTなんだ怒らないでやってくれ
2023/03/23(木) 14:16:50.21ID:Z5yFziEVa
そんな賢くないだろw
暴れてるやつは日本語ろくに読めないんだからw
981デフォルトの名無しさん (ﾜｯﾁｮｲ c95f-5jEH)
垢版 |
2023/03/23(木) 23:22:59.72ID:Ao+X9Xng0
日本語の言語能力が低く日本人にとってはありがいんだろうな。
2023/03/24(金) 16:34:03.18ID:uNFSm4wfa
チョクダイが焦ってるけどAIの流れとまらんだろ
上流と趣味以外はオワコン
983デフォルトの名無しさん (ﾜｯﾁｮｲ 9bca-aXiD)
垢版 |
2023/03/24(金) 20:08:26.11ID:YL1QOUou0
コーディングテストとしてjobsに関係ある層がほぼ消えるワケじゃからのぉ、ワシもrated参加はやめるのじゃ
2023/03/24(金) 20:21:20.15ID:ZgVZm4b/0
>>976
集合の集合は集合でしょうか？
2023/03/24(金) 20:38:08.20ID:b1BDfC7u0
集合でラッセルのパラドックスを考えるガイジも集合しろ
2023/03/24(金) 23:20:35.66ID:vIsectOc0
公式が出来るって言ったらそれはもう終わりじゃん
2023/03/25(土) 02:10:10.73ID:pc8UC5Ad0
教プロはもうおしまいです
GCJとTopCoder Openという最も有名な最強の競プロerが競う大会は終了です
ABCもChat AIに無双されます
初心者も上級者も楽しめない競技になります
2023/03/25(土) 05:29:06.97ID:DJDWvsTV0
ちょくだいの最近の投稿見ると焦りが隠しきれてないな
まぁ絵師みたいなもんか
2023/03/25(土) 10:48:21.84ID:qiY7Z9Qp0
ライト層はAIで良いじゃんってなるから競技人口増えなそう
990デフォルトの名無しさん (ﾜｯﾁｮｲ 86ca-SHnl)
垢版 |
2023/03/25(土) 12:29:02.91ID:90xyxOUe0
ボケ防止としてはかなり有用じゃ、コンテストの体がないとやる気がせん
2023/03/25(土) 16:26:46.80ID:sftOMQ21r
ゲートボールの代わりに競プロを普及させよう
2023/03/25(土) 17:16:42.74ID:pc8UC5Ad0
老人ってドーパミンがあんま出ないんじゃない？
だから競技にする必要ないんじゃね
数独問題集みたいにモクモクとやらせれば十分だろ
2023/03/25(土) 19:54:56.57ID:OgnUV7oza
歳取るとレート下がる一方になるし普通は辞める
2023/03/25(土) 22:42:00.12ID:4uRItVdp0
A～E5完
Dで方針間違えすぎてGまで取りかかれず
2023/03/25(土) 22:42:21.94ID:lg//0IqP0
Eのサンプル3が一生合わなかったのなんでだろう
2023/03/25(土) 22:44:53.55ID:J/KfDX0zM
Eそんなに難しいか？と思ったけど、確かに微妙に典型度低いかもしれんな
2023/03/25(土) 22:53:36.06ID:azcz0A/s0
崖すごそう
TOYOTAコン超えてそう
998デフォルトの名無しさん (ﾜｯﾁｮｲ 86ca-SHnl)
垢版 |
2023/03/25(土) 23:02:02.23ID:90xyxOUe0
3000人も解けてるけどこのD相当難しい、GTP4も解けてなかったし
2023/03/25(土) 23:09:47.69ID:lg//0IqP0
B4乗ループ最初は思いつかなくて面倒そうだなって思ってchatGPTに投げたら全然違うプログラム書いてきてキレてた
2023/03/25(土) 23:11:23.49ID:oNXBC9Tu0
>>998
同じくDで爆死。数字ごとのパリティまでは
気がついたのだが、長さNのビットベクトル
を10個作ってなんとかしようとしてしまった。
縦と横を入れ換える頭の柔軟性がなかった。
10011001
垢版 |
Over 1000Thread
このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 89日 10時間 23分 46秒
10021002
垢版 |
Over 1000Thread
5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。


───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────

会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。

▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/

▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php
レス数が1000を超えています。これ以上書き込みはできません。
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況