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

レス数が1000を超えています。これ以上書き込みはできません。
1デフォルトの名無しさん (ﾜｯﾁｮｲ 1f9f-qCnf)
垢版 |
2021/07/28(水) 21:58:48.02ID:nljYiy+l0
!extend:checked:vvvvv:1000:512
↑2行になるようにする

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

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

※前スレ
競技プログラミングにハマるプログラマのスレ 62
https://medaka.5ch.net/test/read.cgi/prog/1626625368/
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
2デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5d-FBxQ)
垢版 |
2021/07/28(水) 22:02:20.52ID:Qpk5DZvUa
>>1
乙
2021/07/28(水) 22:05:12.46ID:AkDAJnSX0
移転記念パピコ
2021/07/28(水) 22:07:40.18ID:/RomxlsxM
もほほほｗ
2021/07/28(水) 22:32:40.69ID:WRtb+nsR0
SNSヲチ勢はNG推奨
健全な競プロスレにしましょう
2021/07/28(水) 22:34:11.90ID:+rljxl10M
うっかり特定されるやつが出てこないか楽しみ〜
2021/07/28(水) 23:12:31.45ID:AkDAJnSX0
15分後にcodechefあるから出ましょう
2021/07/28(水) 23:12:51.00ID:nljYiy+l0
今週末から8問ABCか
2021/07/28(水) 23:16:20.04ID:hI6NGQCYM
インドコンって特有の問題傾向ってあるの？
AtCoderは算数パズル多め的な感じの
2021/07/28(水) 23:20:30.87ID:AkDAJnSX0
苦痛なlog落としの問題とか謎い式を変形していく問題とか？
俺は知らないけどFPSを使う系の問題もあるらしい
2021/07/28(水) 23:26:33.29ID:hI6NGQCYM
結構勉強にはなりそうだね、atcoderにはなさそうな感じ
それだけ聞くと好きかもしれない
2021/07/28(水) 23:38:05.62ID:7WqubHUU0
アカギスレ開始
2021/07/29(木) 01:53:36.35ID:rtR0TgWb0
インド人ってチーター多い印象
2021/07/29(木) 10:23:02.30ID:gQ0ELf6rM
見てみたらインドコンのがコドフォより英文読みやすかった
英文はこっち標準がいい
2021/07/29(木) 10:32:17.31ID:I+iHrM7x0
このスレは終了しました

競技プログラミングにハマるプログラマのスレ 63
https://medaka.5ch.net/test/read.cgi/prog/1627503463/
2021/07/29(木) 13:13:35.91ID:5KnCS92pM
競プロと関係ない馬鹿な話題が蔓延ってたから移行うれしい
17デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5d-kNB2)
垢版 |
2021/07/29(木) 14:34:49.92ID:s9NsQyija
こっち20まで保守とかいるんやろか
2021/07/29(木) 15:26:18.44ID:7yD+ilrEM
たったレス10個で落ちてなかったスレがあるから大丈夫そうな気がするけど
2021/07/29(木) 18:31:45.01ID:SaZKQbptM
前スレで質問あるって言ってた人、こっちで聞いてみたら
俺も可能な範囲で答えるよ
2021/07/29(木) 18:41:27.58ID:BjjCPPvCr
のいみ鍵垢なってるじゃん
非公開リストで見てたのに
2021/07/29(木) 19:11:47.99ID:8ZzMZHUN0
8問ABC が始まったら AtCoder Problems の横枠？がまた狭くなるのかな
AGC-like とかもう問題名が何も見えんのだけども
22デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5d-kNB2)
垢版 |
2021/07/29(木) 19:15:04.25ID:CiCpZIxsa
自分スマホで見てるから関係ないな
2021/07/29(木) 21:52:45.28ID:YihrRvviM
どう棲み分けされてんのこれ
2021/07/29(木) 22:09:03.33ID:PDupjLth0
向こうは競プロerヲチスレ、こっちは競プロスレ
2021/07/29(木) 23:08:45.28ID:8ZzMZHUN0
25分後くらいにこどふぉ div. 2 です
夜更かしする人は出ましょう
2021/07/29(木) 23:41:30.68ID:DDUZLlkb0
米ニューヨーク市
7月30日以降のワクチン接種者全員に
100ドルを配布するキャンペーン開始
2021/07/30(金) 01:42:19.51ID:bjmh4Zft0
nosub余裕でした
2021/07/30(金) 02:00:37.81ID:czlY0Bar0
質問いいですか
Ford-Fulkersonの計算量O(FE)の最大流量Fって何のことですか？具体的にどう見積もればいいのでしょうか
2021/07/30(金) 02:00:44.03ID:w6cU9sbP0
こどふぉのレートなんて溶かしても余裕じゃない？
橙から落ちるとかならありかもしれんが今日はDiv.2 only だし
2021/07/30(金) 02:05:56.79ID:06AAPmWW0
>>28
最大流量F ってのはそのままの意味で、 始点から終点へ流せる量の最大値
見積もりは難しいと思う。自明なカットで上界与えるくらいしかできないんじゃないかな
(辺容量の最大値) * (辺数) とか
2021/07/30(金) 02:41:39.83ID:czlY0Bar0
>>30
ありがとうございます！スッキリしました
AOJのVerify用問題も(辺容量の最大値)*(辺数)が10^7に収まるようになってるので取りあえずその見積もりで問題なさそうですね
（1/4とかの定数倍はつけてもよさそうですが）

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&;lang=jp
32デフォルトの名無しさん (ﾜｯﾁｮｲ 4d90-nzU0)
垢版 |
2021/07/30(金) 03:05:30.73ID:uZitzRq40
最大流が青までの問題に出ない教プロに何の価値があるんだろうか
2021/07/30(金) 03:15:43.73ID:BzNzYO4rM
蟻本だと中級だからそんなに発展的な内容という位置づけではないわな
34デフォルトの名無しさん (ﾜｯﾁｮｲ 4d90-nzU0)
垢版 |
2021/07/30(金) 03:34:11.33ID:uZitzRq40
最大流とかグラフ系を増やしてしまうと進学校の数学の先生が激おこですからね
2021/07/30(金) 03:47:29.25ID:PogAvYGI0
IOIシラバスで明確に除外されてるものは黄色以降でいいだろ
36デフォルトの名無しさん (ﾜｯﾁｮｲ 4d90-nzU0)
垢版 |
2021/07/30(金) 04:22:03.94ID:uZitzRq40
こんなのがあるのか、有効グラフの連結分解が明確に除外ってw
https://www.ioi-jp.org/ioi/ioi-syllabus_jp.pdf

中高生の「事情」に一般人が配慮する一般向けコンテスト
2021/07/30(金) 05:40:51.76ID:IQSK5lVc0
>>35
これはどう考え方？
ARCで前提にするつもりのテクニックはABCで出しておかないと
ARCがそのテクニックを学ぶための教育的コンテンツになってしまうし、ARCの位置づけはそうではないと思うんだが
一切出さないかABCでも出すかの二択しかないと思っていた

それはそうと実はCodeChef LunchtimeはIOIのシラバスに沿うというルールなんだよな
言うほど守られていないが
2021/07/30(金) 08:21:33.11ID:PogAvYGI0
>>37
ABCの600点(解けたらABC卒業;黄diff〜)
に少し難しいアルゴリズムを出すことは否定しない
2021/07/30(金) 08:51:15.74ID:IQSK5lVc0
>>38
なるほどだけど、少し難しいアルゴリズムが結果的に青dif以下になるなら点数にはこだわらなくていい気がするなあ
本当にフロー流すだけ、とかはIOIで除外されてるけど青ボーダーくらいになりそうだし500点ででても違和感がない
(そんなん出すなよ、というのは一理はある)
2021/07/30(金) 09:39:45.05ID:eRLzqDP1d
ZebranessとかGrid and Tokensは黄diffだったねえ
2021/07/30(金) 11:57:16.76ID:LzoN76F4r
アルゴリズムってなんでこんな仰々しい名前多いんだろ
連鎖行列積問題とか行列積コスト最小化問題って書いてたら、何となくやってること分かりそうなのにわざわざ難しく書く
2021/07/30(金) 12:07:52.74ID:VWDfYKRnM
matrix chain multiplicationの直訳だからじゃない
日本語だと仰々しいが英語だと簡潔
どっちも最適化する対象が名前からわからんけど
2021/07/30(金) 12:30:35.89ID:bjmh4Zft0
そもそもそれDPでとける問題の名前であってアルゴリズムの名前じゃなくない？
2021/07/30(金) 12:48:41.93ID:/5sK49wcM
行列積コスト最小化問題だと行列が3つ以上あるように見えないな
英語のchain要素は欲しい
2021/07/30(金) 12:55:36.34ID:KIwi+fa+0
行列鎖積が限界じゃない
方鎖積とか言い出すと意味が取れなくなって危険
46デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-4g3S)
垢版 |
2021/07/30(金) 13:25:31.86ID:l/bfPV+ta
こっちのスレ快適すぎだろ
47デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-hwgF)
垢版 |
2021/07/30(金) 14:20:47.89ID:jPC1M8tJa
もうあっち見てもいない。いい感じで隔離できたね
2021/07/30(金) 16:15:27.35ID:VUDtfB7pr
あっちはゴリラ
こっちは人間
2021/07/30(金) 16:23:38.23ID:a+QHJ9jSa
8問楽しみだ
1問1問にどこまで固執して良いのかな見極めが重要そう
50デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-hwgF)
垢版 |
2021/07/30(金) 16:39:52.14ID:UIn/rcGPa
500点問題が俺でも解ける難易度になってて欲しい
2021/07/30(金) 16:53:52.14ID:BqYo6PZ7a
緑〜水difの問題生やすの難しそうだよな…Writerは頑張って欲しい
2021/07/30(金) 17:06:49.79ID:J3jLSZNL0
詰まらず、より早く解くのが求められそう
2021/07/30(金) 17:24:29.61ID:nNXXdoxJ0
D以降全部青以上とかいう地獄ありそう
2021/07/30(金) 18:12:36.05ID:r2r5v8sO0
どうせすぐに灰灰灰灰黄黄黄黄になるでしょ
55デフォルトの名無しさん (ﾜｯﾁｮｲ ce6f-ZkVx)
垢版 |
2021/07/30(金) 18:48:08.28ID:TtoKf80P0
そういえば4問ABCから6問ABCに変わった初回はunratedになったのを思い出した
今回も参加者増えてジャッジ詰まらないか心配
2021/07/30(金) 19:26:16.88ID:UeHBykXW0
今回参加者増える要因ある？
57デフォルトの名無しさん (ｵｯﾍﾟｹ Sr05-Czf9)
垢版 |
2021/07/30(金) 20:04:52.00ID:AkwBGTPYr
171 仕様書無しさん sage 2021/07/30(金) 19:51:47.26
IDありの方でいい感じに自演してるけど楽しい
こっち見てない人多そうだししばらくバレなそう
2021/07/30(金) 20:09:14.34ID:fkO8fI5R0
ここまで自演
2021/07/30(金) 20:11:41.00ID:06AAPmWW0
今日は yukicoder と Educational なこどふぉです
2021/07/30(金) 20:19:42.93ID:gwTMj6/EM
まあIDなしスレの方でこのスレについて適当に煽るやつが出てくるのも自然ななりゆきだな
61デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-hwgF)
垢版 |
2021/07/30(金) 20:25:20.61ID:8us7N61Da
20年前の2ちゃんねらーみたいなやつやな
2021/07/30(金) 20:49:35.78ID:YHXdGG5Q0
ABCとインド被ってて困る
2021/07/30(金) 22:55:21.88ID:06AAPmWW0
ABC unrated なら インド優先でいいんでないか
トーナメントは知らん
2021/07/31(土) 03:23:13.88ID:OipI3A3d0
直近コドフォAの考え方教えてください
自分は小中大のスライスの数が3:4:5なので、その辺りから必要な枚数をO(1)で導こうとしたのですがうまくいきませんでした
答えが小中大の枚数に関わらず(n+1)/2*5だなとわかった人はどんな発想でそうなったのか知りたいです
よろしくお願いします
ちなみに関係ないかも知れませんが女子中学生です
2021/07/31(土) 04:01:37.36ID:jolcKo8x0
>>64
小中大も単位枚数当たりにかかる時間が同じ

拡張ユークリッド互除法の観点から、ある程度大きな数の偶数は、6 と 8 のペアの組み合わせで作れるみたいなのがある (実際には 6 以上の整数すべてが 3 つのペアから作れる)
2021/07/31(土) 13:03:20.38ID:ZaIYwuCyM
8問ABCか
黄パフォラインは1-2-3-4-5-6の組み合わせで6完とかかな？
2021/07/31(土) 17:02:23.83ID:bng3vbJSa
確かに重い5を飛ばすかの駆け引きがありそうだね
2021/07/31(土) 17:08:23.85ID:ZSov+pKMr
4問から6問への移行のときも参加者増えてたし今日は少なくとも9000人は参加しそう
多けりゃ1万
2021/07/31(土) 17:11:58.52ID:yD4XB78k0
4問から6問のときはrated対象変化のほうが大きそう
今回はそこまで変わらないと予想
70デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-hwgF)
垢版 |
2021/07/31(土) 17:36:59.59ID:etGBbmq6a
問題数の多さに嫌気さして減るまであるかもね。実質何にも変わらないとしても
2021/07/31(土) 19:38:43.84ID:m+/rETnzM
6解いて55に逆転の目があるの面白そう
2021/07/31(土) 20:22:45.64ID:VGaEoFb90
解説放送、スタイル変えないなら深夜3時コースじゃん
73デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-hwgF)
垢版 |
2021/07/31(土) 20:57:07.06ID:ZzHXwKHIa
snukeさんだけ貧乏くじか
2021/07/31(土) 22:47:17.01ID:OqsC7QEbM
問題多い方が満足感あるな
2021/07/31(土) 22:57:12.04ID:OqsC7QEbM
Fが実装難でGが数論の中レベル典型という感じで難度逆転か
数学問はAtCoderだとみんな解くからね
2021/07/31(土) 23:13:47.64ID:eAG/1XYN0
Fが実装辛すぎて震撼してたが、終わってみるとこれに数十分掛けてるようでは。。という気持ちになるんだよな
実装難問題はだいたいそうなんだけど
77デフォルトの名無しさん (ﾜｯﾁｮｲ 917f-8s23)
垢版 |
2021/07/31(土) 23:24:16.55ID:6TJMuv8N0
今日のC問題、
Bだけソートして、
二分探索でB[l]<=A[i]<B[r](l+1==r)となるl,rを探して
min(今までの最小,min(abs(A[i] - B[l]),abs(A[i] - B[r]))))
で最小値だそうとしたんだけど、WAが2つ。
ソートする前に10の9乗よりちょっと大きい数字とその負の数をBに付けた。TLEはない。

なんで？
…とここまで書いてちょっと大きい数を
10**9+20から3*(10**9)に替えたら全部通った。
ドンマイ、俺
2021/07/31(土) 23:26:47.79ID:xfGVog4d0
つまらない実装ミスでF問題落として魂抜けた
ちゃんと大きめのサンプル作って試していればよかったのに
2021/07/31(土) 23:30:49.78ID:yD4XB78k0
Aの提出者数8554 -> 7822か
700人くらい減ったな
2021/08/01(日) 01:22:54.26ID:toXZwxGF0
ratedの人でGH解けてる人どれくらいいるのかな
2021/08/01(日) 02:31:32.43ID:GpOyqzVF0
G は知識があればなんとかなる
H は畳み込みをブラックボックスとして使ってた人は厳しいかも
2021/08/01(日) 09:27:39.31ID:KMs8EVD40
rated だけど E までは簡単で考察も実装も F より G の方が軽かったし、G は無限人解けてそう
H は知らん
2021/08/01(日) 12:54:17.89ID:rnLvS3mlM
難易度若干シグモイドっぽいの解消して欲しいな(難しいとは思うが)
2021/08/01(日) 13:06:46.38ID:j6FSUO0IM
Gは位数とか原始根みたいなちょっと進んだ整数論を学んでたら知ってるような概念割とそのまんまなので、考察負荷も確かにそんな高くない
Fも考察の本体は「あるバスに乗ったあとに乗るバスがあるとすれば一意に定まる」に気づいて超頂点を作るだけな気がするけど、ダブリング二分探索みたいなおまけ部分が重い
AtCoderで重実装問の後ろに軽い数学問出したらそらそっちに流れるわなという
2021/08/01(日) 13:12:02.99ID:j6FSUO0IM
>>83
C茶、D緑、E水、F青を目指してたんだろうなと思ってる
CDEはその点ちょっとブレただけで割と悪くないのでは？
Fは運営がユーザーの実装力を過大評価してたといういつものやつ
2021/08/01(日) 13:16:27.48ID:rnLvS3mlM
>>85
いまグラフ作ってたんだけどまさにその通りだったわ

https://i.imgur.com/tQx8HP0.jpg

Fがもう少し低ければめちゃくちゃいい勾配のセットだったんだな、惜しい
2021/08/01(日) 13:52:43.24ID:j6FSUO0IM
>>86
やっぱFだけおかしいね
どうすりゃよかったんだろう
最初から逆有向森？みたいなのを明示的に与えてあげるか、バスに乗ってる時間を無視してよいとするか
2021/08/01(日) 14:19:38.51ID:yuCAK+tE0
Fは100分6問のFならもっと解かれたはず
解けそうなやつがGにいっただけ
2021/08/01(日) 14:28:11.54ID:4sSkABKe0
fとgの逆転は120分にすれば解消されそうだけど
2021/08/01(日) 14:37:52.06ID:eHM3Q9HLa
同程度の難易度の問題が500と600にあったらコスパ良い600の方が解かれるのは当然
600の方がちょっと難しかったとしても、つまり難易度は逆転していないとしても、diffが逆転することは全然ありうるよな
そういう意味でdiffを重視しすぎるのはどうかと思う
2021/08/01(日) 14:55:17.34ID:lPTv7IAJM
今回のE問題までのほぼ直線的に解いていくしかないような問題配置以外では、diffは問題難度を評価する指標として微妙だとは思う
2021/08/01(日) 15:02:20.30ID:rnLvS3mlM
確かにこの難易度帯が解ける人にとっては実装が重そうなこの問題よりも発想さえ出来れば解ける得点が高い方に流れるか

そうなると問題数増えて時間同じままだから、実装重い問題は忌避されていくんだろうなあ
2021/08/01(日) 15:34:31.35ID:WPaM0mKIM
問題単体の難易度をより正確に評価できるようなdiffに代わる指標ってありうるかな？
diffの定義式にちょっと変更を加えるとかでも
2021/08/01(日) 16:43:17.71ID:/zE4Aaexa
昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた
2021/08/01(日) 16:43:25.60ID:/zE4Aaexa
昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた
2021/08/01(日) 16:45:08.09ID:yuCAK+tE0
大事なことなので2回言いました
2021/08/01(日) 16:51:09.60ID:rylMcfQtM
Eは俺はTDPC-Rグラフの変形だと思って解いたね
全頂点対だとO(N^3 logK)だけど一頂点対についての問題だから大分計算量節約できそう的な
2021/08/01(日) 17:26:18.55ID:4sSkABKe0
tdpc-rってsccしてdag作ってトポロジカルソートするやつじゃなかったっけ？
共通点が見えんけど
2021/08/01(日) 17:27:02.35ID:wjFVnr2/0
Heuristicの方ってABC全完できるくらいの地力ないと難しいかな？
楽しそうだけど実装の方針がよく分からないです
2021/08/01(日) 17:29:40.55ID:GpOyqzVF0
多分 EDPC R と間違えてる
自分には補グラフの形式で与えられてることが本質だと思った
2021/08/01(日) 17:33:35.53ID:rylMcfQtM
>>98
マジだ
すまん、EDPC-Rのwalkの方だな
どっちもRで大体この辺にあったグラフの問題だよなあって感じで覚えてて、問題開いてよく確認してないから間違えた
2021/08/01(日) 17:41:14.99ID:rylMcfQtM
遷移の節約がメインって考えると確かに補グラフが本質か
むしろ行列累乗の発想を使えないからwalkの本質的な部分とは遠いかもしれない
そもそも俺はDPを一から生やすのが苦手な方だから、DPのテンプレとして既知問題が役に立ったという感じかな
2021/08/01(日) 17:47:22.80ID:rylMcfQtM
>>99
俺もheuristic全然できないけどそんなことはなさそう
基本的なアルゴリズムの組み合わせで解を探索してあげるのが主だからそんなに高度な知識はいらないって聞いたことがある
2021/08/01(日) 18:46:28.69ID:OuCRXDXt0
ナップサックだと嘘になるような貪欲でもheuristicだと十分な解法になり得る
ちゃんとした貪欲が書けるだけどもかなり強いよ
2021/08/01(日) 23:17:01.04ID:SzlISrEQ0
コドフォやります
2021/08/02(月) 00:06:59.46ID:HCiXaFZK0
>>99
Heuristicsは貪欲書けてBFSとDFSができれば何もできないってことはまずないと思う
あとは勇気を持って噓貪欲書いて、結果をビジュアライザで見ながら改善していけばいい
2021/08/02(月) 02:04:52.64ID:wQG5EWK+0
クエリのやつABCで復習したのですんなり解けてうれしい
2021/08/02(月) 02:24:36.26ID:9vrfDka+0
おめでとう
2021/08/02(月) 04:57:00.13ID:wQG5EWK+0
制約がn=2*10^5とかで想定解がO(n)なのって出題者の優しさでしょうか
それとも定数倍とかの関係？
O(nlogn)解で通った人←
2021/08/02(月) 05:19:48.94ID:9vrfDka+0
N と NlogN の区別はなかなか厳しいことが知られております
N 個の入力を与える問題なら問題を解くより入出力を捌く時間の方がネックになるなんてこともある
2021/08/02(月) 12:15:14.37ID:YwN/bnngM
入出力数がO(n)ならn=10^7とかにするとそこがボトルネックになって非本質ゲーになりがち
あと遅い言語でO(n log n)落としてO(n)通すように設計するとC++ではO(n log n)が普通に通るなんてことがある
logを落とす力を評価するコンテストサイトもあるっぽいけど、AtCoderは入出力ゲーとか言語格差とかそんなに好きじゃないのであまりそういう力は問わない
2021/08/02(月) 12:50:39.03ID:LBPYCkqw0
一応ABC189-Cがlogの有無を意図してるっぽい
2021/08/02(月) 14:48:31.21ID:ayT6z8jYr
POJで鍛えなさい
2021/08/02(月) 18:36:35.29ID:8AKddLB+0
logは2つつくとめちゃくちゃ速度落ちるよね
2021/08/02(月) 19:53:01.87ID:YwN/bnngM
セグ木上の二分探索とかlog二つをlog一つに落とせて嬉しいパターンが結構ある気がする
2021/08/02(月) 20:48:14.11ID:GApG+yr20
https://atcoder.jp/contests/abc208/tasks/abc208_f
これは割と変なlogつけると通らないんじゃないかな
2021/08/02(月) 22:33:06.34ID:LBPYCkqw0
logって2つあるほうが早いんじゃないんです？
2021/08/02(月) 23:02:50.81ID:Tt09fpMhH
log x × log xのことじゃね
log log xではなく
2021/08/03(火) 13:47:56.92ID:8JvOP1wgM
最近競プロで必要そうな知識を整理してて、集めるとそれなりの分量になるなと思った反面、AGCの難問には基本的な知識しか問わないけど難しいものが結構あるよね
多分知識入れただけじゃ解けるようにならなそう
どうやって練習してる？
2021/08/03(火) 19:10:08.89ID:0jHwVPOe0
天才以外お断りパズルコンテストだぞ
2021/08/03(火) 19:24:48.79ID:kh8UNFwQ0
高1でatcoder赤になった奴、東進全統高で上級生抑えて一位だな。
プログラミングと受験勉強の配分はどうなってるんだ?
2021/08/03(火) 19:48:26.20ID:S/rr5p7AM
全方向に才能が溢れていた結果としてAtCoder赤になったのであれば、受験勉強も軽くクリアできてもそんなに不思議じゃない
2021/08/03(火) 19:54:23.17ID:Knm+pPdg0
AGCもなんだかんだで練習量でそこそこ溶けるまでは解ける
個別の練習はやってないや
2021/08/03(火) 19:55:24.31ID:Knm+pPdg0
✕　溶けるまでは解ける
◯　解ける
2021/08/03(火) 20:12:18.13ID:k75IS9uU0
>>119
https://www.oreilly.co.jp/books/9784873114057/
読んだことある？
2021/08/03(火) 20:41:09.91ID:S/rr5p7AM
>>123
結局演習量という話はよく聞くね

>>125
ありがとう、読んだことないや
目次を見たけどかなり競プロと相性がよさそうだね
2021/08/03(火) 22:19:00.93ID:0sSYM0/y0
なんかのめり込んでる時期はAGC全然勝てなかったけど一旦離れてたらいい感じに力抜けて苦手意識なくなったな
2021/08/04(水) 00:02:03.33ID:t30SArGP0
あるある
めちゃくちゃやってた時期よりもレート伸びてるわ今
2021/08/04(水) 13:37:25.83ID:PT9ISTH50
ここしばらくコンテストしか出てないけどレートなんやかんや上がってるわ
2021/08/04(水) 22:11:47.50ID:BC2fUSktM
エレガントな問題解決ポチった
数オリの問題も結構含まれてるっぽくて楽しみ
2021/08/05(木) 02:17:05.07ID:StUL0nUY0
>>130
英語版の公式サイトに解説マニュアルあるよ。載ってるのは選ばれた問題だけだけど
2021/08/05(木) 20:50:38.29ID:IgsNgOEp0
PaizaってAからやたら計算量ギリギリな問題が多くなる気がする...
TLEで一発終了なのがキツい
2021/08/06(金) 21:22:03.99ID:eJxIR3k1M
>>131
ありがとう
届いたから読んでるけどまさに算数パズルという感じの問題が集まってて面白い
普通に演習問題の中に難しいのも結構あるから世話になるかも
2021/08/07(土) 12:48:17.49ID:tc9pz7jrr
132だけどやっとA取れました...
茶色になった記念でpaizaに挑戦したけど意外と苦戦した

Aの美術館のセキュリティって問題でasin,acosが出てきて三角関数の逆関数の使い方を色々学べて楽しかった(これだけじゃネタバレにならんと思う)
asinは終域が-π/2〜π/2で全単射
acosは終域が0〜πで全単射だからモジュールの仕様で出てくるradianに気をつけないといけないんよね
2021/08/07(土) 14:56:20.68ID:xkx44HTf0
paizaの問題は話さん方がいいよ
2021/08/07(土) 15:00:37.61ID:m+E3Az4E0
ぶっちゃけアウト臭い書き込み
2021/08/07(土) 15:16:31.01ID:m3lfMST8M
解答の本質とは関係ないぐらいの書き込みなんだろうから直ちにアウトってレベルじゃないと信じるけど、事前に要求知識が分かるだけでも微妙なのでやめといた方がいいと思う
あれ提出までの時間も評価対象だし
2021/08/07(土) 15:32:05.34ID:zSH+M8IW0
一切言及しないほうが無難
2021/08/07(土) 16:04:55.36ID:y0a7Ux9p0
誰も聞いてないのにスレチのpaizaのネタバレを始める茶色
2021/08/07(土) 17:20:38.22ID:6YaIW8x50
rated砂漠の時ってみんな過去問解いたりしてんの？
2021/08/07(土) 19:55:50.34ID:63+No8M60
山ほど溜まってるコンテスト中にACできなかった問題を処理してる
rated 砂漠時に限らないけど
2021/08/08(日) 13:14:36.11ID:RAJi5Z5J0
leetcodeのLISをO(nlogn)で解くってググれば出てくるんで典型なんですかね？
もしコーディング面接だったら解ける気がしないですね
2021/08/08(日) 13:16:52.61ID:CSMSEp0d0
典型だけど覚えてなきゃまあ無理だね
2021/08/09(月) 18:48:38.87ID:8zL0HaLl0
diffよりも正確な問題難易度の指標ってないだろうか
chokudaiはdiff信仰をやめろって言ってるけど現状問題点数が全くあてにならないから結局diff見るしかないんだけど
2021/08/09(月) 19:02:08.36ID:NKZvGIDN0
正確な難易度指標がほしいモチベがなくない？
2021/08/09(月) 19:18:16.99ID:8zL0HaLl0
>>145
勉強として考えるなら適正問題探す意味は薄いけどさ
今の実力でぎりぎり解けたり解けなかったりする問題がすぐにわかったらゲームとしては遊びやすくて嬉しくない？
2021/08/09(月) 19:27:37.98ID:NKZvGIDN0
>>146
その使い方なら diff 程度の信頼度でも十分だと思うけどどう？
2021/08/09(月) 19:53:06.68ID:8zL0HaLl0
>>147
た、たしかに…
2021/08/09(月) 20:50:23.56ID:UyuWFwykM
一元的な指標を作るのは難しいね
ただ点数、diff、平均AC時間、ABC or ARC or AGC、コンテスト中の問題の位置あたりを使えば何かしら予測できそうではある
あと難易度評価と言えばAOJ-ICPCの投票システムとかも悪くなさそう
2021/08/09(月) 21:22:43.06ID:0xclxDfU0
Tree Gameとか問題だけ見たら黄diffがいいところなのにAGC-Fに置いてあるってだけで赤diffなんだよな
diff、点数、出題時期、傾向、コンテスト時間、点数、問題位置あたりをパラメータにしてなんかすごいパワーで問題単体の指標が出来たら嬉しそう
2021/08/09(月) 21:23:13.93ID:0xclxDfU0
2文目、149とほとんど同じこと言ってたわ
2021/08/09(月) 22:35:42.42ID:oJ+uf8nYa
>>150
そんなことあるのか…今回のABCも8問になったから多すぎて終わらんくてHが赤difとかになってしまったのだろうか
2021/08/09(月) 23:22:45.32ID:JOLWY9t6M
分割統治FFTはtwitterの人々の反応をみても知識レベル的に橙〜赤はあるようには見えるし、今回はそんなに極端に上がったわけではなさそう
ただ、今回のFレベルの問題が仮にHの位置にあったら橙diff上位になるみたいなことは普通にありえそう
2021/08/09(月) 23:27:18.20ID:qAneHxiW0
こどふぉでます
2021/08/09(月) 23:31:11.11ID:6hsXVPRwr
どうぞ
2021/08/09(月) 23:48:37.40ID:Qpru44Ly0
8問制になったことで今まで以上にdiffの信憑性がイマイチになりそうなんだよな
EFGHのうち典型3問、実装1問だとしたら
実装問が難易度的には一番易しくても橙diffとかになりかねないし
diffにとらわれず全部覚えろという意見ももっともだが、なるべく効率的にやっていきたいので
やっぱりよりよい指標ができたら嬉しい
157デフォルトの名無しさん (ｱｳｱｳｳｰ Sa55-qGWQ)
垢版 |
2021/08/10(火) 01:12:05.76ID:+8rHdyoLa
せめて120分にしたらもう少しdiff下がるよね
2021/08/10(火) 01:37:07.20ID:kyVvGt1x0
ビット演算系やめてください><
2021/08/10(火) 01:53:40.55ID:mNwE8I44a
EをFGHと同じ括りにしてるのよくわからないけど
毎週高々三つなら全部やればいいじゃんとしか
2021/08/10(火) 07:29:54.11ID:LC21nH1E0
新しい知識週3つ身につけるのって結構しんどくないか
161デフォルトの名無しさん (ﾌﾞｰｲﾓ MM85-4F3g)
垢版 |
2021/08/10(火) 08:42:22.48ID:jFfsp4nTM
Fは500点問題としては難しかった。6問の時のFのままの難易度では。
2021/08/10(火) 13:50:51.09ID:BRh8cZi00
くまくまここ見て誕生年変えただろ、案外見てるもんなんだな
2021/08/10(火) 20:47:31.28ID:4c2QU1WN0
そういうのはあっちでどうぞ
164デフォルトの名無しさん (ｱｳｱｳｴｰ Sa23-fnA7)
垢版 |
2021/08/10(火) 21:06:15.34ID:YaD+0zrAa
ABCで明らかにRatedが解けない様な問題たくさん出してるのってどういう意図なのかな
2021/08/10(火) 21:13:14.40ID:/CAOXhvjM
高難度典型枠は高レベル向け典型90としてみるとありがたいけど、だったらストレートに高レベル向け典型90という形で出してもよかったんじゃないかなあとも思う
界隈の知識レベルを向上させる？みたいなコンセプトそんなに悪いとは思わないからさ
2021/08/10(火) 21:37:39.83ID:rXXBytuO0
ratedが解けない問題出す云々は他のコンテストでもそうじゃないか？
ARCの後ろとかもそんなもんだと思う
2021/08/10(火) 22:23:49.89ID:mpjmHC7I0
ARCもAGCもratedで全完が出るかどうか、くらいの回が多いしABCもそうなっていくのかね
一般論としてはratedが全完同士のスピード勝負になるよりは上から下まで点数の勝負になるほうが健全と思うけど、
ABCは上位のかなりの人数が2400になるから全完多めでも問題ないはずなんだよな
2021/08/10(火) 22:46:22.62ID:kIbhVP3U0
平成ABCでのまぐれ全完が最初で最後の全完になった
2021/08/11(水) 00:11:42.49ID:0Oto7RAVa
ABC全完しても2400パフォ出ない簡単回が続いてた頃より今の方が好みだな
2021/08/11(水) 00:56:37.31ID:b9xBsSxN0
そのうち5完で2400出る回が出そう
171デフォルトの名無しさん (ｱｳｱｳｳｰ Sa55-qGWQ)
垢版 |
2021/08/11(水) 02:40:27.47ID:aKewhnjga
まあ色々文句も出てるけど、e問題までは確実に以前の難易度に戻ったから良かったと思う
172デフォルトの名無しさん (ﾜｯﾁｮｲ 8102-whzZ)
垢版 |
2021/08/12(木) 06:44:33.27ID:cvBubBdB0
それはほんとに思う　Eまで大分解きやすくなったよね　ありがたい
2021/08/12(木) 12:26:52.35ID:MhzNI6zx0
EはABC198以前の難易度になった感じかな
まだサンプル2だしE青パフォとかになることもありそう
2021/08/12(木) 13:06:07.88ID:/vY/xrb70
社長曰く
Easy/Easy/灰-茶/茶-緑/水-青/青/黄-橙/黄-橙

辺りを狙っていくとのことだったので、E青は全然ありうると思う
現時点ではFが思ったより難しいのがアナウンスと異なる点
2021/08/12(木) 19:00:50.50ID:iPUu/t9P0
easyは1個ではダメなのかな
2021/08/12(木) 21:19:29.53ID:O6/hwFmj0
それな
試してもないのに解ける問題数が〜みたいな社長の妄想によりそうなってる
初心者にオススメのコンテストは英語に抵抗なければCF Div. 3だわ
2021/08/12(木) 22:08:44.55ID:XVIxXAq/0
こどふぉは Div.3 だろうが A の時点で for かけないとキツい
2021/08/12(木) 23:15:20.77ID:PAaMatCR0
>>167
なるほど、たしかにRatedで全完する人がいっぱいいると、スピード勝負になっちゃうもんな
全完をちゃんと狙うのはABC卒業してからだな
2021/08/13(金) 02:06:11.01ID:TKH0RJqr0
卒業どころか今のabcでの全完は橙が最低ライン感
180デフォルトの名無しさん (ｱｳｱｳｳｰ Saa5-QBLq)
垢版 |
2021/08/13(金) 04:54:00.24ID:ivCE0qz6a
for文書けない人に配慮する前に気にすべきことがあるんじゃないかとは思う
2021/08/13(金) 04:59:00.27ID:d10N4LCE0
配慮できるところはしたらいいよ
2021/08/13(金) 09:15:28.52ID:ET0TWdhj0
こないだのA問題は実質的にfor書けない人配慮してないと思う
183デフォルトの名無しさん (ｱｳｱｳｳｰ Saa5-QBLq)
垢版 |
2021/08/13(金) 10:00:25.00ID:ivCE0qz6a
こないだのaは自信なかったんで全探で解いたわ
2021/08/13(金) 12:09:33.84ID:Q9Og6rch0
ACLにあるけどあえて自作したライブラリあったら教えてください
その理由も
2021/08/13(金) 12:29:51.97ID:p/cCzLwk0
理解のために全部自作した
2021/08/13(金) 12:52:15.47ID:ngjlvNKt0
Pythonなので自作せざるを得なかった
2021/08/13(金) 16:20:50.50ID:bbHqrAbk0
Pythonも非公式であるよ
2021/08/13(金) 19:37:23.95ID:KfBxR1C6M
前から持ってたやつが結構あって、自分で作ったやつの方が慣れてるからそっち使うことはよくある
ACLのが基本よくできてるが
2021/08/13(金) 19:39:29.14ID:TCQcRUU10
ACLできた時点で大体持ってたな
floor sumとかconvolutionあたりは持ってなかったからACL使ってる
2021/08/14(土) 00:47:37.98ID:ZXowzLrW0
最小費用流
理
2021/08/14(土) 00:49:50.26ID:ZXowzLrW0
由は負辺対応してない、双対変数の復元がない、計算量が悪い
2021/08/14(土) 05:59:35.72ID:ko7wRKQy0
自分が知る範囲だとSSPで十分な問題ばかりだ
2021/08/14(土) 15:46:07.08ID:HsdJVSdnF
そういやACLが登場したけどまだABCでネットワークフローの問題でてない？
2021/08/14(土) 16:00:48.86ID:3VHWyRmA0
205F
2021/08/14(土) 19:52:51.26ID:Wnc/OfBI0
>>194
あざっす
2021/08/14(土) 22:44:25.33ID:ZXowzLrW0
ちょうど最小費用流出て草
2021/08/14(土) 22:45:45.02ID:jJqE/8Qy0
D重い方から考えてたけど軽い方からなのかー
2021/08/14(土) 22:46:53.54ID:Wnc/OfBI0
くくく、このスレで予習できたかいがあったぜ・・・
2021/08/14(土) 22:47:28.63ID:vplBoWGwr
うわー
2021/08/14(土) 23:27:08.23ID:cRK97gTUM
全然GH見てる余裕なかったな
Gは時間が十分あったら赤diffというほどは難しそうに見えない、ARC中盤で出したら黄diff上位〜橙diff下位ぐらい？
2021/08/14(土) 23:57:47.01ID:63WAvoG70
包除原理知ってるなら時間あれば解けるはず
多分橙もいかないと思う
2021/08/15(日) 00:01:22.59ID:2+BjVwf10
って思ったんだけど ARC121E で橙あるのか、じゃあ橙行きそうだ
2021/08/15(日) 00:27:24.96ID:5gOn93br0
時間足りなくてコンテスト中に見れなかったけど、GよりHのほうが簡単に感じた
2021/08/15(日) 01:11:14.80ID:H6I2LS5IM
問題見たけどまさに負辺対応mincostflowを実装できますか？という感じだ
205デフォルトの名無しさん (ﾜｯﾁｮｲ 3121-1+Eo)
垢版 |
2021/08/15(日) 03:22:13.67ID:gujuFnPB0
>>193
そういうCSっぽいのを出すと受験を控えた電通のご子息の負担になってしまうんよ
2021/08/15(日) 03:25:58.48ID:s1GcBgA10
>>205
新ABCで3回は出てるし、皮肉が成立してなくないか
207デフォルトの名無しさん (ﾜｯﾁｮｲ 5902-1kHZ)
垢版 |
2021/08/15(日) 03:52:35.22ID:A2cCfMbu0
Eは典型とかFは典型とかいう意見を見たけどほんとに典型なん？あれをはい典型だねと思って解けるようになる未来が見えないんだけど
2021/08/15(日) 04:50:36.43ID:bWhJC11s0
Fはけんちゃんのそのまんまの記事があるから流石にね
209デフォルトの名無しさん (ﾜｯﾁｮｲ 41cd-TSG6)
垢版 |
2021/08/15(日) 14:08:24.22ID:mhmE79MH0
プログラミング初心者にアルゴ式勧めてる人ちょくちょく見るけど
AOJ の ITP とかのほうが良くないか？
2021/08/15(日) 14:54:37.55ID:uRaI3NTPH
Eは確かにありがちな貪欲っぽく見えるけど、典型だとしたらどんな名前がついてるのか気になるな
2021/08/15(日) 14:59:39.05ID:3DZjO06KM
区間スケジューリング問題の類題じゃないの
2021/08/15(日) 16:06:46.79ID:wBwRbZcb0
>>211
お前すげえな。なるほど。
2021/08/15(日) 23:30:31.95ID:ZhmQbivo0
コドフォでます
2021/08/16(月) 07:46:06.39ID:KEIthCHyM
Twitterと勘違いしてんちゃうぞ
2021/08/16(月) 12:41:38.02ID:4w1z8qFD0
チー牛なう
2021/08/16(月) 14:43:02.04ID:adtnZqXzr
先週のDってKruscalとPrimのアルゴリズムを実装したことある人なら簡単だったのかな
緑だと厳しくて水の人らはそこそこ解けてるからこの辺り知識差がでたのか
2021/08/16(月) 14:46:05.39ID:adtnZqXzr
マトロイドってやっといた方が良いの？
2021/08/16(月) 15:42:21.88ID:FZJNdLMvM
マトロイドは勉強したけど青黄往復レベルの自分だと直接的にそこまで役に立ったことはまだないかな
クラスカル法の一般化として理論は面白い、電気通信大の資料で勉強した
問題に出てくる対象がマトロイドになってるとわかると直感的に明らかでない場合も貪欲でできるとわかって嬉しい
けどそもそもマトロイドであることを初見で見抜いて示すのがそこまで簡単じゃない
自分の認識はこんなもんだけど橙以上の上位陣がよく話してるマトロイド交差みたいな上位典型もあって、自分が把握してない活用法がまだまだありそう
2021/08/16(月) 15:51:57.71ID:FZJNdLMvM
あとこの前のABC-Dではあまり最小全域木アルゴは意識したつもりはなかったけど、辺を段々追加して動的に管理するみたいな発想は確かにそのあたりのアルゴの影響で思い付けた可能性はあるかも
どちらかというと主客転倒がメインで、辺が寄与できる範囲の木を作ろうという気持ちだった
2021/08/16(月) 16:22:44.46ID:P69OtXRQ0
辺の寄与考えると小さい順にやるのがよさそうで、これクラスカル法じゃんとはなったな
俺はどっちかというとABC120-Dのお陰で思いつけたかな
2021/08/16(月) 18:21:55.66ID:4w1z8qFD0
>>216
ちょうど水色でなんとかそれ解けた、ってレベルだけど、
似たようなアイデアを断片的につかう問題をいくつもやってたからたまたま解けたって感じ。
やっぱ解きまくって典型解法に習熟するのが重要なんじゃない？
初等レベルの算数でも足し算、掛け算、割り算の筆算は練習しまくらないと慣れないし。

ちなみにクラスカルは楽勝に実装できるけど、プリムのやり方忘れたやべえ。マトロイドはなんのことだか知らんがな、って知識量。
2021/08/16(月) 23:12:02.22ID:j3YAfdPx0
それはunion-findがあるからですかね？
2021/08/17(火) 00:29:52.66ID:aCo5Pa//0
せやな。UnionFind覚えとけば簡単やろ
224デフォルトの名無しさん (ﾜｯﾁｮｲ 222c-ODwZ)
垢版 |
2021/08/17(火) 20:29:41.66ID:hYkkAkQv0
ウニオンフィンド(´・ω・｀)
2021/08/18(水) 23:33:39.30ID:S6rQne5p0
こどふぉでます
2021/08/19(木) 01:51:19.53ID:pBNq7Nwb0
div3なのにムズくないですか？
2021/08/19(木) 02:03:46.39ID:pBNq7Nwb0
Eの後ろから見るアプローチ天才過ぎる
類題あったりします？
ゴールから考えるのに近いですかね
2021/08/19(木) 02:23:56.11ID:ew9z2fUi0
E は今日の div.3 の中では一番 adhoc 気味かもしれん
後ろから見るというより最後に付け足した文字列は何になるかというのを考えると自然かもしれん
229デフォルトの名無しさん (ﾜｯﾁｮｲ 2eb9-pBez)
垢版 |
2021/08/19(木) 02:58:40.08ID:UckJ/DAo0
ほどよい難易度だったね
230デフォルトの名無しさん (ｶﾞｯｸｼ 0626-LMo/)
垢版 |
2021/08/19(木) 11:00:23.69ID:a6l+9Dx26
ABC214-Dが茶色予想だったってchokudaiがあーだこーだーで言ってたね
・辺をコストでソートする
・Unionfindで管理する
って普通の人はクラスカル法を理解してないと着想難しいし、あれが茶色は流石にないでしょう
2021/08/19(木) 11:25:46.99ID:cVn6riSd0
逆にクラスカル法理解してれば無だからなあ
どの知識が何色かなんてこの漢字は何年生で習うでしょうってくらい難しいししょうもない
2021/08/19(木) 12:02:52.17ID:Lm0ZKUOKM
最小全域木やるだけが茶色くらいなイメージあるな
2021/08/19(木) 12:06:47.36ID:W7/x/NRZM
dpやるだけ
2021/08/19(木) 12:56:10.30ID:pBNq7Nwb0
クルスカル法を想起させたいなら最初から木構造にすな
2021/08/19(木) 13:11:02.73ID:Lj4tZxFZM
あれそんなにクラスカル法結び付く問題かなあ、実装方針が外形的に同じなだけで本質的な部分は別だと自分は感じたけど
2021/08/19(木) 13:19:00.82ID:VmP4TPOx0
クラスカル法とはあんまり関係ない気がする
2021/08/19(木) 13:20:11.00ID:W7/x/NRZM
おれもそう思うわ
たまたま実装方法がクラスカルっぽくなっただけと感じる
2021/08/19(木) 13:21:50.46ID:W7/x/NRZM
解いてるときも、別にクラスカルのことは連想しなかったけど、解けたし。
2021/08/19(木) 15:55:26.69ID:Xp2pw9Z80
考察全部終わってからクラスカルだなとはなったけど最初からクラスカルは違う気がする
2021/08/19(木) 17:06:54.35ID:XyFkWe0Hd
最小全域木やるだけは水色くらいありそうな気がするが…
ufやるだけが茶〜緑くらいのイメージ
2021/08/19(木) 19:38:17.56ID:Gif+FtHO0
一昔前ならUF使えて茶色なんてこと絶対なかったと思うんだけど、厳しすぎない？
2021/08/19(木) 20:03:19.71ID:lHWKO9NcM
知識問のdiffはこれからも下がっていきそう
昔より初級者はちゃんと勉強しないとレートが上がらないゲームになってるとは思う
2021/08/19(木) 20:39:43.61ID:U/+cw26+0
クラスカルとは全く違う

クラスカルは最小の和が欲しいから、小さい方から貪欲に見ていくのであって、今回のは各辺の寄与をみるのに小さい方からみるとうまくいくというだけ

アルゴリズムが本質として違いすぎる
2021/08/20(金) 17:51:46.53ID:sosiCxFj0
クラスカルとは違うけど枝を小さい順から見ていってunionするとか、プリムとは違うけど頂点集合のカットから最小の枝を選ぶとかの考え方を1度やっておくと
別の問題に帰着できそうね
245デフォルトの名無しさん (ｱｳｱｳｳｰ Sa63-wMFD)
垢版 |
2021/08/21(土) 00:34:03.74ID:uRKo8Igna
今月ARC一回だけか。。
2021/08/21(土) 15:45:30.51ID:V1ZE3jgcM
今日のFGHなにが出るだろうか
幾何系がそろそろ出てもおかしくないよね
2021/08/21(土) 16:31:30.90ID:TPRQrV4f0
CHT使うdpとか
248デフォルトの名無しさん (ﾜｯﾁｮｲ ff02-VfHF)
垢版 |
2021/08/21(土) 22:10:18.81ID:7GAoG1Iq0
Rustのメモリ安全性はボローチェッカーによって担保されているが、
Nimと比較してRustはタイプ量が多い事により限りなく低い生産性と
C++のような高い難読性、超巨大なバイナリ生成性能を兼ね備えています

Nimはバージョン1.5.1でRustのボローチェッカーに似た「View types」が実装されれば、
GC無しのView typesで参照の有効性を検証することによってメモリ安全性を保証しつつ
限りなく抑え込まれたタイプ量で高速化したCのソースコードを吐き出せます

Nimソースコード ==nimコンパイラ==> Cソースコード ==Cコンパイラ==> バイナリ

なので、nimコンパイラが通った時点でメモリ安全性が担保されませんか？

Nimの実験的特徴
著者： アンドレアス・ルンプ
バージョン： 1.5.1
http://nim-lang.github.io/Nim/manual_experimental.html


Nimは限りなく抑え込まれたタイプ量で高い生産性とPythonのような高い可読性を実現し
ているにもかかわらず、高速なCのソースコードを吐き出せるのでC言語でリモートワーク
されている方は割り振られた仕事が早く終わっても終わってないふりをして怠けることができる

「怠け者とはこうあるべきだ！」と言うとても大事な事を Nim は我々に教えてくれます
2021/08/21(土) 22:55:31.25ID:1B8QhnzYM
今回は比較的調整がうまく行ってる方なのかな？
Gは困難というほどでもないし、Fもちょうどいい塩梅
250デフォルトの名無しさん (ﾌﾞｰｲﾓ MMc3-ujp1)
垢版 |
2021/08/21(土) 23:08:27.09ID:FoeKOLs+M
今日のC問題、26^8の並べ替えは全探索は無理と思ってたけど、8^8の並べ替え考えればいいんだな。
2021/08/21(土) 23:22:14.02ID:bLvUIapj0
原理を知ってると応用がきくって基本だけど大事よな
今回のD
2021/08/21(土) 23:32:07.02ID:1B8QhnzYM
noshiさんの言ってるTaylor shiftやっと理解した
f(x) = \sum_{n=0}^N c_n x^nとする
二項定理から
f(x+a) = \sum_{n=0}^N c_n (x+a)^n
= \sum_{i=0}^N (\sum_{n=i}^N a^{n-i} c_n \binom{n}{i}) x^i
これは二項係数をばらしてj=N-i, k=N-nとして
\sum_{j=0}^N x^j /(N-j)! \sum_{k=0}^j (a^{j-k}/(j-k)!)((N-k)! c_{N-k})
になる

この後ろの部分をよく見ると畳み込みになってて、
g(x) = \sum_{n=0}^{N} (a^i/i!) x^i
h(x) = \sum_{n=0}^{N} (N-i)! c_(N-i) x^i
の畳み込み(g*h)(x)のi次の項に1/(N-i)!倍すればいい
これでO(NlogN)でFPSの平行移動が計算可能
2021/08/21(土) 23:32:14.25ID:bLvUIapj0
さすがにleetcodeは無理
2021/08/22(日) 02:42:21.05ID:lA6zPNOR0
>>252
FPSではなく、多項式かと。
2021/08/22(日) 04:57:26.20ID:9hi5HAom0
何言ってるのかと思ったけど一般の FPS だと定数項を含む式は合成できないってことか
256デフォルトの名無しさん (ﾜｯﾁｮｲ ff02-VfHF)
垢版 |
2021/08/22(日) 13:12:10.90ID:0Cz6ueFz0
Rustのメモリ安全性はボローチェッカーによって担保されているが、
Nimと比較してRustはタイプ量が多い事により限りなく低い生産性と
C++のような高い難読性、超巨大なバイナリ生成性能を兼ね備えています

Nimはバージョン1.5.1でRustのボローチェッカーに似た「View types」が実装されれば、
GC無しのView typesで参照の有効性を検証することによってメモリ安全性を保証しつつ
限りなく抑え込まれたタイプ量で高速化したCのソースコードを吐き出せます

Nimソースコード ==nimコンパイラ==> Cソースコード ==Cコンパイラ==> バイナリ

なので、nimコンパイラが通った時点でメモリ安全性が担保されませんか？

Nimの実験的特徴 バージョン1.5.1
http://nim-lang.github.io/Nim/manual_experimental.html

第二プログラミング言語として Rust はオススメしません Nim をやるのです
https://wolfbash.hateblo.jp/entry/2017/07/30/193412


Nimは限りなく抑え込まれたタイプ量で高い生産性とPythonのような高い可読性を実現し
ているにもかかわらず、高速なCのソースコードを吐き出せるのでC言語でリモートワーク
されている方は割り振られた仕事が早く終わっても終わってないふりをして怠けることができる

「怠け者とはこうあるべきだ！」と言うとても大事な事を Nim は我々に教えてくれます
2021/08/22(日) 13:20:23.57ID:emY9LezaH
>>254
>>255
ありがとう
最初Nが有限じゃなきゃ意味のない式だから確かにFPSじゃなくて多項式において適用可能か程度の認識で読んだけど、そもそも根本的に定数項を含むFPSを他のFPSに代入しちゃダメなのか
恥ずかしながら理解してなかった
確かに一般のFPSに1を代入したら容易に定数項が発散してしまうね
0に何掛けても0なので0次の項が爆発してしまう
2021/08/22(日) 23:15:22.56ID:eCBCrI1l0
ARC125-DのBIT使って解くパートがよくわからん教えて
2021/08/23(月) 00:00:54.44ID:rVUZWXnA0
dp[i]を先頭i個について最後の要素を必ず使う場合の答えとかしてそのままBITに乗せればいい
2021/08/23(月) 23:52:44.91ID:ylCgDGXX0
競技プログラミングは役に立たない

Competitive programming is useless
https://kislayverma.com/organizations/competitive-programming-is-useless/
2021/08/24(火) 11:36:43.63ID:86nlJJ+dM
ざっくり読んだけど、大意としては白カピさんが前言ってたようなことと大体似たような感じ？
優秀なITエンジニアを目指すことと競プロを突き詰めることは分けて考えた方がいいというのはまあそうだよねという感じ
2021/08/24(火) 12:55:23.18ID:s7mDIt89r
青くらいまで取れたら十分でそれ以上は趣味かな
2021/08/24(火) 14:53:30.06ID:dGk193ua0
独創的な問題じゃなくて、
「このような要件を持ったRailsアプリを作りなさい」

というのが実際に求められることだからな
2021/08/24(火) 15:01:44.46ID:dGk193ua0
あと競技プログラミングで作ったものって
他の人の役に立たないよね？

あんなに優秀（笑）な人が時間をかけて作業してるのに
競技プログラミングの成果は無駄になる

ものづくりのためにあるプログラミングなのに物を作らない
ものづくりに必要ない技術の競技なってるから役に立たない
2021/08/24(火) 15:18:14.22ID:hCwrk83dM
入り口の段階でコーディングに慣れたり頭の体操ができる的な効用はあると思うけどねー
まあ趣味なので一定レベル以上でそんなに実用的な期待のもとにやってる人は少ないと思う
266デフォルトの名無しさん (ｱｳｱｳｳｰ Sa63-y8ey)
垢版 |
2021/08/24(火) 21:34:58.15ID:2qNqCWyUa
黄 abc卒業、一つの到達点
青？
水 アルゴカンスト
緑 業務上は十分
茶 入色！

なんか青だけ中途半端だな。自分の立ち位置をうまく説明できなくて就職も失敗しそう
2021/08/24(火) 21:50:18.98ID:SMXHl8SK0
クイズ・頭の体操・コードゴルフ

プログラミングのお題スレとか、上田隆一のシェル芸と同じ
2021/08/24(火) 23:28:11.24ID:0WsJR9q70
Codeforces の時間です
2021/08/24(火) 23:43:32.61ID:dGk193ua0
Codeforces の時間は終わりました
来週の放送時間は未定です
270デフォルトの名無しさん (ﾜｯﾁｮｲ ff90-DepB)
垢版 |
2021/08/25(水) 02:33:04.77ID:6jB+kuHx0
>>266
それ書いた頃から色１つ以上ずれてる予感
最大流が青以下で出てない以上黄色でもカンストしてないし、灰色で高度なグラフや最適化アルゴリズムを実用レベルで使うことも可能でミスリーディング

今のatcoderはアルゴリズムをダシにしたただの算数パズル
2021/08/25(水) 02:37:42.84ID:bVpxdvkM0
アルゴ力カンストしてます！とか言われても笑ってしまうわ
2021/08/25(水) 02:58:48.07ID:9ur9WLlqr
白カピを信仰しろ
2021/08/25(水) 03:13:33.31ID:QAFlw/BR0
こどふぉは B で詰まりまくって爆死した
整数1, 2個与えて計算してくれみたいな感じの問題が苦手っぽい
274デフォルトの名無しさん (ﾜｯﾁｮｲ ff90-DepB)
垢版 |
2021/08/25(水) 03:26:54.54ID:6jB+kuHx0
グラフアルゴリズムを使えなくても、整数問題と漸化式と関連してdpが使えれば最悪青までいけるように調整してきたのがatcoder、受験生に優しい
275デフォルトの名無しさん (ｱｳｱｳｳｰ Sa63-CKVu)
垢版 |
2021/08/25(水) 04:56:41.94ID:hWSOgqtaa
門外漢に説明する場合実態よりも社長のブログ記事やから
2021/08/25(水) 10:41:38.03ID:bVpxdvkM0
こどふぉB、所謂整数1,2個系っぽくはない気がする 普通のDPであまり数学っぽくはないというか
2021/08/29(日) 22:37:29.72ID:O8C2ShXrr
全然参加してないっぽいね
2021/08/29(日) 22:41:26.84ID:wQMrMg8g0
ad hoc coder
2021/08/29(日) 22:55:37.34ID:Z+jA1Ny+M
牛ゲーっていうんだこれ
G問題なのにad hocで妙だなって思ってたけどちゃんと高度典型に関わる問題だったんだね
牛ゲーへの帰着よりad hoc解の方が簡単で結果みんな解けているけど
2021/08/29(日) 22:58:14.42ID:Z+jA1Ny+M
Gまで比較的簡単だったことを考えるとなおさらHが際立つね
2021/08/29(日) 23:03:52.50ID:6wJ9M+9P0
公式自体は知ってたけど固定されてるパターンしか見たことなくて応用できなかった
2021/08/29(日) 23:25:47.06ID:gwGacy3s0
ああGは区間スケジューリングみたいな貪欲でいけるんだ
天才では？
2021/08/29(日) 23:38:12.75ID:Z+jA1Ny+M
牛ゲー理解したけど、これ知ってても帰着に訓練が要りそう
2021/08/30(月) 00:04:52.56ID:zE3c6uCW0
最短経路問題に帰着したあと、負辺に悩んだ末にグラフの特殊な形を利用して準線形にしたけど
解説見てなるほどなあとなった
初手で反転するタイプのやつ全般、いつも見落としてしまうな
2021/08/30(月) 02:38:00.45ID:kWOHjgqd0
システムテスト弱forces
2021/08/30(月) 03:40:50.80ID:/wFsORFN0
Combined で E 通してる人と同室になる確率が低い
2021/08/31(火) 01:37:25.41ID:GJ5/Tp+20
もしや解説でないとかあるのか？
2021/08/31(火) 03:50:25.65ID:zWtj8ap20
なんの話かは知らんけど解説そのうち出すよといって何年も放置されてる問題は存在する
2021/08/31(火) 18:30:11.43ID:AswRbNW9M
日本語圏を掘るだけでもかなりの知見が発掘できるように中国語圏にも知見がたくさん集まってると思うんだけど、なんかまとめてるサイトとか知ってたりする？
2021/08/31(火) 21:10:30.18ID:hI7pxuUc0
ジャッジでよく聞くのはluogu libre uojとか？
個人ブログはcsdnで書いてる人が多いイメージ
2021/09/01(水) 12:14:20.08ID:fU+iEeheM
>>290
ありがとう
csdnはUIがどことなくredditに似てるね
多分zennとかqiita的なサービスなんだと思うけど
競プロは競争性編程(の簡体字)というみたいだ
2021/09/01(水) 12:15:18.08ID:fU+iEeheM
libreは見れたけどluoguは接続できないな
2021/09/03(金) 17:59:41.58ID:aZL21txy0
https://oi-wiki.org/
ここにまとまってる知見だけでもかなりの量
2021/09/03(金) 18:06:19.71ID:S4blRWG30
すごいwikiですね
2021/09/03(金) 18:30:45.42ID:zCAk3B080
大半は日本でも広く知られていそうだがときどきマニアックなのが紛れ込んでるな
2021/09/03(金) 23:09:38.04ID:ZQGey3GnM
>>293
これはすごい…
Chtholly Treeとか初めて聞いたな
前のABCに出てきたLGV公式とかも当然載ってる
2021/09/03(金) 23:16:13.01ID:ZQGey3GnM
牛ゲーのことを差分约束と呼んでるのか
2021/09/04(土) 22:47:23.13ID:iZFHdm7PH
Eみたいなの新しいデータ構造を作ってみようみたいな感じで面白いと思ったな
2021/09/04(土) 23:10:09.45ID:D7xNfee+0
vEB木って俺の考えた最強のデータ構造感があってかなり好き
実践では使わないけど
2021/09/04(土) 23:20:56.78ID:4070OU6NH
https://www.slideshare.net/catupper/nazoki
catupperさんがスライド出してる謎木だね
2021/09/06(月) 01:35:28.67ID:BDvSeAD00
実装重すぎforces
2021/09/11(土) 22:40:52.42ID:NWwhMr/N0
二次元壁画問題やめてください><
2021/09/11(土) 22:41:48.93ID:urand5+L0
Eで時間使いすぎた…
2021/09/11(土) 22:52:30.32ID:eUpul5/v0
c嫌い
2021/09/12(日) 01:13:19.29ID:XEnhxu4n0
逆にCみたいなのがプログラミングしてる感あって好き
2021/09/12(日) 01:33:19.35ID:kaW/Dkvg0
DPだと添字いくつあってもいいのに
幾何学が絡むと二次元でも頭が爆発するのなんでだろう
2021/09/12(日) 01:41:12.36ID:w/wqXHR50
単純に幾何に慣れてないだけとちゃうの
2021/09/12(日) 01:43:36.75ID:kaW/Dkvg0
その通りでございます
309デフォルトの名無しさん (ﾜｯﾁｮｲ f177-9yYO)
垢版 |
2021/09/12(日) 04:27:40.04ID:7UxarLCX0
算数パズルと叩きまくれば普通のプログラミングやアルゴリズムの問題が増える
2021/09/14(火) 04:13:51.06ID:GzssHl260
https://twitter.com/kyopro_friends/status/1436693258298482688
を見るとABC218-Gがpriority_queueでも解けるように読めるんだけど、今回みたいにバックトラックが必要な場面でもこのテクニックは使えるもの？
multisetみたいに任意の要素を削除できないと厳しい気がするんだけど
https://twitter.com/5chan_nel (5ch newer account)
2021/09/14(火) 05:25:48.22ID:qg5T7rKqr
誰かが削除可能priority_queueのテクニックを紹介してた
2021/09/14(火) 07:41:25.33ID:KKCjfkYV0
出来はするけど面倒だからmultisetで書いた方が楽だと思うよ
2021/09/14(火) 11:44:56.93ID:MFIRQbY90
https://twitter.com/maspy_stars/status/1436690222465486848?s=21
これ？
https://twitter.com/5chan_nel (5ch newer account)
2021/09/14(火) 14:42:52.17ID:/xeH/JpQ0
>>313
C++書いててちょーショック
2021/09/14(火) 14:59:12.87ID:GzssHl260
なるほど…確かにこれなら削除できるね
言われてるようにmultisetのほうが楽だからあまり使わなそうだけど、勉強になったよ
ありがとう
2021/09/14(火) 15:42:22.96ID:h+pf9pNHM
なるほど
priority queueのメリットといえば定数倍の速さだけど、こっちの方が速かったりするのかな？
maspyさんはコドフォでは普通にC++を使ってるイメージ
2021/09/14(火) 18:34:53.52ID:SK+RosMiM
priority queueから削除が要る時は、追加する値を2倍+1、削除する値は2倍にして
同じキューに突っ込んで、取り出した値の下位1ビットが0の数だけスキップする
最強園児の選別でそんな感じのものを使った気がする
2021/09/14(火) 19:14:04.78ID:5jb1fRHV6
レート付き園児が出てくるやばい問題ね
min、maxおよび定数個のk分位点の取得はpriority queueでほぼ代用可能ということかな
検索は大体どの言語にもあるunordered_setで代替できる
lower_boundとかは無理そうか
まあ、平衡二分探索木の代用だとクエリ先読みできるんなら座圧BITの方が直感的にわかりやすい気がするけど
2021/09/19(日) 08:00:29.80ID:HCXVW8kB0
Ruby だと想定解通りに書いても遅くて通らないの何なの?言語差別なの?俺にCrystalの道を示してるの?
2021/09/19(日) 12:40:14.90ID:HwX1dH8g0
Rubyが遅すぎるんじゃないのかな使ったことないから知らんけど
余り遅すぎる言語に合わせるとC++とかでクソ解法が通ってしまうからしょうがないような気もする
一応Pythonなら通せるようにする方針らしいけど
321デフォルトの名無しさん (ﾜｯﾁｮｲ 9732-t0a3)
垢版 |
2021/09/19(日) 13:16:18.07ID:NXnuF3oi0
Rubyはインタプリタとしては遅いわけではないが、JITコンパイルでもあまりはやくならないのが厳しい。PyPyのように速くなるものがあるといいんだけどね。
2021/09/19(日) 14:43:04.37ID:HCXVW8kB0
C++の軍門に下るかCrystalを極めるかしかないのか
昨日と先々週のD問題は想定解書いても通らなかったし、悔しいけどもうRubyじゃ無理なのか
323デフォルトの名無しさん (ﾜｯﾁｮｲ f732-t0a3)
垢版 |
2021/09/19(日) 15:23:37.00ID:vAjqgmQ30
Ruby書けるならCrystalはすぐ書けるようになるよ。ほとんど同じ。

むしろ型アノテーションが使える分、Crystalの方が書きやすいまであるかも。個人の感想です。
324デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5b-3TuO)
垢版 |
2021/09/19(日) 17:32:36.92ID:PtCH0+cLa
crystalはほんとよくできてるよね。静的型、null安全を実現しつつもrubyistがこだわる「rubyらしさ」がほとんど損なわれていない
2021/09/19(日) 17:42:41.13ID:0QFbDPlQ0
RubyはC++と比べると100倍ぐらい遅かったりするんでしょ？
制限時間を緩めてもらわないとさすがにキツそう
2021/09/24(金) 23:47:31.60ID:+K7ebcKh0
コンテスト前に抜くとパフォーマンス出ないジンクスあるからコンテストある日は禁欲してるんだけど、
みんなはそういうのある？
2021/09/25(土) 07:46:07.75ID:clKvl1Nc0
パスタじゃなくて米を食べるようにしている
なんか知らんが気分的に米の方がパフォーマンスが出る、自分にそう言い聞かせてるだけかもしれんが
2021/09/25(土) 09:58:53.83ID:jKOhIQ9/0
テンションの上がる音楽をかけながらだとパフォーマンスが上がる気がする
だいたいシューティングゲームのボス戦の曲だが...
2021/09/25(土) 13:30:23.74ID:YrZFQiAF0
>>328
こういうのはお好みですか？
https://www.youtube.com/watch?v=CZiHhS7r6M0

https://www.youtube.com/watch?v=4IgQ6LNE9Yo&;t=103s
または
https://www.youtube.com/watch?v=4IgQ6LNE9Yo&;t=728s
あるいは
330デフォルトの名無しさん (ｵｯﾍﾟｹ Sr0f-agLc)
垢版 |
2021/10/16(土) 03:00:16.89ID:vcLu1S2Wr
うんち！w
2021/10/16(土) 12:28:23.59ID:Z5bSFj950
おしっこ！w
2021/10/16(土) 19:45:04.31ID:1UED94kPr
トイレの使用時間がT秒以下の時は「おしっこ」、超えるときは「うんち」と出力せよ
2021/10/16(土) 23:50:11.18ID:HoxpZDC90
Cを差分に言い換えてあぼん
いやまあ差分の方針でもいけないことはないけど見通しが悪い
2021/10/17(日) 00:05:50.78ID:f7OUjdhe0
C問題、よく見ると双対取ったら二変数のLPだからSeidel法でexpected O(N)？
気づけなくて悲しい
2021/10/17(日) 23:29:51.69ID:l9G3noePM
今回のHは典型知識なのかな
あんまりad hoc要素を感じないけどかなり強い人でも解けてない気がする
2021/10/17(日) 23:42:38.80ID:f7OUjdhe0
Gは木を二部グラフ(V1×V2)とみなして大頂点S, Tを追加してSからTに最大フローを流した状態の残余グラフについて考えたら解けた

v1 ∈ V1, v2 ∈ V2がマッチしているとして、v1 → S → … → v2 → v1みたいなサイクルがあることがv1を消しても別のマッチを作れる条件で、
v1, v2, Sがすべて同じ強連結成分に属するなら消してもOK、だめならv1は消せない、と考えると通った

「残余ネットワーク上の貪欲は正しい」としか覚えてないので厳密な証明はよくわからない……
2021/10/18(月) 21:30:25.41ID:cUABpoQy0
↑別に難しくなかった
最大フローを流した状態の残余グラフをGとして、GからS->v1->v2->Tに流れているフローを押し戻してv1を消したグラフをG'とする
G'にSからTへの増加パスが存在することが、v1を消しても最大マッチングの大きさが減らない必要十分条件である

G'にSからTへの増加パスPが存在するとする
Pがv2を含まなければPを伝ってSからTに行った後、T->v2->v1->Sと戻ってくるのがG上のサイクルになっている
Pがv2を含んでいる場合はPを伝ってSからv2に行った後v2->v1->Sと戻ってくるのがG上のサイクルになっている
どちらの場合もv1, v2, SはG上で強連結

逆にv1, v2, SがG上で同じ強連結成分に属するとする
v2->v1->SはG上で一方通行のパスだから、Sからv2へのv1を含まないパスが存在して、これにv2->Tを加えるとG'上でSからTへの増加パスである

(v2を消す場合もv1, v2, Tに関して同じことが言える)

この方針なら二部グラフでもO(M sqrt(N)))とかで解けてそう
2021/10/18(月) 23:04:34.93ID:LqxpWLBB0
>>337
いまいちわかってないんだけど
V1 = {2}
V2 = {1, 3}
2-1
2-3
という二部グラフで S->2, 1->T, 3->T みたいに張るとS を含む強連結成分ってSのみにならない？
ST両方について解いてる？
2021/10/18(月) 23:21:33.28ID:cUABpoQy0
>>338
GやG'は残余グラフのほうを指してるつもりだった
その例で言うと、最大マッチングとして2-1を選ぶとGは

S <- 2
2 <- 1
1 <- T
2 -> 3
3 -> T

で、この場合、1, 2, Tは同じ強連結成分に属しているので2を消してもS->Tへの別の増加パスが見つかる
S, 1, 2は同じ強連結成分に属していないので1を消すと増加パスが見つからない
340デフォルトの名無しさん (ﾜｯﾁｮｲ fb01-Avck)
垢版 |
2021/10/21(木) 16:15:46.81ID:8ILWSSPd0
フリーランスに立ちはだかる「常駐」の壁。慣例を打ち壊し、
“テレワーク”案件3割→8割へと成長を遂げた「クラウドテック」の軌跡

リモートワーク求人専門サイト「プロリモート」がリニューアルオープン、業務委託契約の求職者と企業をマッチング

1/3以上が採用につながる高マッチング率、リモートワーク×エンジニア・デザイナー専門の
人材紹介サービス「ReworkerAgent」正式リリース場所からも時間からも自由な働き方を実現！

茨城県日立市、県外からの「テレワーク移住者」に最大151万円の助成金

長野市、市内に移転・事業所設置し、移住することで最大550万円の支援金を支給

フリーランスが活用できる「最大1,000〜3,000万円・補助率50%〜75%」の
『ものづくり・商業・サービス補助金』とは？概要や条件を解説

『ReWorks（リワークス）』リモートワーク特化型転職サイトとして 3月5日 リニューアル
2021/10/24(日) 20:18:53.47ID:1P0Qc1d30
最近某ngtの質問箱に毎日のようにキモいのが送られていて、流石にかわいそうになってきたな。
2021/10/25(月) 00:43:40.20ID:xXPH57uh0
最近始めたけどついさっきああでもないこうでもないおかしい計算が合わないみたいなこと延々とやってC問題一つ解くのに2時間半かかった
辛い
2021/10/25(月) 04:27:00.29ID:GyOhDsWs0
実験エスバーって鍛えることできんのかな
2021/10/26(火) 22:34:52.78ID:59ycdlv3M
数学ではよくある考え方やテクがABC-Cから登場すると思うけど、基本的なものでも初見だと難しいものが多いと思う
最初からスムーズに解ける人たちは散々似た考え方に慣らされてきた人たちだと思うし
ABC-Cぐらいの数学的思考の素養ぐらいは身に付けておいて損はないと思うから、慣れてみるといいんじゃないかな
2021/10/26(火) 22:38:10.35ID:Z19LRAELr
競技プログラミングは役に立たない！！！１１１１１
2021/10/26(火) 22:43:03.70ID:59ycdlv3M
グラフや木の問題だったら手癖でよくあるケースを作れるようにしたりして実験そのものをスムーズにできるようにしたり
愚直解の実装を早めにやるように心がけたり
ありがちな注目すべき量(パリティー、剰余、木の葉の数、木の直径、頂点の次数、連続する二項の差分、転倒数、総xor…etc)の知識が増えてくるとエスパー精度上がりそう、俺自身実験エスパーそんな得意じゃないから知らんけど
2021/10/30(土) 01:57:46.41ID:cDpW0Kxw0
C問題ぼちぼち解けるかなくらいのレベルなんだけど時々手も足も出ねぇ…ってのが紛れてて辛い
まぁそういうのは大体みんなの正答率も低いんだけど
2021/11/01(月) 14:31:29.29ID:i3pN4gLD0
AGCの問題の解き方わからんね
昨日も、Bは不変量見つける感じで典型要素があるといえばあるけどAとかアドホックすぎる
2021/11/01(月) 17:13:19.31ID:xYwaxLMb0
文字種を減らして考えるの典型かもしれん
2021/11/01(月) 18:46:47.15ID:Dv3I90PDa
不変量見つけられなくて死んだ
351デフォルトの名無しさん (ﾜｯﾁｮｲ 1302-48dE)
垢版 |
2021/11/04(木) 22:10:01.18ID:hqf6Ttzz0
AtCoderの「第二回 アルゴリズム実技検定」のテストケースはどこにありますか？
2021/11/04(木) 22:38:53.47ID:KITyg0nv0
dropbox に上がってないのなら無いんじゃないか
2021/11/13(土) 00:38:47.84ID:WhtcoC320
ちょっとずれた話題になるけど競プロ好きな人ってどういう方向の就職が向いてるのかな
よくある金融系とか医療とか販売サイトとかそういうのが全然ピンとこない。ロジックを考えるのが楽しいのであって何を作るかにあまり興味ないというか…
2021/11/13(土) 13:07:06.56ID:7FvDzxQTr
無職
355デフォルトの名無しさん (ﾜｯﾁｮｲ 2302-09aj)
垢版 |
2021/11/13(土) 23:13:52.96ID:cg3EZESf0
paizaのSを全解き目指してるレベルの者だけど、>>345の意見には納得するところがある。
競プロやる前は、クラス定義してDictionaryでどうこうすれば、大抵の問題は片付いた
わけだが、競プロの問題ではクラスなど定義していたら時間切れになってしまうので、
配列だけで何とかするという、文法的にはレベルの低い書き方をして、いかに実行時間を
短くするかということに主眼がおかれていると思う。ビジネスで使うには10の何乗という
データ数はない場合がほとんどだし、計算に１週間程度掛かるのも問題ないことが多い。
競プロ的な書き方をすると、他のプログラマーとコーディングスタイルがかなり異なって
しまうと思う。
2021/11/13(土) 23:22:26.39ID:uY2REMe7r
>>355
>>345だけど長文キモイ死ね
2021/11/18(木) 20:07:30.91ID:Y/dc6XOP0
>>355
個人で開発するとき役に立つよ
2021/11/18(木) 20:15:30.78ID:otq4UsEcr
いや役に立たない
2021/11/18(木) 20:46:20.19ID:yaHQuJEZ0
paizaはatcoderと比較して時間制限が緩いし、その制限に間に合わないときは、
他に最適なロジックがあるってことだと思うよ

あと競プロを解いていると、自分が知らないやり方とか、効率の良いやり方を
知ることができるということが大きいと思う

意外と文字列と時間の細かい扱い方とか知らないことがあるので
それを知るきっかけになるので勉強になる
2021/11/28(日) 10:44:07.64ID:BXa3qjcoM
その是非や影響の議論は置いといてAB難化は事実だと思うんだけど、copilot対策という噂は本当なのかな？
2021/11/28(日) 10:56:10.69ID:DkHLSjjA6
ソースは特に見当たらないけど、それ以外にABを難しくするモチベがあまりなさそうだからそう言われてる
あとは精々、企業コンではあまりにもひねりのない問題の出題は避けてるとか？
362デフォルトの名無しさん (ﾜｯﾁｮｲ f79a-i1Ew)
垢版 |
2021/11/28(日) 13:18:03.58ID:ykDYmOS+0
競技プログラミング的なロジック組んで金になる方法考えてみようぜ
とりあえず俺は自動取引系ソフトに一票
2021/11/29(月) 02:15:40.60ID:6Nke2U5s0
取引系の問題は未来が見えてることが前提だからなあ
364デフォルトの名無しさん (ﾜｯﾁｮｲ 977c-VbP9)
垢版 |
2021/12/01(水) 02:28:23.44ID:7HPQuU+R0
ABC226-H の解説に類題として挙げられていた以下の問題が解けません
> 区間 [0,1] 上に一様ランダムに区切り線を n−1 本入れて n 個の区間に分けた時、 k 番目に短い区間の幅の期待値は？
ABC226-H 自体はすんなり解けたのですが上の問題は正直N=3の時点で自分には手が出なくて、困ってます
2021/12/02(木) 20:39:33.36ID:rnInpLg+M
まず、k=1はわかりますか？
これは期待値がx以上になる確率を考えるとできるはず（累積分布関数を考えているという点が類似ポイント）

で、一般の場合は包除原理を適用するとできる

途中式省くけど答えは1/n (1/n + 1/(n-1) + ... + 1/(n-k+1))になります
2021/12/04(土) 08:39:45.51ID:x9fVLDRG0
ええと、k=1の場合は
P(x) を x 以上となる確率として \int_0^{\infty} P(x) dx が求められれば良い
x 以上となるような区切りの入れ方は[0, 1-nx] に区切りをn-1本入れて、各区切りの間に幅xを挿入したものと一対一対応するので
P(x) = (1-nx)^{n-1}
よってk=1の答えは \int_0^{\infty} P(x) dx = 1/n^2
みたいな感じでいいでしょうか
2021/12/04(土) 11:45:52.27ID:GTTC1A5Hr
競技プログラミングは役に立たない！！！１１１１１
368デフォルトの名無しさん (ﾜｯﾁｮｲ 5202-PP5C)
垢版 |
2021/12/04(土) 12:33:36.19ID:gg0i98sn0
>>367
355だけど、役に立つよ。頭の体操になる。数学の問題を手で解くより面白い。
2021/12/04(土) 13:13:02.72ID:cnvRxgJD0
月刊はスルー
2021/12/04(土) 17:52:55.15ID:Sp+Fe1MX0
問題解くときの計算用紙代わりにブギーボードとかの電子メモ帳を買ったんだけど書き心地良いしかなり良かった
おすすめ
2021/12/04(土) 18:44:46.61ID:4uhn1ZQo0
>>366
0とmax取るか積分範囲を1/nまでにしないと壊れると思うけど合ってる
2021/12/04(土) 23:30:13.88ID:HadgEFtEa
>>370
何インチのやつ使ってる？
2021/12/05(日) 00:26:27.51ID:3WaDD3Ky0
>>372
10
2021/12/07(火) 22:01:44.64ID:XzzazBW10
ipadええぞ
375デフォルトの名無しさん (ﾜｯﾁｮｲ 0f01-izju)
垢版 |
2021/12/18(土) 14:36:12.14ID:EFVtFN3G0
「ゲームで金儲けする時代止められない」ＣＣＰゲームズ代表インタビュー

「CCPゲームズ」のヒルマ・ベーガー代表は14日、オンラインインタビューで最近、
話題に浮上した「プレイトゥオン（Play to Earn 儲けるゲーム）」について「世界のゲーム業界には、
すでにゲームアイテムを取り引きする2次市場が存在する」とし「儲かるゲームは以前にもあったし、
これからも止められない流れになる」と診断した。
CCPゲームズは、世界的な人気ゲーム「イブオンライン(Eve Online)」を開発・運営する。イブオンラインは、
世界で4000万人以上が楽しんでいる。
CCPゲームズは最近、NFT（代替不可能トークン）コンテンツを披露し、注目を集めている。
「アライアンス・トーナメント」というゲーム内の大会商品でNFTコンテンツを配った。
2021/12/21(火) 13:47:34.46ID:8AspzEl40
最近勉強始めたばかりの初心者だけど動的計画法でつまづいている
部分構造最適性っていうけど、損して得取れというか一部では損でも全体で見れば最良になるような問題やケースは無いのか？って思う
2021/12/21(火) 14:46:04.05ID:PWwxpbwJd
ないことを証明して使うんだぞ
2021/12/21(火) 18:49:26.20ID:gTw96teU0
枝刈り全探索だと思うとよさそう ナップサック問題でいうと大きさは同じなのに価値が低い組みたいにどう頑張っても得にならないケースは使わないように大きさごとに価値が最大のものだけ持っておく感じ？
2021/12/21(火) 20:30:24.97ID:JiGJ+/NL0
動的計画法がいまいち理解できない人には、メモ化再帰バージョンを試してみてほしい
と、個人的には思うんだけど、再帰呼び出しそのものが難しいかしら？
2021/12/21(火) 21:03:00.48ID:msz2/cZB0
馬鹿みたいだけどちょっと大きめの表を手で埋めてみるといいんじゃ
2021/12/22(水) 02:28:33.78ID:Z+1UFQDg0
近頃再帰少しずつ書けるようになってきてメモ化再帰も試してはいる
ただたとえばフィボナッチなんかはわかりやすい。同じ計算してるからメモしておくっていうのは
でも経路とかの問題でmemoは違う値にならえないのか？ってなる。値が更新されてたらそれを返すっていうけどさらに更新される可能性はないのか？って
2021/12/22(水) 07:21:37.51ID:NfauV/oWr
競技プログラミングは役に立たない！！！１１１１１
2021/12/22(水) 22:28:18.00ID:AhLEKKoC0
>>381
違う値になりえる場合は使えないよもちろん

正当性が証明できるときだけ使うし、正当性が担保できるようにアルゴリズムを組むんだよ
これ以上は具体的な問題見ないとなんとも
2022/01/06(木) 16:07:10.87ID:ar76WYHcr
競技プログラミングは役に立たない！！！１１１１１
385デフォルトの名無しさん (ﾜｯﾁｮｲ 9901-sV8s)
垢版 |
2022/01/06(木) 17:53:55.86ID:lFeOOX7v0
白カピを讃えよ
2022/01/06(木) 18:46:38.73ID:+JxpBntd0
新スレどこやねん
2022/01/06(木) 18:49:44.26ID:gEtgsFwH0
>>386
新スレはここです
向こうに新スレは立ちません
2022/01/06(木) 19:00:24.58ID:/n5h7nDr0
ABCが待ち遠しい
2週間も待てない
2022/01/06(木) 19:18:36.50ID:e57wTEaXr
ﾜｯﾁｮｲがなんだ実害はないぞ
390デフォルトの名無しさん (ｱｳｱｳｳｰ Saa5-keiW)
垢版 |
2022/01/06(木) 19:27:37.71ID:sqyEIboYa
別にわっちょい怖くなんかないけど、人がおらんとどうしようもない。向こうのスレコンテスト後の数時間はクソスレ極まってるけど、日常のバカ話で人を引き止めてるところはあるのかもしれない
391デフォルトの名無しさん (ｱｳｱｳｳｰ Saa5-keiW)
垢版 |
2022/01/06(木) 19:30:20.21ID:sqyEIboYa
>>390
>コンテスト後の数時間はクソスレ

すまん「コンテスト後の数時間以外はクソスレ」の間違い
392デフォルトの名無しさん (ﾜｯﾁｮｲ 9901-sV8s)
垢版 |
2022/01/06(木) 19:33:22.15ID:lFeOOX7v0
くんすこ
393デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM26-ADtK)
垢版 |
2022/01/06(木) 19:52:52.81ID:E4kfzcZtM
常時クソスレだろ？
2022/01/06(木) 22:42:19.30ID:+JxpBntd0
ごみ
2022/01/15(土) 23:10:33.87ID:JDpiuwgA0
どうして制限時間内に解けないのに、制限時間が終わった途端解法が思いつくのか……俺こういうことよくあるんだけどなんでだろうね
2022/01/18(火) 14:45:51.28ID:0TVQxye3M
実力が足りてないからです
〜完〜
397デフォルトの名無しさん (ﾜｯﾁｮｲ a734-B/cF)
垢版 |
2022/01/26(水) 13:16:14.83ID:HUI/BT/C0
>>395
何物にも縛られない「自由な動き」が創造性を高めると判明！
https://nazology.net/archives/103764

多分これが一番近い理由だと思う
創造性とは少し異なるけど競プロも発散的思考の要素はある
拘束とも少しずれるけどそれに似た緊張が不調なタスクには絡んでると見てる

>>396
結果だけみて判断するのは他人をフィルターにかけるときは傾向が収束するから合理的だが、個々の事案に向き合うときには不十分だと思うで
398デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM8f-yRnv)
垢版 |
2022/01/26(水) 17:34:45.45ID:IMxi6ITqM
風呂に入ってたら思い付いたアルキメデスの原理の逸話もあるし、精神状態に応じて辿り着ける思考は違うんだろうね
特にコンテスト終了前後じゃ劇的に違うだろう
考察得意な人は意図的にその辺のモードをコントロールするのが得意だったりしたりするのかも？
2022/01/26(水) 17:37:21.02ID:IMxi6ITqM
ロシア情勢がキナ臭いけど、CodeForces大丈夫だろうか
2022/01/27(木) 13:18:26.14ID:OpKzkVck0
ややズレるがchokudaiもコンテスト中は自分は天才だと思い込まないと解ける問題も解けなくなると言ってるな
強い人はメタ認知が上手いと言っていいと思う
2022/01/31(月) 18:47:21.46ID:Qej12BAi0
昨日のABC-Ex, 答えの値が求まるのはいいんだけど復元ってどうやるの？
2022/02/05(土) 22:52:58.12ID:jPeChQFj0
解説読んでも理解できないとなかなかつらいものがある
2022/02/07(月) 11:20:03.82ID:87L5vkcm0
それは本当に実力が足りてなくて悲しくなるやつじゃん
404デフォルトの名無しさん (ﾜｯﾁｮｲ 6301-piVT)
垢版 |
2022/02/14(月) 10:47:03.47ID:TVm+ejPZ0
フリーランスに立ちはだかる「常駐」の壁。慣例を打ち壊し、
“テレワーク”案件3割→8割へと成長を遂げた「クラウドテック」の軌跡

リモートワーク求人専門サイト「プロリモート」がリニューアルオープン、業務委託契約の求職者と企業をマッチング

1/3以上が採用につながる高マッチング率、リモートワーク×エンジニア・デザイナー専門の
人材紹介サービス「ReworkerAgent」正式リリース場所からも時間からも自由な働き方を実現！

『ReWorks（リワークス）』リモートワーク特化型転職サイトとして 3月5日 リニューアル

副業・兼業マッチングサービス「クラウドリンクス」登録者数2万人突破
中小企業で進む副業人材の採用、96％が継続採用を希望

茨城県日立市、県外からの「テレワーク移住者」に最大151万円の助成金

長野市、市内に移転・事業所設置し、移住することで最大550万円の支援金を支給

フリーランスが活用できる「最大1,000〜3,000万円・補助率50%〜75%」の
『ものづくり・商業・サービス補助金』とは？概要や条件を解説
2022/03/10(木) 16:34:08.09ID:gI/pxyVEM
ここが新スレですね
2022/03/25(金) 03:32:02.97ID:EX0HU7Ak0
こどふぉのE、思い付く過程が知りたい
2022/07/01(金) 23:28:27.46ID:JFBfOGuK0
むこうのスレもうだめかもしれんね
2022/07/02(土) 12:20:53.48ID:64B/Ignl0
こっちでまったりやるか
2022/07/02(土) 14:29:22.62ID:xEhxhveC0
うんち！w
2022/07/02(土) 14:38:46.53ID:eTWk7aiV0
おしっこ！w
2022/07/02(土) 16:34:24.04ID:BfnPedOR0
今日のABCの感想はこっちでやればええんか？
2022/07/02(土) 16:38:30.13ID:WXVFk7BC0
おれもこっちにする
2022/07/02(土) 17:13:03.65ID:Y5ZkAX2p0
むこうってどこ？
2022/07/02(土) 17:43:00.56ID:LoAUafRE0
まともな会話ができるならどこでもええで
2022/07/02(土) 17:53:27.76ID:0olBoaxMr
競プロ関係のツイートに対して言及するならまだしも写真に対して色々言うのは終わってる
2022/07/02(土) 20:55:32.38ID:WXVFk7BC0
ABCでます
2022/07/02(土) 22:55:59.87ID:WXVFk7BC0
うーん、FよりもさっさとGに取り組むべきだったか
2022/07/02(土) 22:59:29.78ID:0olBoaxMr
EFGHも50点ずつでもいいから点差欲しいな
ABCDF>ABCDEだろうし
2022/07/02(土) 22:59:32.54ID:WXVFk7BC0
Eの解説賢い
累積和とダブリング使って解いたわ
2022/07/02(土) 23:01:26.44ID:0olBoaxMr
低レベル帯は上位アルゴいらないって誰かが言ってたけど今回のEとかみたいに考察省略できるのはアドだよなぁ
2022/07/02(土) 23:06:03.64ID:64B/Ignl0
ワッチョイ有りだとガイジスレとイクが居なくなるのでは？
422デフォルトの名無しさん (ﾜｯﾁｮｲ 0a02-9ZeA)
垢版 |
2022/07/02(土) 23:06:46.41ID:2OTHusXb0
Bがこの重さってまじ？
もう新規囲い込む気ないよねこのサイト
2022/07/02(土) 23:08:58.82ID:64B/Ignl0
>>420
>>421
ワッチョイ一致してるけどスマホをwi-fiに接続しただけで自演の意図はないです
紛らわしくてごめん
424デフォルトの名無しさん (ﾜｯﾁｮｲ 8e02-CTF5)
垢版 |
2022/07/02(土) 23:10:19.92ID:cezlBl1t0
BCDの3問がCCCになってる
2022/07/02(土) 23:11:51.52ID:WXVFk7BC0
普通にナイーブだったし何も気にしてなかったけど、diff見るとたしかにB高いな
Fもなんかむずかったし、また文句出そうだな
426デフォルトの名無しさん (ﾜｯﾁｮｲ 0a02-9ZeA)
垢版 |
2022/07/02(土) 23:12:52.80ID:2OTHusXb0
プログラミング入門者で、競技プログラミングやってみよーって人が今回のABCのBをみたらどう思うだろうね
これじゃあ人なんて増えないわ
2022/07/02(土) 23:14:28.88ID:NaXk4Q6c0
Fみたいなやつ実装爆発して終わってまう
428デフォルトの名無しさん (ｱｳｱｳｳｰ Sacf-pVYn)
垢版 |
2022/07/02(土) 23:24:56.50ID:z91+ebe7a
bよく読めばそんなに難しくないんだけどな
出題者がdiff低く見積もったのもわかる気がする
2022/07/02(土) 23:34:27.93ID:64B/Ignl0
ABC255のBのdiffを余裕で越してきたな
歴代最難関Bか
2022/07/02(土) 23:42:03.00ID:cezlBl1t0
ABCで今回のよりもdiffが高いBが出たのは少なくとも5年前
2022/07/02(土) 23:43:25.18ID:WXVFk7BC0
灰や茶にとってはちょっと難しい要素が複数詰め込まれてた感じか？
問題文がちょっとむずい
8方向遷移がちょっとむずい
順番に並べて整数を作るのがちょっとむずい
みたいな
432デフォルトの名無しさん (ﾜｯﾁｮｲ 1b7f-K581)
垢版 |
2022/07/03(日) 00:33:20.34ID:1yNMSZTa0
Bはひたすら面倒くさかった
2022/07/03(日) 00:36:15.46ID:etWgu0oL0
二次元配列の8方向見ていくやつはスニペットとして持っとくべきだよね
2022/07/03(日) 00:37:25.46ID:QOwa7lEj0
水色の自分にとってはEが面白くて、頑張って解いたらレート上がって楽しい回だった
2022/07/03(日) 01:19:00.41ID:dJxTMHTHd
Bはchokudai作問だったか
確かにC問題の難易度だよなあこれは
2022/07/03(日) 11:20:46.08ID:Rs7jP0Dp0
B問題はdiff200くらいにしてあげるのが新規ユーザーも心折れずに、それでいてチャレンジできるから良いと思うの
2022/07/03(日) 14:22:50.28ID:hxbvIGfm0
競技プログラミングって実際にはプログラミングというより
基礎学力、算数の力を問うようなものだろ

実際超有名進学校の生徒が多いし
2022/07/03(日) 14:29:42.99ID:Rs7jP0Dp0
>>437
そもそも競技プログラミング(計算機科学)は数学の一分野
439デフォルトの名無しさん (ｱｳｱｳｳｰ Sacf-pVYn)
垢版 |
2022/07/03(日) 14:58:10.18ID:1KIWm0Nxa
>>436
diff200くらいだろうと思ってb問題にした結果です
2022/07/03(日) 15:47:20.27ID:xNYzPTaMM
昨日のBは実際難しかったね
あまり競プロ界隈は読解力で差がつくということを認めない傾向があると思う(実際は高校生大学生レベルでもそこで差がつく層はかなり多い)
2022/07/03(日) 15:48:33.58ID:nkFK6+7OD
今回の問題ってどこでみられるの？
2022/07/03(日) 15:58:23.62ID:IXB6SZhb0
何の？
2022/07/03(日) 16:00:50.97ID:IXB6SZhb0
PAST？
2022/07/03(日) 16:34:44.10ID:Rs7jP0Dp0
>>439
chokudaiさんだっけ？B問題作ったの
確かにただのループだけで解けるならdiff200くらいで済んだかもしれんが
マスの外に飛び出しても良いってのが難易度上げちゃったんだろうな
2022/07/03(日) 16:48:15.83ID:yePQN0kk0
不馴れだと8方向それぞれループ書くことになるし
2022/07/03(日) 17:13:36.48ID:etWgu0oL0
Bはcodeforces div3, 4あたりで頻出だし個人的に簡単だったけどAtCoderだけやってる人は実装めんどかったと思う
2022/07/03(日) 18:32:00.12ID:IXB6SZhb0
atcoder は実装弱いって話はホントなの？
2022/07/03(日) 19:52:33.29ID:xNYzPTaMM
chokudaiがそんなこと言ってた気がする
基本的に考察できたらすっきり解けるパズルが多いみたいな
449デフォルトの名無しさん (ｱｳｱｳｳｰ Sacf-pVYn)
垢版 |
2022/07/03(日) 20:10:53.34ID:zNseTisNa
O(1)の数学問題はめっちゃ解かれるよね
文系の俺、順位表のAC数見ていつも涙目
2022/07/04(月) 01:59:20.22ID:9+t2vMmw0
実装強いほうが実務では役に立つんだよな
2022/07/04(月) 02:41:51.56ID:kEQbYpUXa
AHCっていうのがありましてですね
2022/07/04(月) 03:37:12.45ID:nQtKwBZH0
AHC012、ずっと任意の向きの直線考慮しててラスト一時間でようやく縦横だけのほうがスコア出るってたまたま試して気付いたんだけど、
初期から縦横だけでやった人はどうやって縦横だけで十分って気付いたの
2022/07/04(月) 08:49:23.91ID:d0tcxAJN0
エンジニア力を養成するためにコンテスト途中で仕様変更があるatcoder
2022/07/04(月) 09:57:21.03ID:OGisvC6Y0
実装弱者だから、斜めの線引いたときのスコアの計算方法が分からなかったんだよ
455デフォルトの名無しさん (ﾜｯﾁｮｲ 1f3e-A/OY)
垢版 |
2022/07/04(月) 11:32:45.33ID:DTICoLLo0
任意の向きで考え始めると時間かかるからとりあえず縦横に制限すれば楽だな→意外と点取れるな
って感じだったが
苺はランダムだから、まずは直線の向きどうこうよりは囲んだ面積のほうが個数に寄与しがちだと思った
2022/07/04(月) 12:20:49.27ID:Zs7eA4JI0
まともにスコア計算を高速化できない方針に短時間コンで手を出すべきじゃないんだよな
となると縦横が第一候補になるのは自明じゃないか？WaveletMatrixとか使えるのだから
2022/07/04(月) 13:46:55.02ID:7jOuGy8qa
色々ありがとう
初手とりあえず広めに解を取ってしまいがちなんだがもうちょっと色々考えてみる
2022/07/04(月) 19:20:57.03ID:9IzbeOYI0
アルゴは解けなかった問題を解けるようにする/解ける問題を速く解く、で強くなれるけど、
ヒューリスティックはどうやったら上位勢との差が縮まるのか分からん
2022/07/04(月) 19:48:18.96ID:8BT+wSuCa
そういうのこそ社長に聞いてみるべき
2022/07/04(月) 22:30:23.09ID:d0tcxAJN0
焼きなましや山登りは試行回数が命だからアルゴが役に立つとか言ってたな
2022/07/05(火) 01:35:39.97ID:GAzz5U460
だめだdiv2のD全然分かんねえよ爆死だわ
2022/07/05(火) 18:09:30.73ID:prrLE4lfM
ヒューリスティック頑張るとしたらやっぱりマラソンマッチの過去問やりまくるとかがよかったりするんだろうか
2022/07/05(火) 18:21:19.46ID:uWVVskU40
一問やりこむことのが大切な気がする
2022/07/05(火) 20:18:56.64ID:U81slK7hd
あっとこ黒字化したんだな
2022/07/06(水) 10:01:44.04ID:nHn2EtC00
自身が解けない問題をしっかり理解するきっかけになるからあえてレートよりdiffが高い問題を解説したら実力伸びる気がしてきた
ただ解説の精度に著しい問題が発生しそう
2022/07/06(水) 11:32:18.18ID:TFlo3lRna
他人の実力を下げることにも貢献して、レート上昇に効果的かもしれない
2022/07/06(水) 13:30:00.62ID:sgQalINg0
自分の色がわかるように書いておけばいいよ
2022/07/06(水) 15:29:05.91ID:3cnNEXq60
競プロ得意じゃない人が競プロ解説するの、実務能力のない層がプログラミング教材作って荒れてる駆け出しエンジニア界隈となんら変わりないのでは
2022/07/06(水) 16:44:19.28ID:nHn2EtC00
一色上のdiffくらいなら許されないかな
大筋は公式解説に則れば間違いも少ないと思うし
2022/07/06(水) 16:45:29.66ID:nHn2EtC00
赤は何を解説しても許されるので赤になりたい
2022/07/06(水) 16:51:27.51ID:ARODCn+La
公式解説を解説するだけのメタ解説記事になりそう
2022/07/06(水) 19:22:40.08ID:mnHDMQPM0
黄色か橙くらいあれば diff 関係なく理解さえできれば解説書けそう
それ未満は自分が正しいこと書いてるかの判断もつかなさそう
2022/07/06(水) 19:41:31.34ID:4Vv58caxM
書いた時点でのレートもつけとけば別に書くの自体はご自由にという感じだけど
2022/07/07(木) 00:07:45.78ID:/roehicAa
そもそもインターネットを汚さないでください
勝手に書くのはもちろん自由だけど公開せずに非公開のまま独りで満足してね
2022/07/07(木) 00:09:11.12ID:/roehicAa
寒色の人に限ってはすべてこのようによろしくお願い致します🙇
476デフォルトの名無しさん (ﾜｯﾁｮｲ 5301-A+Eo)
垢版 |
2022/07/07(木) 00:59:43.89ID:Kgc1E1s+0
表現の自由
はい論破
2022/07/07(木) 09:11:59.86ID:Y2KBdQwir
これでqiitaに2色上の問題解説してるやついたらスレ民バレしそうだな
ちょっと温めとこ
2022/07/07(木) 13:07:08.85ID:kxkoo7YLM
炎上、身バレに対する一番の対処はやっぱり沈黙なんだな
2022/07/07(木) 19:20:49.65ID:pMItU7emM
ムイタerの集合とマイタerの集合は背反なのでム板に書き込んでることがバレてもノーダメのはずです＞＜
2022/07/08(金) 08:30:17.25ID:P1nKRhfu0
蟹江ってどこに行ったんだ
最近聞かないにょ
2022/07/08(金) 12:18:03.13ID:46+3h4xWM
猿者は追わず
2022/07/08(金) 12:56:56.89ID:LM2Uaqtka
阿部ちゃん大丈夫かな🙏
2022/07/08(金) 13:22:08.42ID:P1nKRhfu0
俺の晋三...😭
2022/07/08(金) 18:21:57.29ID:hzgkjgK+a
R.I.P.
2022/07/09(土) 09:53:33.21ID:qeNi5QTkd
うにくんtwitterやめたの？
2022/07/09(土) 11:49:08.07ID:r6KtyWWL0
普通にアカウントある気がする？
2022/07/09(土) 16:37:11.12ID:wzgPzeMJa
喪に服して賞金はしばらく廃止しよう
2022/07/09(土) 17:00:44.03ID:ucqHkj0i0
最近発言やばかったしやめたほうがいいと思う
2022/07/09(土) 17:08:08.98ID:w9T+I5n8a
安倍の死を悲しむべきかくんの復活を喜ぶべきか
2022/07/09(土) 17:08:36.83ID:w9T+I5n8a
うにくんって社会人なの？
2022/07/09(土) 17:20:53.89ID:r6KtyWWL0
最近か？
酔ってる時はずっと発言ひどいイメージだけど
2022/07/09(土) 18:56:18.24ID:uSQvYEtC0
>>489
コンテストに出て「実力を発揮できないパフォーマンスだった」と病むんだから全然めでたくねえよ
2022/07/09(土) 19:01:47.33ID:OVm+Z0x10
競プロやるな、まずはvimをやれといわれたけど本当ですか
手がホームポジションから離れるだけのロスですら命取りらしい
2022/07/09(土) 19:05:19.85ID:r6KtyWWL0
emacsかVScodeしか勝たん
495デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-h6Ny)
垢版 |
2022/07/09(土) 19:10:30.74ID:/7QgEttWa
>>493
ABC卒業したらそういうところも気にする必要あるのかもね
496デフォルトの名無しさん (ﾜｯﾁｮｲ 239f-GdaO)
垢版 |
2022/07/09(土) 19:13:04.46ID:uSQvYEtC0
競技プログラミングで思考が入力に追いつかないなんて入力が遅すぎるか本当に天才的に冴えてるかどっちかじゃない？
2022/07/09(土) 19:53:07.35ID:1keNAONba
そもそも競プロよりvimのほうが役に立つから合ってる
2022/07/09(土) 20:16:03.63ID:OVm+Z0x10
言語の勉強よりもvim優先のほうがいい？
2022/07/09(土) 20:20:39.59ID:1keNAONba
お前が何をやりたいのか知らんけどやりたいことをやるのがいいよ
2022/07/09(土) 20:54:05.53ID:iLKCZgT10
ど偉い人が不遇な亡くなり方をしてしまいましたね
自粛してABCに参加します
2022/07/09(土) 21:19:21.99ID:lQ9GpzMN0
参加できなかった…
502デフォルトの名無しさん (ﾜｯﾁｮｲ 55e6-BXm0)
垢版 |
2022/07/09(土) 22:01:50.75ID:xBP8FTI+0
許さんぞ　チーのもの
チーのもののくせに大それた事を
気分が悪くなったわ
503デフォルトの名無しさん (ﾜｯﾁｮｲ 55e6-BXm0)
垢版 |
2022/07/09(土) 22:02:51.98ID:xBP8FTI+0
犯人見て思ったこと
現実では関わりたくもねー　チーのもの
2022/07/09(土) 22:25:29.74ID:lQ9GpzMN0
tourist敗れる
2022/07/09(土) 22:51:40.06ID:uSQvYEtC0
ユーザー解説を書いて認められたいって承認欲求が病む原因だからやっぱTwitterを復活させるべきじゃなかった
2022/07/09(土) 23:04:01.48ID:XnT0XzQU0
検索汚染をやめろ委員会が発足されてしまう
507デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-2HoA)
垢版 |
2022/07/11(月) 10:47:09.75ID:1W23UOpta
>>468
競技のコード観てると汚いのが多いし
そういうのが勝ってしまうのもどうかと思う
508デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-wDuZ)
垢版 |
2022/07/11(月) 16:27:58.25ID:NjyTZsvXa
touristのコードとか綺麗やけどな
2022/07/11(月) 17:26:51.63ID:Fv5uTKOO0
そもそも与えられた課題に答えさえすればいい
しかもACしたら見返す必要はない
2022/07/11(月) 17:34:30.05ID:TgxWuk/E0
競プロにとってのコードは計算用紙みたいなものだから、汚してなんぼのもん
2022/07/12(火) 01:17:52.96ID:VRn1IBCdM
100行もない、自分以外に理解させる必要もないコードについて、速度優先して汚く書くのも無駄な工数をかけないという実務感覚の一種だと思うよ
2022/07/12(火) 03:34:08.05ID:PR0yudl9a
実務じゃないような気がするがｗ

綺麗さ云々いうなら、コードの綺麗さを競うカテゴリー作れって働きかければ～
2022/07/12(火) 06:18:50.74ID:KZunHuJm0
コーナーケースを潰すために書く分岐処理とかはしっかり検討すればこれもっと綺麗になるなとコンテスト後に提出したコードを見て気づくかな
2022/07/12(火) 09:49:50.85ID:nuTe4rEL0
tourist のコード(マクロがほぼない)を実務erの視点で見たら変数名が短いこと以外にどんなところがダメなんや？
アルゴリズム部分はかなり洗練されてると思うけど
2022/07/12(火) 19:15:55.14ID:s2SMihWRd
・情報系の枠を増やすのが急務。なぜなら進振りで行けないから(東大ローカル事情)
・枠を増やすのが急務だけど新しい大学はレベルが低いから不可

めちゃくちゃじゃね？
2022/07/12(火) 19:46:25.78ID:yS6SynVl0
めちゃくちゃだね
誰がツイートしてるのかしらんけど灰かな
2022/07/12(火) 20:25:50.94ID:AfL+QIri0
AtCoderやったこと無さそうな発言だわ
2022/07/12(火) 21:51:24.91ID:KZunHuJm0
これは思考力灰
2022/07/13(水) 14:52:48.71ID:q3tkBlqX0
>>514
変数名はむしろちゃんと付けてる寄りな気がするけどな

後は575やめて適当な長さで関数に切り出してコメント付けとけばレビュー通る気がする
2022/07/13(水) 20:56:55.23ID:AX+MGypu0
vimとsublimeだったどっちが有利ですか？
言語の勉強の前に先にエディタをマスターしようとしています
2022/07/13(水) 21:09:56.57ID:MPzA+fCP0
スレチ
2022/07/13(水) 21:34:02.13ID:hq1XzdaG0
Sublimeはさすがにもう選ぶ理由が少ないよ
VSCodeより軽いけど、vimにもVSCodeにも機能面で劣る
というわけで勝手にvimとVSCodeの比較のつもりで話すけど
マスターするっていえるぐらい気合があるならとりあえずvim使ったら？

そもそもどっちも使えるようになっておくといいけど、気合があるうちにvimに慣れておくといいよ
VSCodeはマスターっていうほど気合を入れることなく、お手軽に使えるようになるだろうし
523デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-h6Ny)
垢版 |
2022/07/13(水) 22:12:05.84ID:kDIyIUura
前からエディタの話ばっかりしてるアホが一人おるな
しかも聞いてばっかで実行しようとしない
2022/07/13(水) 23:47:21.67ID:o2q7eQWB0
エディタ選びで数日かけてるなら競プロも業プロも向いてない
2022/07/14(木) 00:16:04.57ID:1tikFi/NH
訊くだけで自分で触らないなら競プロ不向き
2022/07/14(木) 00:48:20.54ID:iszQ3CPQa
つまり競プロerよりも幸せになれる可能性が高い
2022/07/14(木) 00:49:42.10ID:8VDot5Ctr
一理ある
2022/07/14(木) 20:31:38.30ID:NLVyz3+vM
sublime初めて知ったわ
2022/07/14(木) 21:08:30.03ID:Q7iUcQr30
このスレ以外とｶﾞｯｸｼワッチョイの書き込み無いんだな
お前らネットリテラシーあるやん
2022/07/15(金) 16:20:08.54ID:N7TmGlR1M
そりゃニートだし
531デフォルトの名無しさん (ｱｳｱｳｳｰ Sa39-cI5m)
垢版 |
2022/07/16(土) 22:47:03.67ID:sS1IvH3Pa
apiadのwinning runかと思ったらtouristまさかのまくりw
2022/07/17(日) 12:21:37.93ID:2EZghsjw0
またネトストスレになったね
正当性のある言い分ならリプで言えばいいのに
2022/07/17(日) 12:23:34.31ID:se832qtyr
またネトストスレ監視スレになったね
正当性のある言い分なら本スレで言えばいいのに
2022/07/17(日) 12:27:55.74ID:2EZghsjw0
ネトストスレ監視スレになったこと一回もないだろ
うまいこと言えてないよ
535デフォルトの名無しさん (ｱｳｱｳｳｰ Sa39-q/r2)
垢版 |
2022/07/17(日) 15:22:17.42ID:ryq1q+OZa
必死すぎウケるw
2022/07/17(日) 16:37:45.81ID:2EZghsjw0
てかマジで誰かリプで言ってやれよ
なんで引用RTしか無いんだよ
2022/07/17(日) 17:02:22.89ID:C/KYDjvE0
今リプしにいったら5ch民だってバレるだろ
538デフォルトの名無しさん (ﾜｯﾁｮｲ 9501-mMB8)
垢版 |
2022/07/17(日) 17:07:51.34ID:lP/cgJhX0
まともな感性のフォロワーならとっくにミュートしてるはずだし、誰もリプしないのはそういうこと
539デフォルトの名無しさん (ｱｳｱｳｳｰ Sa39-3/et)
垢版 |
2022/07/17(日) 20:01:31.85ID:qEPC/5M0a
もう彼のフォロワーお気持ち表明楽しみにしてる奴しかいないでしょ
2022/07/17(日) 20:12:15.60ID:N/bBsi+20
ARCやこどふぉの話題がねえ
自分はtwitterで書き散らして終わるのでこっちに書き込まなくなってしもたが
2022/07/19(火) 12:42:52.06ID:9UJCSIy8M
AGC1回分の作問で40万円か
率直に言うと割に合わないし夢がないと思ってしまった…
542デフォルトの名無しさん (ｱｳｱｳｳｰ Sa39-q/r2)
垢版 |
2022/07/19(火) 13:54:24.18ID:f5ehd13Ra
いや、十分じゃね？
Agcは全く収益産まないんだから年間240万円ドブに捨ててるようなもんだろう
2022/07/19(火) 14:00:43.73ID:XbsFgEwYd
ABCは5000円くらい？
2022/07/19(火) 14:54:56.99ID:g/jinM1i0
ABC8問作って5000円だったとしたらキツすぎる
2022/07/19(火) 15:21:30.22ID:myejtxI+0
慣れた人がやると時給2000円くらいにはなるんじゃないの？
546デフォルトの名無しさん (ｱｳｱｳｳｰ Sa39-q/r2)
垢版 |
2022/07/19(火) 16:05:16.13ID:f5ehd13Ra
点数*10円くらいちゃうのかな
efで差つけろって話題のときそんな話が出たような
547デフォルトの名無しさん (ﾜｯﾁｮｲ 0d01-qysg)
垢版 |
2022/07/19(火) 18:55:50.22ID:S8bArn500
PスポーツとかPリーグとかできるんかね。
2022/07/23(土) 22:44:50.78ID:fbrwkkWxM
GとEx逆転は珍しい
Gで崖ができると今度は青ぐらいの人が被害食らうな
2022/07/23(土) 23:22:42.93ID:fbrwkkWxM
G解説を読んだ
状態の持ち方さえ決めてしまえば飛躍はないけど、この状態の持ち方を思い付いて実装してみようって気がなかなか起きなさそうだし、やっぱり難問だな
なまじGっていつももっと簡単に解ける印象だし
2022/07/23(土) 23:43:52.52ID:bsZUQ/BH0
Eをセグ木でやる方法、各作用が要素数4のモノイドの直積になっているからできないことはないけど、そこまで考察が進んだ累積和の要領でやるのが自然かな
2022/07/23(土) 23:44:30.09ID:bsZUQ/BH0
>>550
進んだ→進んだら
2022/07/23(土) 23:50:53.24ID:fbrwkkWxM
よく考えたら直積モノイドなのか
あまり考えずにビットごとに処理したわ
2022/07/24(日) 00:15:12.14ID:bLfBSwEb0
普通に解いたら別に結合律とか考えなくていいからね
2022/07/26(火) 14:12:21.73ID:aCXouxV/M
chokudaiがアルゴリズム力不足を感じるようなタスクに取り組んでいるみたいだけど、なにをしているんだろう
2022/07/26(火) 15:21:18.78ID:m36KkBXx0
代表だし単にやることをたくさん抱えてるだけじゃないのかなあ
556デフォルトの名無しさん (ﾜｯﾁｮｲ 5101-R4TS)
垢版 |
2022/07/26(火) 17:08:10.61ID:IrL7txwd0
・フリーランスに立ちはだかる「常駐」の壁。慣例を打ち壊し、
“テレワーク”案件3割→8割へと成長を遂げた「クラウドテック」の軌跡
・リモートワーク求人専門サイト「プロリモート」がリニューアルオープン、
　業務委託契約の求職者と企業をマッチング　
・1/3以上が採用につながる高マッチング率、リモートワーク×エンジニア・デザイナー専門の
　人材紹介サービス「ReworkerAgent」正式リリース場所からも時間からも自由な働き方を実現！
・『ReWorks（リワークス）』リモートワーク特化型転職サイトとして 3月5日 リニューアル
・副業・兼業マッチングサービス「クラウドリンクス」登録者数2万人突破
　中小企業で進む副業人材の採用、96％が継続採用を希望
・フリーランスが活用できる「最大1,000〜3,000万円・補助率50%〜75%」の
『ものづくり・商業・サービス補助金』とは？概要や条件を解説
・茨城県日立市、県外からの「テレワーク移住者」に最大151万円の助成金
・長野市、市内に移転・事業所設置し、移住することで最大550万円の支援金を支給
557デフォルトの名無しさん (ﾜｯﾁｮｲ 5101-R4TS)
垢版 |
2022/07/26(火) 17:08:39.28ID:IrL7txwd0
フリーランス向けエージェント「クラウドテック」会員数8万人突破
〜働きやすい環境構築のため、単価向上・全年齢の活躍の場創出・
地方企業のDX推進の取り組みを強化します〜

フリーランスエンジニア専門の案件一括検索サイト「フリーランススタート」、
累計掲載案件数25万件突破！リモートワークの累計掲載案件数35,000件突破！

新規人材の80%がフルリモート希望！　IT人材市況動向レポート2021年12月版を公開

人口移動報告　家賃高い、首都圏脱出　「コロナ禍、仕事フルリモート」

クラウドテック、地方企業向け『クラウドテックDX』を開始、
7万人を超えるDX人材が、地方の非IT企業のDX推進を支援

新潟県、移住してきたテレワーカー／フリーランスに最大50万円を支給

テレワークの一般化により、11月にはテレワーク可能案件83.7%へと増加。
2021年、フリーランスのトレンドは「移住＆テレワーク」と予測
2022/07/30(土) 23:16:04.03ID:/e5auuua0
E がさっぱりで参っちまう
2022/07/30(土) 23:22:15.77ID:uh8qQW+AM
D解説読んだら化かされた感があるな
なんか前見た覚えあるのになんで思いつかなかったんだ
560デフォルトの名無しさん (ﾜｯﾁｮｲ fa10-NdPv)
垢版 |
2022/07/31(日) 22:51:55.95ID:CJUWmQJb0
E全然分からなかった
解説見たらへえって感じだけど、なんで急に赤色の頂点の次数の総和を考え出すの？
解けた人の考え方聞きたい
2022/07/31(日) 23:00:49.66ID:FStFDS540
模範解答的な思考過程は知らんけど、
ある頂点1つに着目してそこを塗ったときに、色が異なる辺が増えるかどうかを考えたら気づいたぞ
周囲の頂点が赤色だとしても青色だとしても同じやんってな
562デフォルトの名無しさん (ﾜｯﾁｮｲ fa10-NdPv)
垢版 |
2022/07/31(日) 23:15:59.14ID:CJUWmQJb0
んー、腑に落ちない
教えてくれてありがとう
2022/07/31(日) 23:17:46.51ID:BkLcBR9X0
隣接した頂点を塗ってみたら偶奇が打ち消し合っているように見えて、絶対これ使うやろと思って睨んだら出た
564デフォルトの名無しさん (ﾜｯﾁｮｲ fa10-NdPv)
垢版 |
2022/07/31(日) 23:30:20.86ID:CJUWmQJb0
お絵描きして考えてはいたんだけど、何も見えてこんかった...
2022/08/01(月) 00:59:16.72ID:az5bV7Pn0
違う色の頂点間を結ぶ辺の数そのままだと上手く解けなかったので、
他の扱いやすい数との関係を考えてたら次数合計と偶奇が同じことに気付いた
2022/08/01(月) 01:26:59.80ID:/yOF1YamM
Eは爆速で解いてる人たちがいたからどうせ簡単な解法なんだろうと思って次数の遇奇だけでできないか考えたら行けた
2022/08/01(月) 01:31:16.33ID:IUF0b1bQ0
>>565
ああ、解けてたからあまり気にしてなかったけど、解説のやつそういう意味だったか
やっと理解した

たしかに解説の流れだとなんでそれに気づくんねん、って感じするが、
まあ求める辺の数と次数にさえ着目できれば気付けるね
2022/08/01(月) 17:18:40.65ID:GPsg5YsiM
いろんなことにいっちょ噛みして語りたい人という印象を受けたな
他の質問を見たら蟻本を知ってそうだし、全く知らずに言ってるわけでなさそう
ただプレイヤー目線ではなくて、競技経験自体はあまりなさそう
https://jp.quora.com/AtCoder%E3%81%A7%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E5%AD%A6%E7%BF%92%E3%82%92%E3%81%97%E3%81%9F%E3%81%93%E3%81%A8%E3%81%AF%E5%B0%B1%E6%B4%BB%E3%81%A7IT%E6%A5%AD%E7%95%8C%E4%BB%A5/answers/367992068?ch=10&oid=367992068&share=cfedb6e5&target_type=answer
ところで、同姓同名の東大の情報系教員がいるみたいだけど、これ本人？
内情erいる？
2022/08/01(月) 17:40:04.17ID:IUF0b1bQ0
>>568
https://jp.quora.com/%E5%A4%A7%E5%AD%A6%E6%95%99%E6%8E%88%E3%81%AE%E6%9C%80%E7%B5%82%E8%AC%9B%E7%BE%A9%E3%81%A7%E5%8D%B0%E8%B1%A1%E3%81%AB%E6%AE%8B%E3%81%A3%E3%81%A6%E3%81%84%E3%82%8B%E3%82%82%E3%81%AE%E3%81%AF%E3%81%82%E3%82%8A/answers/325721043
2022/08/01(月) 17:40:31.26ID:IUF0b1bQ0
　　 ＼　　　丶　　　　　 　 i.　　　 |　　　　　　 /　　　 　 ./　　　　 　 ／
　　　　＼　　　ヽ　　　　　　i. 　　 .|　　　　　　/　　　　 /　　　　　 ／
　　　　　 ＼　　　ヽ　　　　　　　　　　　　　　　　　　　　　　　　／
　　　　　　　　　　　　　　　　　わ　た　し　で　す　
　　　＼　　　　　　　　　　　　_,, 　---一 ー-　,,,_
　　　　　　、　　＿,,,,　＿,, -.'"　　　　　　　　　　　`　、　　　　　　　　　　　-‐
ー　　　　　ミ三ﾐ三ミ三ﾐミ　　　　　　　　　　　　　　　　ヽ_,
　　　　　-=＝三ミ彡三ミﾐ　　　　 ,,=-＝=　　　　　==、　iﾐ=-、＿
　　　　　＿,,ンミミ三ﾐ三ミﾐ]　　-彡-一 ー-、　r一 ーミ、|ミﾐ三ﾐ=-'　　　　　　--
_＿　　　_, -=＝彡ミ彡ミﾐミ|　 ン|　,=て)>　(|ー|　,て)>、　||三ミ彡＝=-'
＿　　　　　,彡彡三ミ三ミﾐレ'~　.|. '　　　　　|　 ヽ　　　`　 |ミ三彡三=-　　＝　二
　　　　　（＿彡三ミ彡ミミﾐ'　　　ヽ、　　　 ノ　　　＼＿＿ﾉiミ彡ミ三=ー
　　　　　ー-=二三ンーﾐミﾐ　　　　 `ー /(＿r-、r-_）　　　.|彡ミ三＝-、
　　　　　）（＿ミ彡ﾐ| i' ヽヽミ　　　　　　 | : : : __ : :__: :i　　　.|彡ミ三=-、　　　　　--
　　　　　と彡ミ彡ミヽヽ<ヽﾐﾐ　　　　　　|: ﾝ＝-ニ-ヽ、　　 .|彡ミ三＝=-
　　　　　　彡ミ彡ミミヽ 　)　`　　　 、　.' <=ｪｪｪｪｪﾝ |　　　 |彡ン=-＝　　　　　　--
-‐　　　　-=＝彡三ﾐ `ーヽ : : : : : :i: :　　`ー--一''　　: : ﾉミ三＝=''
　　　　　　''　てノこミ彡三ﾐ`i : : : : : :ヽ: : : .　　　　　　.:, :/ミ三=-、
　　　　 　　　''　三ミ＝三三ﾐ|ヾ、: : : : :ヽ: : : : : : : : :_ノ:./三=-'
　　　　　　　　　-=＝''￣　.　　　　　　　　:￣￣￣　　　　彡 `
／
　　　　　　　　　　　　　　　/　　　　　　　　　　　　　　　ヽ　　　　　　　　　 ＼
　　　　　　／　　　　　　　　　　　　　　　　　　　　　丶　　　　　　 ＼
　　　　 ／　　　/　　　 /　　　　　　|　　　　i,　　　　 　 丶　　　　　　＼
　　　／　　　 /　　　　/　　　　　　 |　　　　 i,　　　　　　　丶　　　　　　　＼
2022/08/01(月) 17:42:48.96ID:Zno8edUi0
モノホンなら真面目に相手しちゃいかん
またなんか言うてるわ程度で流しとけ
2022/08/01(月) 18:50:10.35ID:GPsg5YsiM
>>570
このAAにあえて寄せに来てるだろってぐらい似てて草
573デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-546A)
垢版 |
2022/08/01(月) 19:33:03.00ID:wZgy5UePa
アピールできるのギリギリ黄までってすごく真っ当では
水なんて4級やろ？
囲碁や将棋に学生時代打ち込んで4級になりました！
ってアピールされたらどう思うんよ
2022/08/01(月) 21:23:05.76ID:rc336Zuv0
逆に赤橙だと競プロしかやってこなかった奴だと思われん?大丈夫?
2022/08/01(月) 22:27:23.59ID:Zno8edUi0
他の事も話せばいいんでないの
2022/08/01(月) 23:20:01.30ID:GPsg5YsiM
本当にそれだけしかない人なら暖色上位あった方がいいのかもしれないけど、one of themとして使うんなら別に緑とか水でも十分だと思うけどね
大手企業でも別にそんな新卒はハイスペだらけじゃないよ
2022/08/06(土) 23:12:36.78ID:e9rpaNpfM
Eは昔六問ABCでFの位置に置かれてた問題に似てるな
やっぱりちょっとずつ問題のレベル上げてる？
578デフォルトの名無しさん (ﾜｯﾁｮｲ 9b71-uMN9)
垢版 |
2022/08/07(日) 14:06:05.87ID:92VIw/Wa0
Eをmodとった値になんの意味があるのかｗｗｗ
近似値で良いじゃん
2022/08/07(日) 14:29:12.18ID:/tgNGTe2a
業務でも浮動小数の誤差が嫌なときは確率や期待値に素数のmod取ったりするよ
2022/08/07(日) 22:33:12.42ID:McTfrCXHM
シミュレーションとかでものすごく小さな誤差も気になるときには実際有理数体と有限体のどっちが取り回しがよいんだろうね
そういうのやったことない
2022/08/09(火) 13:47:59.34ID:zJsO1qIpM
トヨタでのバイト、AtCoderとして受託して業務提携でプレスリリースを出すみたいなことはできなかったんかね
いい実績作りな気がするけど
582デフォルトの名無しさん (ｱｳｱｳｳｰ Sa55-7XjG)
垢版 |
2022/08/09(火) 19:25:34.31ID:Uwp36N1Ga
社長がいなくても回るんならもう副社長が社長でいいやん
2022/08/10(水) 14:57:40.38ID:FBU34xC90
AtCoderが受託開発を始めるのはちょっと違うでしょ
2022/08/12(金) 09:27:10.43ID:bPVPTUbD0
アは役！証明できるじゃん
2022/08/12(金) 09:27:31.49ID:bPVPTUbD0
アルゴリズムは役に立つ！
2022/08/13(土) 23:00:37.57ID:Q3YkY08AM
今回は前半の方がいつもより難しめで後半の方は簡単め？
2022/08/13(土) 23:09:04.86ID:1rThskKv0
自称ユーザー解説については、コンテスト中に書いて終了後即座に提出したか、testerが書いた（writerじゃないから非公式という認識？）みたいな感じじゃないか
2022/08/13(土) 23:18:52.37ID:1rThskKv0
切断クエリを逆順に見てUnionFindによる結合に読み替えるやつ本当にABC-Eって感じのテクニックだな
2022/08/14(日) 00:07:55.47ID:JkLDfijlM
今さらだけどchokudaiが忙しい理由ってトヨタのアルバイターだったからか
590デフォルトの名無しさん (ﾜｯﾁｮｲ e5da-lLTM)
垢版 |
2022/08/14(日) 15:11:07.66ID:3gxKNbVN0
0012 仕様書無しさん 2022/07/02(土) 21:05:02.67
prog：プログラマー［重要削除］
https://ace.5ch.net/.../saku2ch/1032017835/

230 上奥　龍 (ﾜｯﾁｮｲ d58e-sbT5 [182.171.118.130]) mistery0817@gmail.com 2022/07/01(金) 13:06:33.82 ID:9RE/ovUm0
対象区分：［個人・三種］優先削除あり
削除対象アドレス： https://medaka.5ch.n.../prog/1655625352/811
https://medaka.5ch.n.../prog/1655625352/813
https://medaka.5ch.n.../prog/1655625352/861
削除理由・詳細・その他： 811番のレス・813番のレスに対しては[個人名・住所・所属]の二類に属する情報が掲載されているため、削除申請を行います。
861番のレスに対しては[個人名・住所・所属]の三群に所属する情報であると考えていますが、
インターネット上のURLが掲載されている状況です。
そのURLには、個人名並びに私の昔の写真が掲載されております。
しかし、スレッドの議論の状況から誹謗中傷の個人特定が目的である情報であると考え、削除申請をさせて頂きます。

以上3点のレスが削除申請を行うものになります。よろしくお願いします。

231 Dele Ace ★ 2022/07/01(金) 16:49:02.69 ID:CAP_USER
>>230
見ました。
URLリンク先に問題がある場合はリンク先に削除を依頼して下さい

958 仕様書無しさん 2022/07/02(土) 19:03:13.41
>>894
ご尊顔
https://www.ds.shiga.../news-faculty/p7102/
2022/08/15(月) 00:10:08.26ID:P9utAIwR0
1完ちょっと早め解きでおそらく微減...
でもまだARCどころかABCですらギリレート上がる範囲だから悲壮感はない🤗
よくやったほうだ😎
2022/08/15(月) 00:13:42.71ID:P9utAIwR0
B方針は割と合ってる😭
2022/08/15(月) 00:15:58.63ID:P9utAIwR0
もう政治の話する人と金玉ネタ擦ってるキッショい誘導しかおらんのか
2022/08/15(月) 00:27:35.29ID:kI762SvKM
AGCはやっぱり赤コーダー用コンテストだね
2022/08/15(月) 00:34:12.32ID:wLqUUm+w0
ABが解けて2800-2000だから
黄青にはいい難易度だった
2022/08/15(月) 00:43:08.18ID:kI762SvKM
180分のコンテストでB早解き競争ってしょっぱくない？
2022/08/15(月) 00:44:28.68ID:kI762SvKM
ああ、青だと確かにそうか
2022/08/15(月) 00:45:29.88ID:DNbe8aKk0
競争っていうほど簡単じゃないぞ・・・悔しい
2022/08/15(月) 10:28:16.89ID:duOqXhxOM
アドホックで難しくて分かれば綺麗に解けるような問題が都合よく無尽蔵に作れる保証はない以上、AGCもそのうち考えたことがあるor見たことがある勝負に帰着するのかもな
2022/08/15(月) 10:50:14.74ID:P9utAIwR0
遂に異常精進erが黄色止まりじゃなくなる時代なのねん
2022/08/15(月) 22:34:51.82ID:sKjgT8Sq0
情けない話だが AGC より ARC, こどふぉ、インドのが楽しい
2022/08/20(土) 20:32:01.58ID:cw0JDlJG0
3-5-6-8-8-12か
なんとか四完したいなー
2022/08/20(土) 23:31:30.88ID:cw0JDlJG0
四完どころか二完遅解き…
Cで玉砕しました…
2022/08/24(水) 15:11:08.87ID:XjPDH9lUM
・ ｢1万時間の法則｣の元ネタ（被引用数: 9847）、再現されず。むしろ、一番上手なグループは累積練習時間が少ない傾向

競プロer的にはやっぱこれが大きいな
2022/08/24(水) 20:34:14.85ID:uvR7jnPXr
山上義士の話ししてええか？
606デフォルトの名無しさん (ｱｳｱｳｳｰ Sa63-ngAI)
垢版 |
2022/08/25(木) 09:21:20.76ID:H6ZjYSuOa
山上徹也の話だったらしていいよ
2022/08/26(金) 13:34:27.44ID:GQPfjH410
政治erもみんなこっちにこないとダメそうだな・・・
2022/08/26(金) 13:37:09.06ID:0L95KBLp0
ホモラーも来たら面白くなるな😄
2022/08/26(金) 17:28:13.38ID:pYnL3GXk0
こっちならワッチョイでNGすれば1週間は見えないからありがたい😎
2022/08/27(土) 20:53:33.09ID:ZPoFPdWM0
ABC出ます
2022/08/27(土) 22:52:05.61ID:hkrAFGwB0
Exって一種の実家DP？
2022/08/27(土) 23:11:30.79ID:3wy+ENA+M
二次元セグ木、存在は知ってるけど実装したことないやつだ
2022/08/27(土) 23:56:20.02ID:4L+zG4II0
競プロから離れろ
俺なんてアンレで下がっても得したわくらいにしか思わん
2022/08/27(土) 23:56:46.49ID:4L+zG4II0
間違えてワッチョイスレにくんの書き込みしちゃった😭
2022/08/28(日) 00:15:41.43ID:fzZHjavpr
なんの問題ですか(レ)
2022/08/28(日) 00:50:07.66ID:Mk7rvrNb0
アンレでやらかしたらむしろ得したって気持ちにならねえか？
2022/08/28(日) 15:45:18.47ID:ZVxp6vC5M
のし ゆたか への で一位争い？
618デフォルトの名無しさん (ﾜｯﾁｮｲ bf71-InTp)
垢版 |
2022/09/03(土) 22:43:13.85ID:+ovHgQRj0
２冠、難易度上がりすぎて長年維持してた緑脱落しそうｗ
2022/09/03(土) 23:11:31.53ID:RIPR8ere0
Eってにぶたんが想定なのか・・・
ヒープ使って貪欲にやるほうが自然じゃない？
2022/09/03(土) 23:22:04.35ID:Bj/hTzV0M
どうせこんなん二分探索でしょ(ﾍﾗﾍﾗ)って感じで半端な考察でコーディングしてたら、別に小さい順にとって全然問題ないことに気づいて結局ヒープ貪欲になったな
2022/09/03(土) 23:28:55.16ID:RIPR8ere0
まあたしかに、最大値の最小化だからにぶたんぽい、って思えるか
おれは実験してたら貪欲でいけるってすぐ気づいてしまった
622デフォルトの名無しさん (ﾜｯﾁｮｲ bf71-InTp)
垢版 |
2022/09/03(土) 23:47:53.39ID:+ovHgQRj0
(コスト,インデックス)の配列のヒープでやってたけど中に手を入れられない事に気づいて２分探索にして時間切れ・・・
2022/09/03(土) 23:58:51.45ID:Bj/hTzV0M
更新があったらpushすればいいだけ
更新前の残りカスがpopしてきたら枝刈り
要はダイクストラと一緒
2022/09/04(日) 00:14:55.13ID:HJqqrS490
C++ でいう std::set を持ってくれば中に手を入れられるので……？
625デフォルトの名無しさん (ﾜｯﾁｮｲ 0701-Jj1I)
垢版 |
2022/09/04(日) 00:20:53.96ID:YUzYugU50
ニブたんのイラストが欲しいところ。
2022/09/04(日) 00:28:12.08ID:rmP8KkZTM
G蓋を開けるとそんなに捻りがあるわけでもない挿入DPだな
なんで思い付けなかったんだろう
2022/09/04(日) 13:03:27.94ID:nBwf9QtV0
最近昔よりARCが解けない気がするし、いよいよ俺も過学習erかぁ〜？って状態
頭が悪いのはどうしようもないからあきらめてるけど、CF div1過学習とかでARCはなんとかできる？
628デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-/yQy)
垢版 |
2022/09/04(日) 15:34:08.14ID:x0sSmgMe0
https://ideone.com/JtsEhf

これは以下の問題の解答として書いたものですがパスしませんでした。
どこが間違っていますか?

https://atcoder.jp/contests/dp/tasks/dp_g
629デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-bBdM)
垢版 |
2022/09/04(日) 15:35:21.26ID:x0sSmgMe0
トポロジカルソートを使っています．
630デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-bBdM)
垢版 |
2022/09/04(日) 15:37:44.90ID:x0sSmgMe0
深さ優先探索でのグラフの点への後行順のリバースオーダーがトポロジカルオーダーになるので，
それを利用しています．
631デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-bBdM)
垢版 |
2022/09/04(日) 15:42:05.58ID:x0sSmgMe0
ところで，アルゴリズム専門の大学教授が参加したら強いと思いますか？
632デフォルトの名無しさん (ﾜｯﾁｮｲ 0701-Jj1I)
垢版 |
2022/09/04(日) 15:43:12.14ID:YUzYugU50
むしろ、東京アルゴリズム専門学校を設立すべきでは？
633デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-bBdM)
垢版 |
2022/09/04(日) 15:45:32.52ID:x0sSmgMe0
Erik Demaineとか強そうじゃないですか？
634デフォルトの名無しさん (ﾜｯﾁｮｲ bf2a-qLXA)
垢版 |
2022/09/04(日) 15:49:41.68ID:KvZxXp+G0
>>628
次数が0の頂点からdfsを始めないとqがトポロジカル順にならないかな
あと、PythonとかPyPyなら
import sys
sys.setrecursionlimit(10**5+10)
とかを書かないとREになるよ
635デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-bBdM)
垢版 |
2022/09/04(日) 15:53:52.62ID:x0sSmgMe0
>>634

ありがとうございました．
その再帰のリミット設定を追加したらパスしました．
プログラム自体は変更しなくても大丈夫でした．
2022/09/04(日) 16:04:24.00ID:wXfdv5JvM
後退解析チックなトポロジカルソートしか知らないからそういうトポロジカルソートのやり方は知らなかった
2022/09/04(日) 16:09:15.88ID:wXfdv5JvM
>>633
強い人はめちゃくちゃ強いだろうけど、全般的にそうかは微妙かな
年齢も大きい
アルゴリズムの有名な実力のあるおじいちゃん研究者がこどふぉ水だったりするし
2022/09/04(日) 16:35:59.36ID:nBwf9QtV0
ARCはまだ訓練でどうにかなるレベルらしいから、気長に難問に取り組むのがいいんじゃないか
知らんけど
639デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-bBdM)
垢版 |
2022/09/04(日) 17:36:16.96ID:x0sSmgMe0
>>637

確かに人によって全然違うでしょうね．
極端な場合，プログラミングをやったことがないという人さえいるみたいですし．
640デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-bBdM)
垢版 |
2022/09/04(日) 17:48:11.72ID:x0sSmgMe0
みなさん，アルゴリズムの本はどんな本を読んでいますか？

クヌース
CLRS
セジウィック＆ウエイン
Kleinberg & Tardos

何かおすすめの本はありますか？
2022/09/04(日) 17:58:28.50ID:6TwASNhDp
Cormen
2022/09/04(日) 22:31:48.58ID:9ocqxCfk0
超高速グラフ列挙アルゴリズム−〈フカシギの数え方〉が拓く，
組合せ問題への新アプローチ
ERATO 湊離散構造処理系プロジェクト・湊真一、2015

計算時間が何百億年も掛かるのが、数秒で解けた
「おねえさんの問題」で有名な、
湊真一の超高速グラフ列挙アルゴリズム ZDD

プログラミング・コンテスト・チャレンジブック、第2版、2012
3人の大学院生が、様々なコンテストの問題を集めたもの。g++ 用のC++

オライリーの「入門 データ構造とアルゴリズム」は、インド人の著者

他にはセジウィック、石畑清、川中真耶など
2022/09/04(日) 23:20:29.56ID:nBwf9QtV0
ARCダメだった…
2022/09/05(月) 00:14:34.73ID:KwyAzWVCM
コルテの組合せ最適化の評判はどうなんですか？
645デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-bBdM)
垢版 |
2022/09/05(月) 16:51:34.75ID:POytJmdv0
>>641

ありがとうございます．CLRSですか．第4版が出ましたね．

>>642

『超高速グラフ列挙アルゴリズム』ってトンデモ本ではないんですか？

>>644

その本って，高級な話題を扱っていそうですが，競技プログラミングに結びつきますかね？
2022/09/05(月) 17:51:08.42ID:njTO333C0
こんなところで聞いても灰しかいないぞ
赤か橙に直接聞け
2022/09/05(月) 18:54:43.43ID:bZ4vo4vxM
>>645
コルテ組合せ最適化の内容に関して言うと、LP、フロー、マトロイドはじめ、競プロサイトの中でも知識が要らない方と言われているAtCoderでもそれなりに見るような話も結構扱っているように見える
ただ、それらをコルテで勉強するのがいいのかはちょっと自分はよくわからない
648デフォルトの名無しさん (ﾜｯﾁｮｲ bf71-InTp)
垢版 |
2022/09/05(月) 21:57:07.54ID:o8y8QwPZ0
在庫管理系の面接受けたけど、競プロと関係なさすぎて。簡単な最適化くらい出せば良いのに。
649デフォルトの名無しさん (ｱｳｱｳｳｰ Sa8b-ZRei)
垢版 |
2022/09/06(火) 19:20:46.62ID:t7+pgncea
業務はアルゴリズムとか関係ないからな
プログラマの仕事は基本的にデータベースの出し入れだけ
でも業務知識や設計はなかなかバカにできない難易度だな
650デフォルトの名無しさん (ﾜｯﾁｮｲ bf71-InTp)
垢版 |
2022/09/06(火) 21:25:40.57ID:Kf3p7rj70
いや、アルゴリズム、数理最適化使うんだけどatcoderパズルが的外れすぎて役に立たない。線形計画もラグランジュ法も出さないで何がアルゴリズム人材だと。
2022/09/06(火) 22:19:18.14ID:0qm6A0XY0
まじで！？AtCoder役に立たないの！？
652デフォルトの名無しさん (ﾜｯﾁｮｲ bf71-InTp)
垢版 |
2022/09/06(火) 22:46:39.84ID:Kf3p7rj70
問題にもよるけど昔より難易度上がってるし一般的な業務だったら灰色上くらいで、アルゴリズムっぽいのでもせいぜい茶色くらいまでかと。数え上げとかmod,xorなんちゃらみたいなのがなければもっと上まで役に立つ可能性があるといっても良い気がする。精進は時間の無駄と考えて気楽に参加してる。
AHCのほうはかなり役に立つと思う。
2022/09/06(火) 22:51:12.89ID:wi6f+hdmM
線形計画法の問題とか考察つまんなそう
2022/09/06(火) 23:14:40.13ID:0mlgzznW0
線形計画はよく出てるじゃん
2022/09/07(水) 00:40:38.30ID:P6TFpbuE0
普通にLP解いたりラグランジュ双対とったりする問題は頻出だと思うけど
同じ数理最適化でもニュートン法とかもっと機械学習っぽい連続最適化問題出せみたいな話は分かるが
2022/09/07(水) 00:48:11.56ID:P6TFpbuE0
ただその辺はABC-GとかExとかARC-C以降とかに放り込まれているから、数論や組合せ論系の問題が元から得意じゃないとそこで阻まれてたどり着きにくいというのはそう
657デフォルトの名無しさん (ﾜｯﾁｮｲ bf71-InTp)
垢版 |
2022/09/07(水) 01:27:40.63ID:KXyAg9cX0
え、脳死でソルバーに突っ込んで解けるのがG以降にあるの？
だとしても普通に最適化系の科目をで履修中の人が解ける3-400点程度に押さえてCDあたりで出すべきかと
2022/09/07(水) 02:44:08.46ID:P6TFpbuE0
>>657
いや、さすがにそんな脳死解法が想定解の問題はいくらABCでも後半じゃ出ない
https://atcoder.jp/contests/abc216/tasks/abc216_g
例えばこれは数列をうまく変換して条件言い換えるとLPが出てきて、その双対LPが最短経路問題になってるからダイクストラ法で準線形に落とせるって問題
ソルバーに投げず別のアルゴで解けるようにしないと通らないし、また、LPに帰着させる部分が大体非自明なのがAtCoderで出るLPの特徴
一方、本当に一目でLPだとわかり、脳死でソルバーに投げればいいタイプのLPをABC-Cとかに出せって話もわからなくはない
個人的にはつまらない問題だと思うけど教育的ではある
2022/09/07(水) 03:01:49.65ID:P6TFpbuE0
そもそもAtCoderのアルゴの方のコンテストだと確率的に正解になる解法はコンセプト上想定解にしにくいから、脳死LPが出てくるとしたらソルバーに投げるんじゃなくて普通に頂点全探索が間に合うような問題になるかな
二次元ですら実行可能領域求めるの結構大変だから、ABC-Cで出すとしたらかなりかなりわかりやすい凸多角形にする必要がありそう
2022/09/07(水) 03:03:03.88ID:k+EcBBmh0
ARC128-CのLP感好きだよ
2022/09/07(水) 03:05:01.25ID:P6TFpbuE0
あ、確率的に、というのはTLEの方の話ね
2022/09/07(水) 10:36:39.59ID:+ZV6H66AM
ABC-Cに虚無LP入れたら荒れそうだな
崎になにか教育コンテンツで啓蒙した方がよさそう
2022/09/07(水) 12:43:39.65ID:FwvlQ1D10
2021年以降のARCみたいな問題て他にどこで練習すれば
664デフォルトの名無しさん (ﾜｯﾁｮｲ e733-Iguz)
垢版 |
2022/09/07(水) 16:13:49.50ID:jifeMzUR0
https://atcoder.jp/contests/abc087/tasks/arc090_a
にある
左上および右下のマスにもアメが置かれており、あなたはこれらのマスに置かれているアメも回収します。
ってどういう意味？
単純に通ったマスの飴だけとったらACになったんだけど、問題の意味が分からんかった
2022/09/07(水) 16:33:40.95ID:yQCLjQqS0
スタートとゴールも移動中に通ったマスとみなす
666デフォルトの名無しさん (ﾜｯﾁｮｲ e733-Iguz)
垢版 |
2022/09/07(水) 16:39:19.33ID:jifeMzUR0
そういうことかありがとう
2022/09/07(水) 18:24:50.65ID:P6TFpbuE0
>>664
確かに一瞬、意味が取れなくて(i,j)を通ったら(i-1,j-1) or (i+1,j+1)の飴も回収できてますよ、的な話かと思ってしまった
(1,1)と(2,N)の飴も回収しますとか書いた方が紛れが少なそう
2022/09/07(水) 18:25:54.23ID:P6TFpbuE0
>>663
これは俺も気になる
相性が悪いのかもしれないけど、かなり難しくなってないか？
669デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-CzlZ)
垢版 |
2022/09/07(水) 19:18:51.47ID:pyqwkznf0
競技プログラミングの問題には人間の作者がいるので，それほど独創的な問題を量産できるとは思えません．
とすると，ある程度の訓練を積んだ人間にとっては，同工異曲な問題群に見えるのではないか？

と考えたのですが，あっていますか？
2022/09/07(水) 19:25:51.03ID:lTpXDHBr0
そらそうだよ
数オリだろうが過去問たくさん練習すれば解ける確率上がるからね
671デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-CzlZ)
垢版 |
2022/09/07(水) 19:40:51.71ID:pyqwkznf0
数学オリンピックの問題はおそらく数学者が作っていると思いますが，AtCoderの問題は学者が作っているわけではないですよね？
だとすると，問題の独創性はかなり低いのではないかと推測しますが，あっていますか？
2022/09/07(水) 20:11:10.05ID:lTpXDHBr0
さすがにAGCとかになると作問者もかなりハイレベルだし既出かどうかをチェックする体制などもあるのであまり関係ないと思いますが、作問者じゃないしわかりません
そんなに気になるなら高橋社長に聞いてみたらどうですか
TwitterでもYouTubeでも匿名で質問しても回答をくれますよ
2022/09/07(水) 20:12:27.65ID:lTpXDHBr0
AtCoderの出題者は今のところ、一般の学生、たまに会社員って感じではありますね
2022/09/07(水) 20:22:49.29ID:P6TFpbuE0
別にそんなことはないよ
ABCは典型問題だらけだけど、AGCはかなり独創性の高い問題を出すことを志向している
そもそも数学者としての能力と競プロの独創的な問題を作る能力はそもそも微妙に違う、良くも悪くも
もちろんAGCすら世界10位以内とかのクラスから見たらパターン見えるのかもしれないけど、大体の人だと二十年頑張ってもパターン学習できないと思う
2022/09/07(水) 20:23:20.87ID:P6TFpbuE0
>>674
あ、これは>>671へのレスね
2022/09/07(水) 20:28:55.80ID:P6TFpbuE0
数オリ勢の成績見た感じIMOとAGCだと多分AGCの方が難しいと思うんだけど、実際のところどうなんだろう
2022/09/07(水) 20:31:50.41ID:WXz7nKNF0
ABC224HなんかはLPの定式化は自明でソルバに突っ込んで解いた人もいるらしい
2022/09/07(水) 20:55:25.96ID:P6TFpbuE0
>>677
これソルバ解けるのか、思ったよりLPソルバ優秀だな…
というか想定解の双対とってMCFもかなり見えやすい問題だ
2022/09/07(水) 20:57:18.48ID:lTpXDHBr0
AGCも問題にバラツキあるから、ハッキリとは言いづらいけど、
全年齢対象なのになかなか全完が出ないAGCのほうがやっぱ難しといえるんじゃない？

ちなみに今年の数オリは中国からの参加者は全員が満点を取ったらしい
簡単だったのかな
680デフォルトの名無しさん (ｱｳｱｳｳｰ Sa8b-QAu0)
垢版 |
2022/09/07(水) 22:38:04.79ID:LY9bvG3na
赤コーダーともなれば数学者と変わらんだろ
2022/09/07(水) 23:09:32.31ID:WXz7nKNF0
赤を褒めてるのか貶してるのかわからんな
682デフォルトの名無しさん (ﾜｯﾁｮｲ e733-Iguz)
垢版 |
2022/09/08(木) 00:50:08.86ID:A4rHdGWR0
chokudaiも以前に何かの放送で、新しい問題つくるのがほんと大変だって言ってたな
2022/09/08(木) 01:10:26.92ID:tYYY8KHVr
うんち
2022/09/08(木) 01:10:36.47ID:tYYY8KHVr
あっスレ間違えた
2022/09/08(木) 16:53:49.09ID:/uGN1f4lM
E8くんなにするんだろう
新書籍発売？
新コンテストサイト公開？
2022/09/08(木) 16:56:30.24ID:/uGN1f4lM
まあ大概学問もパターンゲーじゃないか
むしろアドホックな考察力が求められる分野の方が少数だと思うね
2022/09/08(木) 17:47:01.03ID:ebtkaE3x0
典型90の本じゃないのかな
2022/09/08(木) 18:28:42.75ID:T90QpKCS0
あれまだ発売されていなかったのか
2022/09/08(木) 19:37:15.04ID:/uGN1f4lM
>>687
なるほど、そういえば発売まだだったのか
確かにそれが一番可能性高そうだな
2022/09/08(木) 21:04:16.55ID:AKUPUpuB0
E8くんって最近コンテスト出てない？
前のAGC見かけなかった気がするな
2022/09/09(金) 03:58:24.24ID:KcSQBtjOM
E8くん、すごい執筆速度だ
このアウトプット力は素直にすごい
ただ、やっぱりABC-ratedが対象読者みたいで、暖色を押し上げる本は相当難しいんだなと
2022/09/09(金) 11:34:36.68ID:zBJv5lXS0
新しいE8本、俺はヒューリスティックできないからその部分は読もうかと思う
2022/09/09(金) 13:43:54.42ID:kTxh4G5U0
ヒューリスティック蟻本誰か出して🤗
2022/09/09(金) 14:01:12.69ID:eDV4BhqD0
蟻本の著者でもあるwataさんが書いてるこれの解説を読めばよくね？
https://atcoder.jp/contests/intro-heuristics
2022/09/09(金) 14:14:38.24ID:kTxh4G5U0
これ普通に知らなかった
感謝です
2022/09/09(金) 14:21:03.62ID:eDV4BhqD0
でもこのPDF、ビームサーチの解説が「後で追記」のままになってるな・・・
chokudaiに通報したほうがいいね
697デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-CzlZ)
垢版 |
2022/09/09(金) 14:25:44.31ID:kJ4avtf50
競技プログラミングをやっている人で強い人でも、アカデミックな匂いのしない人
が結構いるように思います。
2022/09/09(金) 17:13:05.72ID:zBJv5lXS0
学者じゃないから、そりゃいると思うよ
数学や情報科学が得意な人も少しいるゲーマーコミュニティってだけで
2022/09/09(金) 17:33:18.01ID:zBJv5lXS0
暖色向け本の話だけど、今のAtCoderで黄色より上に上がるのに別にそんなに知識って寄与しないイメージ（というか知識だけならみんなもう持ってる層での競争）で、こういうデ/アの知識を入れた方がいいとか、知らないデ/アの知識を手に入れるにはどうしたらいいのかみたいな話はあんま”本質”って感じがしないんだよな
2022/09/09(金) 18:51:34.08ID:E+8eKKfg0
12年前に蟻本出したってよう考えたらすげえことだな
701デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-CzlZ)
垢版 |
2022/09/09(金) 19:03:35.57ID:kJ4avtf50
何がすごいんですか？
2022/09/09(金) 19:17:01.85ID:zBJv5lXS0
競技プログラミングは独創的な問題に価値を見出しているから、年々新しい問題がたくさん作られているんだけど、未だに12年前の本が中級者（ここでは水〜黄ぐらい？）向けの本としては定評があるから
2022/09/09(金) 19:22:06.29ID:n8dQNxep0
蟻本って、プログラミング・コンテスト・チャレンジブック、第2版、2012 の事か

色々なコンテストから、3人の東大大学院生がまとめた本でしょ。
ほとんど全てのアルゴリズムを網羅している

言語は、g++ 用のC++

読んだ感じ、すごい学生達だと思った。
商売はアイデア。これはニーズがあるから売れると思った
2022/09/09(金) 19:22:54.76ID:zBJv5lXS0
まあ蟻本の知識的な内容を全部理解しててもちゃんと考察力がないと橙にもなれないと思うけど
705デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-CzlZ)
垢版 |
2022/09/09(金) 20:00:57.21ID:kJ4avtf50
>>702
独創的な問題といっても，アルゴリズムとデータ構造の本に書いてある知識で解ける問題ですよね？

みなさんはアルゴリズムとデータ構造の本を読んで勉強しますか？
2022/09/09(金) 20:05:14.26ID:zBJv5lXS0
ある一定レベル以上行くと要求知識と難易度ってそんな関係ないんだよね
小学生でも理解できる単純な貪欲アルゴリズムが解法の問題が永続赤黒木を要求する問題より難しいということがままある
2022/09/09(金) 20:06:03.79ID:pJ7ShlGc0
解けないよ
小学校の計算ドリルじゃあるまいし

AGC解いてみればわかると思うけど、知識は大前提で、それ以上に閃きみたいなのが必要
つまりアルゴリズム知識問題というよりは、どちらというとやたら頭を使うパズルやなぞなぞといったほうがいい
2022/09/09(金) 20:11:55.82ID:zBJv5lXS0
AtCoderに関して言えば、正直、ABCの問題（Exまで）や典型90を解いて蟻本を読むだけでもほぼ知識的には網羅できていて、学術的なアルゴリズムとデータ構造の本を読む必要性があるかというとそこまででもない
ただ、アルゴリズムとデータ構造を題材としたゲームをやっているので周辺知識に興味がある人も多くいて、趣味で勉強している人は結構いる雰囲気
学術的じゃない人もいるけど、学術的なことが好きな人も他より多めだと思うので、そういう人と話してみたら面白いのではないかな
2022/09/09(金) 20:34:07.29ID:yIa0OFzGM
アルゴリズムとデータ構造の網羅性のある教科書の知識があれば知識面では十分問題が解ける水準にあると思う
ただそれには前提があって、発想力がないといくら知識があっても解けない（そしてここの要求水準が結構厳しめ）
って感じかね
2022/09/09(金) 20:37:14.53ID:pJ7ShlGc0
そうだよ
AGC解いてみろよ
AGCでも、AとかB問題ならアルゴリズム知識すら不要で、発想力のみ問われてるようなのが多いぞ
711デフォルトの名無しさん (ﾜｯﾁｮｲ e733-Iguz)
垢版 |
2022/09/09(金) 20:48:11.75ID:0OeV3J7Z0
何十年考える時間与えられても解けない自信あるわ
2022/09/09(金) 20:50:30.48ID:yIa0OFzGM
>>705
AtCoderの社長のchokudaiとかは、アルゴリズムイントロダクションを昔読んでたね
競プロで強くなるために最適な道かは知らないけど、読んでる人はいっぱいいると思う
2022/09/09(金) 20:53:37.03ID:Xak+SWAc0
好きな、覚えたてなコンピューター言語その他を使ってやるブラゲーっと思ってやってみた。
https://www.youtube.com/watch?v=Z9ki00Z5SWg&list=PLirT2ByBZWrNT1tlKZy2uAFRsaEc9KEEe&index=13

任天堂の“絶対に挫折させないプログラミングゲームUnreal Emgineみたいなノードだけど、Unreal Engineでいいんじゃないかと思った。
https://www.youtube.com/watch?v=Z9ki00Z5SWg&list=PLirT2ByBZWrNT1tlKZy2uAFRsaEc9KEEe&index=13
2022/09/09(金) 21:42:10.67ID:eDV4BhqD0
>>705
試しに解かなくてもいいけど、このへんの問題を考えてみ
AGCの中では破格に簡単な部類の問題だよ
https://atcoder.jp/contests/agc056/tasks/agc056_a
https://atcoder.jp/contests/agc021/tasks/agc021_a
https://atcoder.jp/contests/agc053/tasks/agc053_a

アルゴリズムの知識なんて全くいらないし、アルゴリズムの参考書なんてほとんど役に立たないよ
2022/09/09(金) 21:45:01.95ID:eDV4BhqD0
10^8回以上のループを書いてしまったら、実行時間制限に引っかかりそう

っていう程度の知識はいるけども
716デフォルトの名無しさん (ﾜｯﾁｮｲ bf71-InTp)
垢版 |
2022/09/09(金) 21:51:15.46ID:jmAmnAZ30
というか、典型を嫌うのでアルゴリズム全然使わなくても水とか青になれちゃうじゃん
2022/09/09(金) 22:03:48.01ID:N29LuzVwa
アルゴリズムの定義読んでこい
2022/09/10(土) 00:12:27.66ID:VggS9H2X0
蟻本は著者の頭が良いから簡潔に書かれてて、それ故に俺の頭じゃ理解できん
2022/09/10(土) 03:32:09.56ID:yhVOakDL0
本当に賢い人は云々
720デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/10(土) 04:59:42.21ID:eGCheWpr0
>>718
単に説明が下手なだけだと思います。
完成度も低いと思います。
2022/09/10(土) 05:04:17.39ID:44udkTjy0
ほならね
722デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/10(土) 05:06:40.45ID:eGCheWpr0
海外の本で良い本はないんですか？
2022/09/10(土) 13:06:15.05ID:ES5OPAh40
蟻本の説明がへたくそだとは思わないし、行間も一般的な数学書より狭いと思うけど、実際海外の競プロ本ってどんなのがあるのか気になるな
2022/09/10(土) 14:11:29.88ID:yhVOakDL0
Springerの"Guide to Competitive Programming"は読んだことある。
けんちょん本と同等程度のレベルって感じだけど典型テクニックへの言及はこっちのほうが多いかな
アルゴリズムの説明だけで実装が書いてないところが結構ある
2022/09/10(土) 14:14:41.39ID:2MbFO6mH0
蟻本は簡単な説明だけ。
個別のアルゴリズムは検索して、理解するまで自分で図を描いて勉強しないと無理

だから、>>642
に書いたように、個別の著書で調べる

湊真一、セジウィック、石畑清、川中真耶、インド人とか

例えば赤黒木なら、どの本だったかな? みたいな
2022/09/10(土) 15:22:48.30ID:ES5OPAh40
>>724
ありがとう
聞いた感じ、英語圏の標準的な入門書って雰囲気だね
やっぱり気になるのは中国だからいくつか調べてみた

・算法竞赛入门到进阶
・算法竞赛入门经典
・算法竞赛宝典

調べた感じまず目についたのはこのあたり？算法竞赛で競技プログラミングらしい
いずれもペーパーブックしかないところが惜しい
俺は機械翻訳しないと中国語読めないので
入门は日本で出版されている平均的なものとあまり変わらなそうな予感がするけど、宝典とかいうのは気になるね
2022/09/10(土) 15:25:44.75ID:ES5OPAh40
と思ったら電子書籍もありそうだ
amazonだけで調べて電子書籍ないと思い込んだのは我ながらネットリテラシー低いな
2022/09/10(土) 15:28:15.89ID:ES5OPAh40
しかし中華サイトは技術サイトでもキモい広告の表示のされ方がするな
2022/09/10(土) 16:26:58.64ID:vGRthkD8p
いいね、中国の最高の本を見つけたら教えてね
2022/09/10(土) 16:53:59.26ID:/N4+WCeu0
無理に中国語にこだわらなくてもいいと思うけど
2022/09/10(土) 17:39:53.64ID:yhVOakDL0
蟻本の凡人日本語訳が求められている
2022/09/10(土) 20:23:17.78ID:denZ2QcH0
今日初参加するわよろしく
本番の回答ここに貼ってくれてもOK！
2022/09/10(土) 22:42:02.88ID:h7iCGaIK0
なんで久しぶりに参加したときだけDが異常にムズいの
EとかFとか挑戦すらできず…
2022/09/10(土) 22:59:34.87ID:FQ2evD1NM
D解いた時点でひどい順位だったけどFGが軽実装で救われた
2022/09/10(土) 23:02:53.92ID:ulAsr0Va0
安倍晋三erすき
2022/09/10(土) 23:03:14.22ID:ulAsr0Va0
スレ間違えたけど間違えてない気もする
2022/09/10(土) 23:37:10.70ID:ES5OPAh40
Exの最後のパートの「区間集合が与えられて、その集合に属する任意の区間内に*が存在するように*を配置するとき、*の数を最小化せよ」って問題、定期的に出る典型だ
これもmincut maxflowの要領で双対とると蟻本でも有名な区間スケジューリング問題になって双対すごいってなった問題
なお今日はそこまで至れなかった模様
738デフォルトの名無しさん (ﾜｯﾁｮｲ de71-pqEy)
垢版 |
2022/09/10(土) 23:43:38.03ID:IxTwXPHP0
Dみたいなプログラミング的に普通っぽい問題の難易度が高いｗ
2022/09/10(土) 23:48:32.95ID:v7e0/wUkM
>>738
dfsで全列挙みたいなのが地味に一番実装難易度高い気がする
2022/09/10(土) 23:50:24.73ID:v7e0/wUkM
G、実はabc...とzyx...のときの順位を足して二で割るだけでいいって流れてきて、嘘だろ！？って思ったけど式を見てみたらそうだった
実はTrieもsuffixもprefixも要らんかったんや…
2022/09/10(土) 23:56:40.36ID:ES5OPAh40
>>730
競プロ強いのは中国語圏とロシア語圏だし、日本で出版されているよりすごい書籍があるとしたらその辺かなと思って
2022/09/11(日) 00:01:21.87ID:jAgyYoIY0
あと、Exの解説ではSA使ってるけど、長い文に対する複数文字列の位置検出といえばAho Corasick法がまさに使える
2022/09/11(日) 00:14:58.33ID:jAgyYoIY0
C、絶対位置を相対位置に変換して考えるのって初見でできたらかなり頭いいと思うんだけど茶diffなんだね
みんな頭いいな（もしくは典型で染みついている層が茶まで下りてきてるか）
2022/09/11(日) 00:32:41.95ID:Bha8il/10
パソコンに向かって解法や実装で延々と悩んでたのに、
疲れてベッドに横たわるとすぐにアイデアが出てくるのが謎
2022/09/11(日) 00:49:02.92ID:jAgyYoIY0
上位者は本番中に問題を解ける思考モードへの入り方がうまいっぽい
chokudaiか誰だったか忘れたけど、本番じゃないとAGCの問題解くの難しいって言ってたな
かなりメンタルが影響するらしい
2022/09/11(日) 00:51:45.15ID:kEOVMHNm0
数オリで中国チームが全員満点って話あって、情オリ見てみたけどこっちでも上位4は中国チームのメンバーで独占してるんだなあ・・・
https://stats.ioinformatics.org/results/2022

と思ってもっとよく見てみたら6位まで全部中国人やんけ
747デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/11(日) 11:51:48.46ID:c+Ui/I6I0
>>737
Exというのはどの問題のことでしょうか？
2022/09/11(日) 12:15:21.09ID:sY9L7CLNM
>>747
ABCの八問目で一番最後の問題
昔はHだった
749デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/11(日) 12:33:26.32ID:c+Ui/I6I0
>>748
ありがとうございました。

『プログラミングコンテストチャレンジブック第2版』のp.325に、

「したがって、先ほどの長方形を左半分と右半分の一辺dの正方形に分けると、それぞれの正方形には、
点はたかだか3個しか含まれません。」

と書いてあるのですが、たかだか2個ではないですか？
3個になる例はありますか？
750デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/11(日) 12:37:14.74ID:c+Ui/I6I0
3点となる例がわかりました。
でも4点の例がないことはどうやって証明するのでしょうか？
直感的には3点であろうと思いますが。
2022/09/11(日) 12:39:35.27ID:B0Yjkt4W0
>>743
競プロ初心者だけどC、40分くらい考えた末解けて自分天才だろと思ったのに茶diffだったんだな
みんな頭いいな
2022/09/11(日) 12:40:58.84ID:kEOVMHNm0
初心者で今回のCが解けるなら大したもんだよ
2022/09/11(日) 14:17:40.92ID:sY9L7CLNM
>>750
コンテスト中だと直感で済ませちゃうけど、ちゃんと証明書こうとするとめんどいやつだ

全ての点対の距離がd以上であるような4点が正方形領域内にあると仮定する。
この四点をA,B,C,Dとし、四角形ABCDを考える。
(1)全ての頂点の角度が180°未満のとき
角度が90°以上である頂点が存在、これをAとしても一般性を失わない。
ここで余弦定理より、BD^2 = AB^2 + AD^2 - 2 AB AD cos∠BAD >= AB^2 + AD^2 >= 2 d^2
よって、BD >= √2d
(2)ある頂点の角度が180°以上のとき
角度が180°以上である頂点をAとしても一般性を失わない。
ここで、∠BAC+∠DAC>=180°なので∠BACと∠DACのいずれかは90°以上。
∠BACを90°以上としても一般性を失わない。
(1)と同様の議論により、BC >= √2d

正方形領域内の点対距離は√2d未満（座標計算普通にやれば示せると思う）
(1),(2)のいずれの場合においても矛盾が生じる。
（証明終）
2022/09/11(日) 14:26:08.97ID:sY9L7CLNM
あ、(1)も(2)も不等式評価で角度が180°以下であることを使ってるけど、ちゃんと書いてないからキモい雰囲気の証明になってるな
2022/09/11(日) 15:12:26.47ID:jAgyYoIY0
凸包の最遠点対という特徴量、いかにも重要そうだけどあまり競プロで使った覚えがない
ABC234Exなんかは最近点対問題の解法と似た発想かもしれない、さすがにABC234Exの方が難しいけど
2022/09/11(日) 15:27:05.90ID:kEOVMHNm0
本質は無なので無料です
2022/09/11(日) 15:46:11.70ID:sY9L7CLNM
逆に最遠点対どうやってNlogNで求めるんだっけって思ったが、凸包求めてキャリパー法でくるくるか
幾何系はド典型でも全然頭に定着しない
758デフォルトの名無しさん (ﾜｯﾁｮｲ 7d01-J1Nd)
垢版 |
2022/09/11(日) 16:55:39.75ID:Nz+JHxy30
昨日のABC、Dの実装でバグらせる予感しかしなかったからEから解いて何とかギリギリ解けたけど難易度E>Fだったんだな
F典型って聞いたけど青くらいまで行けば典型に見えるんだろうかたしかに取り組みやすそうな問題ではあったけど
759デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/11(日) 17:29:18.43ID:c+Ui/I6I0
>>753
証明ありがとうございました．
うまい証明ですね．
760デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/11(日) 17:37:25.16ID:c+Ui/I6I0
>>751
今，解こうとしていますが，難しいですね．
素朴な方法だとΘ(N^2)ですね．
回転前の喜ぶ人の人数から，回転後の喜ぶ人の人数が簡単に計算できないかと考えているのですが，うまくいきません．
761デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/11(日) 18:18:32.35ID:c+Ui/I6I0
>>751
幅3のパルス波が押し寄せてくるイメージを思いつきました．
なんとなく解けるような気がします．
762デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/11(日) 18:57:12.47ID:c+Ui/I6I0
>>751

半日かかりましたが，Θ(N)のアルゴリズムを作ってパスしました．
これじゃ，コンテストでいい成績は残せませんね．
2022/09/11(日) 20:29:08.05ID:792CMm+80
ARC出ません
2022/09/11(日) 23:13:18.91ID:jAgyYoIY0
E問題解きたかったなあ…
2022/09/11(日) 23:24:22.70ID:jAgyYoIY0
最終的にはわからない問題を考え続けるのが一番の練習法らしいから、解説を見ないで解く体力が長い目で見て実力に寄与する気がするし、ABC-Cを半日考えて解くのは上等
ただ、ABCだと知識ゲーの要素があるから、最初のうちは解説見た方がサクサクレートが上がる場合もあるし、悩みどころだ
766デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/12(月) 07:10:41.31ID:rinzAyh80
「Closest pair of points」を求めるアルゴリズムについてですが，『プログラミングコンテストチャレンジブック第2版』の
説明だと説明が全く不足しています．

この本を褒める人がいますが，信じられません．
確かに他に少し高度なこの類の本がないというのは事実だと思いますが．

CLRSの計算幾何学の章に非常に詳しく解説が書いてありますので，そちらを読もうと思います．
767デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/12(月) 07:12:15.09ID:rinzAyh80
『プログラミングコンテストチャレンジブック第2版』ですが，完全な解説ではなく，スケッチ程度の説明集だと
思います．

ネット上の解説などもそのようなものがほとんどだと思います．
2022/09/12(月) 07:57:57.20ID:AFh4CYQbr
そうなんだ
2022/09/12(月) 11:21:41.15ID:WsTAO2GiM
4点の証明よりめんどい行間ある？って思ったけどマージソートの部分か
x座標で点集合を分けたあと、各ステップでx座標的に隣接する点集合を合わせることを繰り返すわけだが、そこでマージソートの要領でy座標をソートすることで、時間計算量を増やさずにy座標のソートができる
ある程度のレベルの学術書で単体で行間埋められる本の方が珍しいし、別に行間だらけだから良書じゃないなんてことはないと思うがな
770デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/12(月) 17:30:34.33ID:rinzAyh80
>>769
確かに有益な本だとは思うのですが，もう少し解説が丁寧だといいなと思います．
完全に理解するために，ソースコードに頼ることが非常に多いので．

何かおすすめのAtCoderの問題はありますか？
難しすぎると解けないので，初心者でも解けるくらいで面白い問題が希望です．
2022/09/12(月) 18:09:25.90ID:E//33fQvM
>>770
このサイトはAtCoder Problemsといって、各問題のdifficultyという数値を見ることができる
https://kenkoooo.com/atcoder#/table/

difficultyとはなにかと言うと、半分ぐらいの確率でその問題を解けるであろう人のレートを推定したもの
ここでdifficultyの二分探索でもすれば自ずと丁度いいぐらいのところに行きつくと思う
基本的には自分のレートと同じか一色上ぐらいがやってて楽しい
初心者でプログラミング自体はできるんなら、最初はABC-C、ARC-Aぐらいの問題が丁度いいレベルと思う
面白さについて言えばAtCoderの問題は大体パズル的には面白いはず、ただそこも好みだな
高度な知識をたくさん使いたいんならCodeForcesの方が面白いかもしれない
772デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/12(月) 18:15:28.92ID:rinzAyh80
>>771

詳しく丁寧にありがとうございました．

時間をかけて解いていきたいと思います．
2022/09/12(月) 18:20:46.33ID:E//33fQvM
蟻本が解説に関して親切設計な本ではないのは確か
今は蟻本よりもっと初学者向けの競プロ本がたくさんあるから、その中から選ぶのも手ではある
最近は鉄則本なんていうのも出て、それも蟻本に比べたら多分初学者向け
https://kato-hiro.github.io/AtCoderClans/books/

ただ厳密数学的な意味で丁寧な本ってあるんか？自分は蟻本以外読んだことないからよくわからん
774デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/12(月) 18:38:46.03ID:rinzAyh80
>>773
リンクありがとうございました．
2022/09/13(火) 06:55:02.21ID:sWJYur860
こどふぉで自分のレートのdifficultyの問題をずーっとやってるんだけど、
簡単に解けるのと全然歯が立たないのがある…
2022/09/13(火) 19:26:09.73ID:9QsJBQr90
外国人と日本人で結構な得意な問題が違う気がする
777デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/14(水) 09:18:47.48ID:jsfAG/sd0
github.com/drken1215/book_algorithm_solution/blob/master/solutions/chap04.md

この4.6のコードですが、本当にO(N*W)ですか？

ボトムアップ型の動的計画法がO(N*W)というのは分かりますが、4.6は違うような気がします。
778デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/14(水) 09:24:01.59ID:jsfAG/sd0
>>777
これは、部分和問題のコードのメモ化再帰のコードです。
2022/09/14(水) 11:19:03.17ID:9MjfrPGa0
ざっと見た感じはO(NW)で合ってそう
2022/09/14(水) 11:35:22.59ID:vMgqqEzp0
引数のwが負になりうる実装で、そもそも壊れてそう
2022/09/14(水) 11:39:04.72ID:vMgqqEzp0
issue 立ってるけど放置されてるな、やる気はその程度か
782デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/14(水) 13:32:56.43ID:jsfAG/sd0
文字列の編集距離について質問です。
S、Tを文字列とする。
dp[i][j]をSの最初のi文字からなる文字列とTの最初のj文字からなる文字列の間の編集距離とする。

■変更操作（Sのi文字目とTのj文字目とを対応させる）：
S[i-1]==T[j-1]のとき：コストを増やさずに済みますので
chmin(dp[i][j], dp[i-1][j-1])
です。
S[i-1]!=T[j-1]のとき：変更操作が必要ですので
chmin(dp[i][j], dp[i-1][j-1]+1)
です。
■削除操作（Sのi文字目を削除）：
Sのi文字目を削除する操作を行いますので
chmin(dp[i][j], dp[i-1][j]+1);
です。
挿入操作（Tのj文字目を削除）：
Tのj文字目を削除する操作を行いますので
chmin(dp[i][j], dp[i][j-1]+1)
です。
783デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/14(水) 13:34:32.86ID:jsfAG/sd0
「S[i-1]==T[j-1]のとき」と書いてありますが、これは
「S[i]==T[j]のとき」が正しいというわけではないですか？
784デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/14(水) 13:34:44.34ID:jsfAG/sd0
>>779-781

ご回答ありがとうございます。
785デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/14(水) 13:36:39.23ID:jsfAG/sd0
>>782
は『問題解決力を鍛える!アルゴリズムとデータ構造』という本に書いてある解説です。
786デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/14(水) 13:38:36.60ID:jsfAG/sd0
配列は0始まりなのでこれで間違っていませんね。
787デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/14(水) 13:44:17.21ID:jsfAG/sd0
>>782

S[i-1]==T[j-1]のとき：コストを増やさずに済みますので
chmin(dp[i][j], dp[i-1][j-1])
です。

これをSの最初のi文字からなる文字列を編集により、Tの最初のj文字からなる文字列に最小の手間で
変更するには、Sの最初のi-1文字からなる文字列を編集により、Tの最初のj-1文字からなる文字列に最小の手間で
変更すればいいということを言いたいのだと解釈しました。

Sのi番目の文字を変更したとしてもトータルの編集の手間が少なくなることはないというのは証明が必要ではないでしょうか？
788デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/14(水) 13:46:31.88ID:jsfAG/sd0
>>782

の他のところについても同様の疑問があります。
2022/09/14(水) 15:14:15.25ID:tHNQsFnsr
そうなんだ
790デフォルトの名無しさん (ﾜｯﾁｮｲ de2a-62hs)
垢版 |
2022/09/14(水) 15:24:09.35ID:9+y+r6nn0
適当なこと言うけど
Sのi番目の文字を変更したとしても、最終的にはSのi番目の文字をTのi番目の文字に合わせないといけないから、
Sのi-1番目までの操作に置き換えられるということじゃないかな

例えば、bookをdeskに合わせるなら、
bookのkを適当にaに変える→booa
でも最終的には最後の文字はkにしないといけない
booaの最後にkを挿入→booak
booakっていうのは、bookのbooの部分にaを挿入したものと考えられる
こういう感じで、結局Sのi-1番目までの操作と考えることができるっていうことだと思う
2022/09/14(水) 15:30:11.95ID:5xlFzeB+0
S[i-1]==S[j-1]で、Sのi文字目かTのj文字目を変更したときに、dp[i][j]<dp[i-1][j-1]とするとdp[i-1][j-1]<dp[i-1][j-1]が導かれるようにできるよ
dp[i-1][j-1]未満の編集距離で揃えるにはSのi文字目かTのj文字目のどちらかを使わなきゃいけないことに注目する
792デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 09:32:52.27ID:3elqjdXs0
>>790-791
ありがとうございました。
まだ、よく分からないので、少し質問の仕方を変えてもう一度質問させてください。

以下がなぜなのかが分かりません。
いかにも成り立ちそうですが、証明ができません。

S = 'LOGISTIC'
T = 'ALGORITHM'

(1)
Sの最後の文字CをTの最後の文字Mで置き換える。
Sからその最後の文字を除いた文字列を、Tからその最後の文字を除いた文字列に
最小の手間で編集する。

(2)
Sの最後の文字Cを削除する。
Sからその最後の文字を除いた文字列を、Tに最小の手間で編集する。

(3)
Sの最後の文字Cの後ろに、Tの最後の文字Mを付け加える。
SをTからその最後の文字を除いた文字列に最小の手間で編集する。

(1)、(2)、(3)を実行するのに必要な手間のうち最小の手間が、文字列Sを文字列Tに
編集する最小の手間である。
793デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 09:35:19.04ID:3elqjdXs0
間違えました。以下のように訂正します。

S = 'LOGISTIC'
T = 'ALGORITHM'

(1)
Sの最後の文字CをTの最後の文字Mで置き換える。
Sからその最後の文字を除いた文字列を、Tからその最後の文字を除いた文字列に
最小の手間で編集する。

(2)
Sの最後の文字Cを削除する。
Sを、Tに最小の手間で編集する。

(3)
Sの最後の文字Cの後ろに、Tの最後の文字Mを付け加える。
SをTからその最後の文字を除いた文字列に最小の手間で編集する。

(1)、(2)、(3)を実行するのに必要な手間のうち最小の手間が、文字列Sを文字列Tに
編集する最小の手間である。
794デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 09:38:28.08ID:3elqjdXs0
また、間違えました。以下のように訂正します。

S = 'LOGISTIC'
T = 'ALGORITHM'

(1)
Sの最後の文字CをTの最後の文字Mで置き換える。
Sからその最後の文字Mを除いた文字列を、Tからその最後の文字Mを除いた文字列に
最小の手間で編集する。

(2)
Sの最後の文字Cを削除する。
Sを、Tに最小の手間で編集する。

(3)
Sの最後の文字Cの後ろに、Tの最後の文字Mを付け加える。
Sからその最後の文字Mを除いた文字列を、Tからその最後の文字Mを除いた文字列に最小の手間で編集する。

(1)、(2)、(3)を実行するのに必要な手間のうち最小の手間が、文字列Sを文字列Tに
編集する最小の手間である。
795デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 13:41:42.51ID:3elqjdXs0
SをTに最小の手間で変換するオペレーションが以下の画像の通りだとする。
オペレーションを実行する順序には関係なく、SはTに変換されることに注意する。

imgur.com/GSQfWoU.jpg

(1)Sの最後の文字の右にInsertオペレーションがある場合。

Sの最後の文字の後ろに、Tの最後の文字を付け加える。
Sからその最後の文字を除いた文字列を、Tからその最後の文字を除いた文字列に最小の手間で編集する。

これが(1)の場合に、SをTに変換する最小の編集方法になる。
796デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 13:41:55.18ID:3elqjdXs0
(2)Sの最後の文字の右にInsertオペレーションがない場合。

(2-1)Sの最後の文字に行うオペレーションがN（何もしない）の場合。

この場合、Sの最後の文字とTの最後の文字は等しい。
Sからその最後の文字を除いた文字列を、Tからその最後の文字を除いた文字列に最小の手間で編集する。

これが(2-1)の場合に、SをTに変換する最小の編集方法になる。

(2-2)Sの最後の文字に行うオペレーションがD(Delete)の場合。

この場合、Sの最後の文字を削除する。
Sを、Tに最小の手間で編集する。

これが(2-2)の場合に、SをTに変換する最小の編集方法になる。

(2-3)Sの最後の文字に行うオペレーションがS(Substitute)の場合。

この場合、Sの最後の文字をTの最後の文字に置き換える。
Sからその最後の文字を除いた文字列を、Tからその最後の文字を除いた文字列に
最小の手間で編集する。

これが(2-3)の場合に、SをTに変換する最小の編集方法になる。
797デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 13:43:21.05ID:3elqjdXs0
こう考えたのですが、これでいいでしょうか？
2022/09/15(木) 14:20:18.89ID:2rpOawCB0
多分、dp[i]を、i番目まで揃えたときの最小手順数だって定義してると思う
その次のインデックスの文字を揃えるために出来ることがその3パターンしかなければ、そうなんじゃないかなぁ
dpを更新したときに、定義が崩れてしまわないか？を集中して考えてみると良いと思う
2022/09/17(土) 14:19:59.56ID:ChhZpwg90
最近競技プロ出来てねー
まぁ2年くらいやったし飽きたのかも
800デフォルトの名無しさん (ﾜｯﾁｮｲ 5701-nNgT)
垢版 |
2022/09/20(火) 09:38:15.86ID:l9naZzzk0
パイザってサイトに『エンジニア騎士とクエリの魔女』の『暗黒の地』って
競技プログラミング風味のものがあるんだよ。まあまあ面白くて
これで12位になったので、ソース公開するね。
https://paiza.io/projects/Me-9l8aRopclovpRhczITg
ソースを読んだ感想を書いてくれたりしてくれると嬉しいです。みんなもやってみよう
2022/09/20(火) 11:41:19.73ID:Qcy/onU00
いいね！
すごいね！
2022/09/20(火) 13:54:44.15ID:gUImHuHP0
この問題わかんね
https://twitter.com/SSRS_cp/status/1571996174604963840
https://twitter.com/5chan_nel (5ch newer account)
2022/09/20(火) 14:02:43.97ID:gUImHuHP0
平方分割すればできるのはわかるけど、想定解はそうじゃないっぽいし
2022/09/20(火) 14:51:16.41ID:Y9OiSWpN0
Lだけの話に限定するけど、
Lの効果をインデックス毎に保管しておいて、（入力例１なら[-1, -2, 2, 0, 1]）
それのセグメント木を作れば区間最小値をlogNで取り出せるようになるからいけるんちゃうか？
2022/09/20(火) 16:42:42.75ID:fSXnXfcH0
耳DPをセグ木に乗せるだけやろ
2022/09/20(火) 17:00:13.31ID:gUImHuHP0
>>804
問題は、Rも同じようにインデックス毎に効果を保管するとして、区間内で和が最大になるLの効果とRの効果のペア（Lの効果のインデックスよりRの効果のインデックスの方が右になければならない）をO(1)とかO(logN)で取り出さなきゃいけないことだと思うけど、そこが難しくないか？

>>805
耳DPというと、左の区間外、Lの区間、元の値をそのまま使う区間、Rの区間、右の区間外みたいな感じの状態の持ち方？
2022/09/20(火) 17:17:04.14ID:Y9OiSWpN0
>>806
たし蟹
ぱっと考えただけだとペア探しにO(N)かかってまう
ちょっと分からんわ
2022/09/20(火) 18:28:08.02ID:yGxPr74E0
まずaについて、各項の隙間ごとにLはその左でRはその右にあるような置き換え方での和の最小値を求めておいて、区間が限られたらその区間にある隙間に対して区間minして端の分を補正したらいいんじゃないの
2022/09/20(火) 18:44:31.27ID:R7N7Rzx3r
うんち
2022/09/20(火) 19:40:54.03ID:gUImHuHP0
>>808
なるほど、と思ったけど、
N=4
A=[0,1010,1010,0]
L=1000
R=1000
Q=1
l,r=1,3
みたいなときに厳しそう
2022/09/20(火) 20:06:23.92ID:yGxPr74E0
>>810
めちゃくちゃ嘘だったわ
2022/09/20(火) 20:08:23.68ID:3RVLul1m0
普通にx毎に最小になるyを取れるようにする方針だけど
それだと幅*Qぐらいだから多分無理なので改良として
セグツリーかなんかで[x,..)の領域に対して一発でy取れるようにすりゃいんじゃねって思った
ちなワイ茶色
2022/09/20(火) 21:29:32.52ID:Y9OiSWpN0
超思いつきだけどさ、
L<Rの場合、Lのテリトリーを譲ってまでRの幅を広げる必要はない気がするんだよな
だからLについては貪欲に最小拾っていいとかないかな？
2022/09/20(火) 22:04:05.16ID:6eFEjyRr0
耳DPのトロピカル行列をセグ木に乗っけて終わりとちゃうんか
2022/09/20(火) 22:05:42.62ID:6eFEjyRr0
全区間についての答えの和とかは解けんのかな
オーバーフローはないもんとして
2022/09/20(火) 22:19:34.98ID:gUImHuHP0
耳DPの遷移を表すトロピカル行列が
L ∞ ∞
A_i A_i ∞
R R R
になってて、積についてモノイドになってるからセグ木に乗る
区間積求めてあとは(0,∞,∞)^tに作用させればおｋってこと？
2022/09/20(火) 22:21:34.19ID:gUImHuHP0
>>813
なんかこれはこれで正当化できそうな雰囲気がある
2022/09/20(火) 22:25:23.85ID:gUImHuHP0
結局正解っぽいやつについて自力で全然思いつかなかったの悲しい
2022/09/20(火) 23:18:52.20ID:gUImHuHP0
>>800
paizaってOpenCV使ったりするような問題出るんだ
2022/09/21(水) 00:43:34.61ID:x1slIPpsM
行列積の定数倍が重いせいで平方分割落とす制約にできないのか
2022/09/21(水) 11:31:22.73ID:KfFuyi/HM
情報の保持って観点じゃトロピカル行列は
A_i A_i
R R
の左下部分だけで十分ってことか
https://twitter.com/SSRS_cp/status/1572362117432643586?t=_MoRQwYnYHKZd2peSTfpbQ&s=19
https://twitter.com/5chan_nel (5ch newer account)
2022/09/21(水) 11:32:37.83ID:KfFuyi/HM
あと区間長さえ保持しとけば
823デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM8f-nNgT)
垢版 |
2022/09/21(水) 12:17:44.87ID:qEUpkz9TM
>>819
あ、opencasは私個人的な
ローカル環境での
動作確認、デバッグ用です
そういうのつけとけば
参加してくれる人いるかな
的な意図もあります
824デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5b-lIjq)
垢版 |
2022/09/21(水) 16:22:14.70ID:AliPmZ5ga
ふつうにLとの差分の累積和とって右から全探索でいいんじゃないのか？
2022/09/21(水) 18:13:16.60ID:+9EfOb1n0
N,Q≦10^5の制約だけど、それは2secで通る？
826デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5b-lIjq)
垢版 |
2022/09/21(水) 20:13:31.40ID:k2jdRmOoa
Nだから普通に通るよ
2022/09/21(水) 20:48:04.88ID:bmvBppJjM
具体的なやり方が読み解けないけどクエリごとに全探索したらO(NQ)なのでは？
2022/09/21(水) 20:52:43.66ID:bmvBppJjM
もしかして、元々の問題ABC263Dの解法の話してる？
2022/09/21(水) 21:08:22.89ID:bmvBppJjM
昔のadminがりんごさんだったころのSRMってAGCとかに役に立つ？
830デフォルトの名無しさん (ﾜｯﾁｮｲ bfd7-lIjq)
垢版 |
2022/09/21(水) 22:35:20.54ID:JxZ0RmNU0
>>828
ごめん話題変わってた？

左からLとの差分の累積和とって、左からi番目までで1番値が大きいやつのインデックスメモっておくのがO(N)
右から見てってiより右側はRにして、iより左側でLにするべき境目はさっき求めたからiの全探索でO(N)でいける認識

説明やばいけど勘弁して
2022/09/22(木) 00:37:51.08ID:7XNeWjKf0
ABC263Dの解法としてはそれでOK
リンクされたツイートではさらに、元々の数列のうち区間[l,r)の部分に限った数列について元々の問題を解く×Qって設定になっていた
その解き方だとO(NQ)でTLEするので、これがちょっと難しかった(もう解法は発表されたけど)
2022/09/22(木) 01:37:50.90ID:LfyHnz2g0
正直、4つ持つことになんの意味があってどう嬉しいのか全く分からんぞい
耳dpってやつなの？
2022/09/22(木) 03:17:37.64ID:FFFEjz5/0
4つ情報を持ってないと、モノイドにする（≒結合則を成り立たせる）上で情報が足りないからセグ木に乗らない
このモノイドが代数的な言葉で言えばトロピカル行列に対応している
ちなみにこのトロピカル行列は耳DPの遷移だから、そっちから考えても同等の解答に行き着く的な感じ
明日気が向いたらこの辺ちゃんと書く
何か言葉は仰々しいけど別にトロピカル代数の知識なくても、上書き区間左側確定 T/F 上書き区間右側確定 T/Fで値持って区間をくっつけること考えたらどういう演算をしたらいいかは発想できると思う
2022/09/22(木) 03:22:21.63ID:FFFEjz5/0
自分の理解だとさらに区間の長さも必要そうだから厳密には必要なのは5つの情報かな？
2022/09/22(木) 11:18:12.70ID:c1NDWA0LM
半環上の正方行列が積が結合則満たすのって実正方行列での証明考えれば自明だけど、それが行列積だと分かってない状況だとかなり直観的に分かりづらいよな
そもそも行列積自体、初見で線形写像の幾何学的な話もなしだと結合則が成り立つと見抜くのが無理そうな意味不明な演算に見えるし
836デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/24(土) 18:24:44.81ID:nZKOKQNY0
大槻の本に、比較によってソートするアルゴリズムの最悪計算量は、 Ω(n * log(n)) であると書いてあります。

最善の計算量が O(n * log(n)) よりも良いようなものって存在しますか？
2022/09/24(土) 18:33:53.75ID:hL268OjV0
nがあります
2022/09/24(土) 18:36:10.29ID:ewV+cEv/0
ボゴソートは最良計算時間nですよ
839デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/24(土) 18:38:34.03ID:nZKOKQNY0
例を挙げてください。
2022/09/24(土) 19:08:37.47ID:B/S/upiL0
最善って意味だと挿入ソートはO(N)
2022/09/24(土) 19:21:32.49ID:lQxqE4zm0
バブルソートはソート済みの列に対して O(n)
842デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/24(土) 19:24:43.12ID:nZKOKQNY0
>>837-838,841

ありがとうございました。確かにバブルソートはそうですね。でもマージソートとか最善の計算量と最悪の計算量が同じ計算量のものが多いですね。
2022/09/24(土) 22:42:30.99ID:JAEDuJ+F0
A問題、A問題の難易度じゃないだろ
844デフォルトの名無しさん (ﾜｯﾁｮｲ 9e71-mIyF)
垢版 |
2022/09/24(土) 22:53:45.20ID:cuZGjTPy0
Aこの難易度でも良いけど、ビギナーコンテストなんだから9割くらいが解けるDくらいまでにすべき、１０問は多すぎ
Dも昔は愚直にやって通るくらいの難易度だった気が
2022/09/24(土) 22:56:24.67ID:XN000lpY0
D問題が greedy じゃダメな理由がわからん……
解説に反例があるのは見たけど納得できない
2022/09/24(土) 23:04:41.84ID:Cc5Uw0Zt0
確かに直感的にはDはgreedyでもよさそうだけど、ナップサック法よろしく、整数が絡むと途端に直感greedyが壊れる
ABC-DからABC-Fぐらいの問題だとコンテスト中はgreedyがダメな理由を考えるより簡単に正当性を示せるDPを思いつくことを意識した方がいい
2022/09/24(土) 23:07:25.27ID:Cc5Uw0Zt0
反例に関して言えば2個取るという選択肢がないのが効いてる
2022/09/24(土) 23:16:48.66ID:Cc5Uw0Zt0
ExのFPS解面白い
確かにDP遷移で途中\sum_n {n a_n}みたいな形の式が出てきてめんどくさそうと思ったけど、こういうのはFPSならただの微分か
849デフォルトの名無しさん (ﾜｯﾁｮｲ 9e71-mIyF)
垢版 |
2022/09/25(日) 01:57:37.46ID:eKbCKhXa0
Dが水という事は、ビギナーコンテストだからC問題までの３問で良いじゃん
2022/09/25(日) 02:18:02.40ID:qNDnNxHD0
8問ABCは言うなればCodeForces Div. 2 + Div. 3 + Div. 4みたいな状態だから、Div. 3単独開催やDiv. 4単独開催が欲しいって話は分からなくもない
4問時代のABCがまさにそんな感じだったけど
コドフォが最近Div. 4増やしてるし、AtCoderも現ABCの下の区分のコンテスト作っていいと思うけどね
2022/09/25(日) 02:25:38.65ID:qNDnNxHD0
自分の感覚だと
CF Global = AC AGC
CF Div. 1 = AC ARC
CF Div. 2 = AC ABC-C〜Ex
CF Div. 3 = AC ABC-C〜F
CF Div. 4 = AC ABC-A〜D
ぐらいのイメージなんだけど、合ってる？
そんなコドフォ出てないから詳しくないけど、Div. 2以下の階級を全部ABCがカバーしている状態ではあるのは確かだと思っている
852デフォルトの名無しさん (ｻｻｸｯﾃﾛﾚ Sp47-Rupp)
垢版 |
2022/09/25(日) 09:32:03.84ID:HBsCeuHap
昨日のEってどういう思考過程をすれば二分探索が思いつけるんだ
言われたらそれはそうってなるけど
2022/09/25(日) 11:07:00.84ID:gbe15JeH0
>>845
肉を切らせて骨を断つ
無傷でいようとすると勝てないってわけよ
2022/09/25(日) 12:13:04.55ID:ODs0tVKRM
昨日のEは別に二分探索なんか使わなくても素直なやり方で解ける気がするが、判定問題が簡単で単調性がありそうならとりあえず二分探索試して損はない
2022/09/25(日) 12:15:43.34ID:ODs0tVKRM
ぐろふぉはAGCより取っつきやすい気がするな
2022/09/25(日) 12:46:21.45ID:ODs0tVKRM
Twitterみた感じEのO(NlogN)解は重実装扱いなのか
個人的には二分探索解と大して変わらんやろと思ったが
857デフォルトの名無しさん (ｻｻｸｯﾃﾛﾚ Sp47-Rupp)
垢版 |
2022/09/25(日) 13:15:51.54ID:JpevNCD6p
愚直にシミュレーションしようとしたらバグらせまくったから二分探索の発想が早い段階で思い浮かぶように出来たら便利だなって
2022/09/25(日) 22:01:15.20ID:IPCnGxrw0
端数は後でなんとかすることにしてだいたい何周すればいいか知りたくなって、周回数を決め打ちすれば何個減るかはO(N)でわかるから二分探索すれば良さそうとなる
2022/09/25(日) 23:58:46.25ID:5HnvgjcS0
ユーザー解説にO(NlogN)の実装があるから見たけど、そんな重実装かこれ？
二分探索より楽に見えるんだが
2022/09/26(月) 09:01:27.51ID:cpj0q9yVM
本来二分探索の実装ってかなりバグらせやすい方だと思うんだが、めぐる式で教育が行き届いている？のか、最近はみんな脳死で書ける印象
O(NlogN)解は量や内容は大したことないがアドホックなのが効いてんのかな
2022/09/26(月) 10:32:20.32ID:ncSKb+wV0
にぶたんの最後のシメを考えるのが苦手すぎる…
LRがどうなったら終わりで、どっちに答えが入ってるのか分からなくなるよ
2022/09/26(月) 11:47:57.47ID:ut+E4sGm0
そこでめぐる式よ 継続条件はwhile(abs(ok-ng) > 1)で答えはokに入る
2022/09/26(月) 12:49:10.56ID:QsR2IXV50
その式だけだとokがleftかrightか分からん
2022/09/26(月) 12:53:59.99ID:7xAfjatjM
別にleftでもrightでもどっちでもいいからバグらないと言える
位置関係より意味内容に忠実な表記
2022/09/26(月) 14:00:18.97ID:i/jndsoD0
ok、ngとかいいつつちゃんと定義域を渡さないといけないところらへんで、慣れてないひとは混乱するんだろうと思う
ok、ngではなくて、明確に定義域を指定するようなインタフェースに整えてあげると初学者には優しいでしょう

おれはいつも混乱しないように詳細を積めてから実装してるからok、ngなんて使わずhi、loで書いてるけど
2022/09/26(月) 14:31:20.74ID:QwvWOyok0
ok(ng)の初期値は条件が真(偽)だとわかっているところ
もしくは定義域の一個外にするけど
そんなに混乱するか？
2022/09/26(月) 14:51:56.76ID:i/jndsoD0
おれはしないから予想してるだけ
868デフォルトの名無しさん (ﾜｯﾁｮｲ 9210-A/T8)
垢版 |
2022/09/26(月) 15:55:48.24ID:50Eh55hb0
自分は二分探索、毎回コピペしてる
値が小さい方から大きい方にかけて、条件式がTrue, True, ..., False, Falseになるのと
False, False, ..., True, Trueになる2パターン用意しといて毎回コピペしてる
869デフォルトの名無しさん (ﾜｯﾁｮｲ 9210-A/T8)
垢版 |
2022/09/26(月) 16:10:31.34ID:50Eh55hb0
ん、めぐる式二分探索って、上の2パターンを一般化しますよっていう話か...
3年半も競プロしてんのに初めて知ったよ...
2022/09/26(月) 17:20:22.65ID:mM+PT8Od0
別にlo, hiやleft, rightの実装で全く困ってなければ知らなくてもいいと思う
位置と判定、境界を一緒に考えると頭がこんがらがる初心者にとって、めぐる式は判定関数とok,ngの初期値さえ与えておけば二分探索部分のコードは位置関係すら考えず貼るだけなので楽
2022/09/27(火) 00:33:47.81ID:OQZ1tOOg0
LRをどっちもokにしちゃうと無限ループしちゃうんだよな
まったくもう
2022/09/27(火) 00:51:50.39ID:ZwmfNOl50
あー、そういえば、めぐる式で一番重要なノウハウは、[left, right)の半開区間にすると処理が簡単、ってことだと思うわ

閉区間にすると考えることもコードも増えてキツイと思うんだけど、外人のコードだとかなり見かける
こないだのABC1位のひとでもこれでやってるんだよな
if check(mid)
l = mid + 1
else
r = mid - 1
2022/09/27(火) 01:56:33.69ID:f9wenpM60
中国って割と1-based・閉区間の派閥がいるイメージだわ
2022/09/27(火) 07:38:03.73ID:nRLJF7B50
取り敢えず区間扱うときは全て半壊区間が安定してるなぁ
2022/09/27(火) 10:17:28.55ID:RK9MOCkIM
そのあたりは情報処理能力やライブラリ化でごり押せるから、上級者でも筋の悪い実装方針でやってたりすることがあるイメージ
特に軽実装のAtCoderでは、まず算数パズルができるということが何よりも大事だから
876デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/27(火) 15:17:24.67ID:j2LDQh400
DAG上の最短路問題について普通のアルゴリズムとデータ構造の本には載っていません。
これはトポロジカルソート＋動的計画法によって、最短経路の求め方が自明だという考えからでしょうか？
2022/09/27(火) 15:31:56.76ID:ZwmfNOl50
さあ、ダイクストラでも大体十分だったりするから需要ないんじゃない？
2022/09/27(火) 16:05:50.65ID:RqBRw8Xlr
うんち
879デフォルトの名無しさん (ﾌﾞｰｲﾓ MM32-QTvv)
垢版 |
2022/09/28(水) 13:02:21.64ID:F+G1dH1CM
ABC263のDやってるんだけど、
kyopro_friendsさんの解説に出てくる累積minってググっても出ないんだけど、
nok0さんの解説のf(k+1)=min(f(k)+A[k+1], L*(k+1))のこと？
累積和使って最小値求めると、全体でO(N^2)になっちゃいますよね
2022/09/28(水) 13:33:58.07ID:E29MaAWV0
>>879
そのf(i)の意味を勘違いしてるかも。
例えばf(5)ならば、

①A1+A2+A3+A4+A5
②L+A2+A3+A4+A5
③L+L+A3+A4+A5
④L+L+L+A4+A5
⑤L+L+L+L+A5
⑥L+L+L+L+L

この６パターンの内の最小値って意味だよ
881デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 15:59:44.30ID:B1p+YPuG0
AtCoder Problemsが独自に算出したという「difficulty」ってどこで見れるんですか？
882デフォルトの名無しさん (ｱｳｱｳｳｰ Sa43-q+3U)
垢版 |
2022/09/28(水) 16:24:44.67ID:cIcLbxtta
AtCoder Problemsで見れます
883デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 16:38:42.88ID:B1p+YPuG0
>>882
Show DifficultyをONにしても表示されません。
884デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 16:47:43.15ID:B1p+YPuG0
大槻のAtCoder入門を図書館から借りてきましたが、やさしすぎますね。
2022/09/28(水) 17:47:31.56ID:ZeFU5MB7M
>>883
左の円の色とか円の中のゲージがdifficulty
886デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 18:08:29.44ID:B1p+YPuG0
>>885
ありがとうございました。マウスのポインターを円の上に持っていったら表示されました。
887デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 21:41:22.84ID:B1p+YPuG0
大槻のアルゴリズムとデータ構造の本に、クラスカルのアルゴリズムの計算量が、
O(|E| * log(|V|)) であると書いてあります。

なぜ、 O(|E| * log(|E|)) と書かないのですか？
2022/09/28(水) 22:01:47.27ID:7KJ1BqpF0
文脈が分からないけど、単純グラフって仮定があるんなら|V|^2>|E|だからってことで深い意味はないと思う
強いて言えば|V|の方がlogのお得感が出るとか？
889デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 12:34:13.21ID:aXocYaHs0
大槻のAtCoder入門という本に、頂点の数 N、辺の数 Mのグラフの構造の入力の受け取る処理に
O(N + M) の計算量が必要だと書いてあります。

O(M) が正しいと思いますが、どうですか？
890デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 12:34:55.30ID:aXocYaHs0
>>888
ありがとうございました。
2022/09/30(金) 12:35:34.42ID:jkyVOJ86d
辺の数がゼロのグラフとか
2022/09/30(金) 13:36:02.20ID:DDlNV6wMd
入力長はO(M)だけどvectorの確保にO(N)かかりそう
2022/09/30(金) 14:19:09.50ID:LLOTX79E0
本当にグラフの構造情報を受け取るだけであればO(M)でいいけど、後続の処理で結果的にはO(N+M)かかることがほとんど
ただ、たとえばN=10^100, M<=10^5みたいなパターンの問題も考えうるから、O(N+M)よりはO(M)の方が正確かな、特に他に但し書きがないのであれば
かなり自明な話なので、そこのO(N+M)の記述で混乱して問題を解くのに支障が出る人はいない気がするけど
2022/09/30(金) 14:35:51.41ID:og+oo4X4a
すべて入力から受け取る必要があるならそら入力にO(N+M)かかるやん
入力の辺は重複しないみたいな条件がついてるなら、O(N^2)あるいはO(M)になったりする
895デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 20:10:13.70ID:aXocYaHs0
>>891-894
ありがとうございました。

明日の午後9時からの「AtCoder Beginner Contest 271」に参加予定なのですが、
何問くらい解けるのが平均的なんですか？
100分しか時間がないのでおそらく2,3問しか解けないと思っています。
896デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 20:13:19.02ID:aXocYaHs0
大槻の『AtCoder入門』という本を図書館から借りてきて第5章の中級編の最後まで読み終わりました。
そこまでの問題であれば、時間がかかったものが多いですが、すべて独力で解けました。
2022/09/30(金) 20:23:47.23ID:5Nix2QT6r
そうなんだすごいね
2022/09/30(金) 20:30:00.67ID:CkroVdQhM
大槻って呼ばれてるの違和感しかない
899デフォルトの名無しさん (ﾜｯﾁｮｲ 5f01-JEMU)
垢版 |
2022/09/30(金) 22:00:39.59ID:vp8mMnx50
東大出身のNTTなら敬称は殿だろね。
本もたくさん出してるし。
2022/09/30(金) 22:11:04.33ID:0jY5NHsN0
参加者の過去の成績や練習量はすべて公開されています
実力のある参加者は大量の問題を解いています
自分の成績が今ひとつでも気を落とさないことです
901デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 22:17:34.52ID:aXocYaHs0
例えば、大槻の『AtCoder入門』という本の上級編の1問目の「abc115_d」の問題ですが、独力で解けました。
基本的なアイディアはすぐに浮かんだのですが、パスするのに1時間もかかってしまいました。
そして、練習を重ねてもこの時間を短くすることは難しいのではないかと思います。
902デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 22:20:59.94ID:aXocYaHs0
あと一つ質問ですが、問題の解答(AC)を、計算時間の短い順にソートすると、上位の
解答の計算時間が異常に短いです。

ソースを見ても、アイディアは同じなのになぜあんなに速くできるのでしょうか？

計算時間のコンテストではないので、レーティング上は、あまり重要ではないと思いますが、
気になります。
2022/09/30(金) 22:53:54.54ID:LLOTX79E0
解ける問題数については、三問解ければまずOKで、あわよくば四問解くことを目標にするぐらいじゃないかな
初回参加だとC問題解けない人の方が多そうな気がするし四問解ければなかなかだと思うよ
ABCは毎週開催されるようなものだし、一回一回の結果を気にしない方がいい、特に最初は
レートには直近10回程度の結果が反映されるから、今回失敗しても続けてればすぐにその影響を消せる
あと、参加回数が少ないとレートがめちゃくちゃ低く算出される仕組みなので、パフォーマンスを自分の成績指標として見よう
2022/09/30(金) 23:07:02.91ID:LLOTX79E0
平均的な話をすると、どうなんだろう
AtCoderから競プロ始めた人だったら一から二完の間じゃないかな、そもそもプログラミング初心者も多いし
あと、上級者のコードが速いのは、再帰関数を非再帰にするとか、キャッシュ効率をよくするとか、入出力を高速化するとか、コンパイラのオプションを変えるとか、そういう細かい工夫の積み重ねだと思う
C++だったら別に意識しなくても問題ない気がするけど、Python使いだったら再帰を非再帰にするとか入出力高速化ぐらいはやっとくと、ABC-E問題以降楽そう
2022/09/30(金) 23:13:27.03ID:LLOTX79E0
つけくわえるとABC-Dまではかなり典型度の高い定型的な問題が多いので、練習すれば解答時間は縮められる方の問題だと思うよ
2022/09/30(金) 23:17:37.45ID:Hduo0GQQ0
レートでいうと100で上位50%みたいな感じだった気がするし、平均的なひとだったら最初は2完で上出来かね
強い人だと初参加でも3完か4完らへんをやってパフォ1000超えてるのが珍しくないけど
2022/09/30(金) 23:53:23.95ID:bglqOH/20
こどふぉもやりたいけど23時半から2時間ってのが微妙だな～
眠くなっちゃうんだよなぁ
2022/10/01(土) 00:16:22.62ID:LpkgDzWuM
社会適合者⁉
2022/10/01(土) 00:18:46.82ID:WF3iEAg30
末尾再帰で最適化できる言語もある
2022/10/01(土) 00:23:21.36ID:3jdVdEDLr
schemeだけちゃうんけ？仕様で定められてるのは
2022/10/01(土) 00:31:45.72ID:8aXdhr6R0
再帰だとPyPyよりもCPythonのほうが早いらしいけど、なんでそうなるのか気になる
912デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM7f-poG4)
垢版 |
2022/10/01(土) 20:55:59.80ID:w1pBwNBnM
ヒューリスティックコンテスト向けのおすすめ本ってあります？
913デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/01(土) 22:48:49.05ID:DVLayUHe0
A, B, Dしか解けませんでした。
Cはソートして、巻番号が小さい順に見ていって抜けている巻を、巻番号がもっとも大きな2巻を売って買う
ということを繰り返せば良さそうでしたが、実装が面倒だと思い飛ばしました。
2022/10/01(土) 22:50:22.12ID:8aXdhr6R0
Cは二分探索を使う解法にすれば実装がクソ軽いよ
915デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/01(土) 22:50:52.66ID:DVLayUHe0
>>903-906,909-911
ありがとうございました。
916デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/01(土) 22:52:49.49ID:DVLayUHe0
>>914
ありがとうございます。考えてみます。
917デフォルトの名無しさん (ｱｳｱｳｳｰ Sa27-XVJY)
垢版 |
2022/10/01(土) 22:52:51.85ID:CG2rPef9a
Cはにぶたんが楽だったな
愚直にシミュレートしたら3wa,2wa,1wa,1wa…って感じになったぴえん
2022/10/01(土) 22:53:56.43ID:8aXdhr6R0
>>917
おれもシミュレートしたけどWAを潰しきれなくて、二分探索にしたら瞬殺できてなんか悲しかった
919デフォルトの名無しさん (ﾜｯﾁｮｲ 6fbd-atM5)
垢版 |
2022/10/01(土) 23:00:56.33ID:zvX3MF2G0
8月から競プロ始めて現在レート337の雑魚

Dは楽だったけどCでwa出してしもうた。。
明日のレギュラーも参加するか
2022/10/01(土) 23:08:50.61ID:Ry8jupv50
(N-最初に持っている本で読む本の数)/2 >= (これまでの不足している本)で判定すれば別に二分探索もいらないと思うけれど
2022/10/01(土) 23:11:38.80ID:Ry8jupv50
Exってこれ典型なのかな？
解説見てみたらどことなくARCの難問っぽいけど
2022/10/01(土) 23:20:11.35ID:YhoWw2wyp
ABCのDまでは安定して解けるようになったけどEになった途端全然安定しなくなるのシンプルに過去問解き進めるしかないかな
2022/10/01(土) 23:21:52.81ID:YhoWw2wyp
というかCの制限時間が4秒だったのってどういう想定？二分探索でもシミュレーションでも割と余裕ある気が
2022/10/01(土) 23:25:52.82ID:Ry8jupv50
確かにCの制限時間よくわからないね
set使うと結構定数倍重くなるのかな？
925デフォルトの名無しさん (ｱｳｱｳｳｰ Sa27-XVJY)
垢版 |
2022/10/01(土) 23:28:08.04ID:CG2rPef9a
パスの復元じゃなくDpの値にそのままパスぶっ込むのでもokにしたかったとか？
2022/10/01(土) 23:28:38.05ID:Ry8jupv50
ABC-Eは典型90の内容抑えれば結構戦えるレベルな気がするなあ
あとEDPC埋めとかね
2022/10/01(土) 23:28:53.28ID:8aXdhr6R0
入力が 3 × 10^5 コ以上あるときは、解法に関係なく少なくとも3秒以上になってるような気がする
2022/10/01(土) 23:31:02.64ID:Ry8jupv50
2*10^5でもいい気がするけど、それだと速い言語で二重に走査するだけのO(N^2)回とかが通ったりすることがあるのかな
2022/10/01(土) 23:35:23.86ID:Ry8jupv50
てか2*10^5でO(N^2)が2secで通るんなら、3*10^5のO(N^2)も4secあれば通りそう
あとは初心者が筋の悪い入力受け取りをしていたときにそこのオーバーヘッドで落ちるのを予防するとかかな
930デフォルトの名無しさん (ｱｳｱｳｳｰ Sa27-XVJY)
垢版 |
2022/10/01(土) 23:35:36.10ID:CG2rPef9a
あ、dじゃなくcか
2022/10/01(土) 23:47:22.98ID:Ry8jupv50
HEX
2022/10/02(日) 00:22:19.74ID:3PZJtakoa
サンプルでWAを出すやつはこれを使え〜
https://greasyfork.org/ja/scripts/433152-atcoder-easy-test-v2
933デフォルトの名無しさん (ﾜｯﾁｮｲ 6f71-0qRf)
垢版 |
2022/10/02(日) 01:34:13.68ID:FZycuJqr0
なんか文句いってたら数え上げとXORの頻度が減った気がする。このあたりほんとアルゴリズムと関係ないので燃やすべし。
2022/10/02(日) 01:44:55.64ID:cj6ZUnIP0
G問題がちょうど数え上げ+XORだったけど
組合せ論嫌うのもよくわからないね
2022/10/02(日) 01:45:17.65ID:cj6ZUnIP0
あ、Fだった
936デフォルトの名無しさん (ﾜｯﾁｮｲ 6f71-0qRf)
垢版 |
2022/10/02(日) 01:55:00.10ID:FZycuJqr0
>>934
数年前はこの類が毎週出てて違和感しかなかった、統計学でも数理最適化でも観測範囲内で組合せ論は二項係数くらいしか役に立ってないハズ
2022/10/02(日) 01:58:26.63ID:rnPodEBd0
競プロは役に立たない
938デフォルトの名無しさん (ﾜｯﾁｮｲ ff10-UJKs)
垢版 |
2022/10/02(日) 02:03:38.75ID:m2kqJsOp0
C、線形で解こうとしたんだけど、謎の1WAが出て困ってる
同じ1WAの人結構いたけど、みんな二分探索に切り替えてACしてる
https://ideone.com/yD7l3P
誰か教えて欲しい
2022/10/02(日) 02:06:44.15ID:cj6ZUnIP0
「競プロは自分にとって離散数学パズルだ」ってりんごさんが言ってるし、整数論とかやるのと同じような立ち位置じゃないかなあ
そもそも初等組合せ論の考え方は初等確率論の基本なんだから、役に立たないというのも違うと思うしね
今回はGも数え上げ問題だったわけだけど、DP遷移部分について俺は幾何分布の考え方をイメージしたね
940デフォルトの名無しさん (ﾜｯﾁｮｲ 6f71-0qRf)
垢版 |
2022/10/02(日) 02:10:22.92ID:FZycuJqr0
>>937
そう、別に個人的にはそんなに嫌いじゃないんだけど、好む層の魂の元が中学入試あたりで、自然数の各桁の和とか数学的に大した意味もないトピックがやたらドヤドヤしていたのがちょっと不快。プログラミング、アルゴリズム、情報科学というより、IQ高めの算数エリートの娯楽という感じ。
2022/10/02(日) 02:12:42.56ID:cj6ZUnIP0
>>938
貯めてるsellが足りないときに貪欲に大きい方の本を売ってるけど、そこで順当にいけば読めるはずだった本売ってるんじゃない
一冊残しておいた方がいい場合とそうじゃない場合がある
2022/10/02(日) 02:17:08.77ID:cj6ZUnIP0
>>940
魂の元が中学入試なのはまあそうって感じ
俺も算数パズルや離散数学よりも比較的連続最適化とかの方が好きっちゃ好きだから分からなくもない
まあでもCSでは離散数学は基礎教養だし、離散数学と中受算数は親和性高いよね
943デフォルトの名無しさん (ﾜｯﾁｮｲ ff10-UJKs)
垢版 |
2022/10/02(日) 02:24:07.54ID:m2kqJsOp0
>>941
ありがとう ACできた
シミュレーションしながらsellを貯めていくのはダメで、sellをシミュレーションの前に計算するようにしたら通った
2022/10/02(日) 09:47:36.55ID:nZxo1B790
重複する本は∞巻目ということにしてからシミュレーションしてもうまくいくよ
2022/10/02(日) 11:05:00.45ID:bP9R5MM60
小数点の精度はどうすりゃいいのか未だに分からん
興味がないねんな…
946デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/02(日) 12:40:51.35ID:c1nVdKJ60
米田の新しい本を買いました。
PASTの公式本とどちらを先に読むか迷っています。
947デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/02(日) 12:43:27.85ID:c1nVdKJ60
大槻のAtCoder入門という本は買わなくて正解でした。
図書館で借りて読めば十分な内容です。
948デフォルトの名無しさん (ﾜｯﾁｮｲ ff10-UJKs)
垢版 |
2022/10/02(日) 14:48:02.40ID:m2kqJsOp0
>>944
確かに その方が実装綺麗にまとまるね
2022/10/02(日) 16:15:35.42ID:FsOTPbTb0
正解です
2022/10/02(日) 16:49:02.85ID:eK4S0SoN0
>>946
大槻さんの本で初級用の知識は入ったんだろうから問題集に移ることをオススメする。
2022/10/02(日) 16:56:26.21ID:eK4S0SoN0
>>950踏んだけど立てられなかったから誰か立ててくれ
2022/10/02(日) 17:44:45.80ID:FqAfPtIrM
次スレ
https://itest.5ch.net/mevius/test/read.cgi/tech/1664700238/l50
2022/10/02(日) 17:58:33.59ID:eK4S0SoN0
>>952
助かったありがとう
2022/10/02(日) 20:39:28.28ID:RBz4Dz1b0
AHC、他の人の解法を参考に自分のを高速化しただけで60M超えてつらい
自分が高速化だと思ってコンテスト中やってたことが逆効果になってただけだったし
2022/10/02(日) 21:43:51.33ID:zlxZgBGt0
今ランキング見てるけど日本人多いんだね
まだまだこの国も未来がありそう（他人事）
2022/10/02(日) 22:03:53.70ID:bP9R5MM60
こどふぉのランキング見てると中国がスゲェ
957デフォルトの名無しさん (ﾜｯﾁｮｲ ffbd-atM5)
垢版 |
2022/10/02(日) 22:36:17.43ID:RAAxIiX40
コンテスト中に呟いちゃいけないんだろうけど

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


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


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

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

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

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

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

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

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

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

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

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

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

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

とできる場合でも、

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

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

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


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

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

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

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