競技プログラミング総合スレ 63
レス数が1000を超えています。これ以上書き込みはできません。
!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 SNSヲチ勢はNG推奨
健全な競プロスレにしましょう インドコンって特有の問題傾向ってあるの？
AtCoderは算数パズル多め的な感じの 苦痛なlog落としの問題とか謎い式を変形していく問題とか？
俺は知らないけどFPSを使う系の問題もあるらしい 結構勉強にはなりそうだね、atcoderにはなさそうな感じ
それだけ聞くと好きかもしれない 見てみたらインドコンのがコドフォより英文読みやすかった
英文はこっち標準がいい 競プロと関係ない馬鹿な話題が蔓延ってたから移行うれしい たったレス10個で落ちてなかったスレがあるから大丈夫そうな気がするけど 前スレで質問あるって言ってた人、こっちで聞いてみたら
俺も可能な範囲で答えるよ のいみ鍵垢なってるじゃん
非公開リストで見てたのに 8問ABC が始まったら AtCoder Problems の横枠？がまた狭くなるのかな
AGC-like とかもう問題名が何も見えんのだけども 25分後くらいにこどふぉ div. 2 です
夜更かしする人は出ましょう 米ニューヨーク市
7月30日以降のワクチン接種者全員に
100ドルを配布するキャンペーン開始 質問いいですか
Ford-Fulkersonの計算量O(FE)の最大流量Fって何のことですか？具体的にどう見積もればいいのでしょうか こどふぉのレートなんて溶かしても余裕じゃない？
橙から落ちるとかならありかもしれんが今日はDiv.2 only だし >>28
最大流量F ってのはそのままの意味で、 始点から終点へ流せる量の最大値
見積もりは難しいと思う。自明なカットで上界与えるくらいしかできないんじゃないかな
(辺容量の最大値) * (辺数) とか >>30
ありがとうございます！スッキリしました
AOJのVerify用問題も(辺容量の最大値)*(辺数)が10^7に収まるようになってるので取りあえずその見積もりで問題なさそうですね
（1/4とかの定数倍はつけてもよさそうですが）
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&;lang=jp 最大流が青までの問題に出ない教プロに何の価値があるんだろうか 蟻本だと中級だからそんなに発展的な内容という位置づけではないわな 最大流とかグラフ系を増やしてしまうと進学校の数学の先生が激おこですからね IOIシラバスで明確に除外されてるものは黄色以降でいいだろ こんなのがあるのか、有効グラフの連結分解が明確に除外ってw
https://www.ioi-jp.org/ioi/ioi-syllabus_jp.pdf
中高生の「事情」に一般人が配慮する一般向けコンテスト >>35
これはどう考え方？
ARCで前提にするつもりのテクニックはABCで出しておかないと
ARCがそのテクニックを学ぶための教育的コンテンツになってしまうし、ARCの位置づけはそうではないと思うんだが
一切出さないかABCでも出すかの二択しかないと思っていた
それはそうと実はCodeChef LunchtimeはIOIのシラバスに沿うというルールなんだよな
言うほど守られていないが >>37
ABCの600点(解けたらABC卒業;黄diff〜)
に少し難しいアルゴリズムを出すことは否定しない >>38
なるほどだけど、少し難しいアルゴリズムが結果的に青dif以下になるなら点数にはこだわらなくていい気がするなあ
本当にフロー流すだけ、とかはIOIで除外されてるけど青ボーダーくらいになりそうだし500点ででても違和感がない
(そんなん出すなよ、というのは一理はある) ZebranessとかGrid and Tokensは黄diffだったねえ アルゴリズムってなんでこんな仰々しい名前多いんだろ
連鎖行列積問題とか行列積コスト最小化問題って書いてたら、何となくやってること分かりそうなのにわざわざ難しく書く matrix chain multiplicationの直訳だからじゃない
日本語だと仰々しいが英語だと簡潔
どっちも最適化する対象が名前からわからんけど そもそもそれDPでとける問題の名前であってアルゴリズムの名前じゃなくない？ 行列積コスト最小化問題だと行列が3つ以上あるように見えないな
英語のchain要素は欲しい 行列鎖積が限界じゃない
方鎖積とか言い出すと意味が取れなくなって危険 8問楽しみだ
1問1問にどこまで固執して良いのかな見極めが重要そう 緑〜水difの問題生やすの難しそうだよな…Writerは頑張って欲しい そういえば4問ABCから6問ABCに変わった初回はunratedになったのを思い出した
今回も参加者増えてジャッジ詰まらないか心配 171 仕様書無しさん sage 2021/07/30(金) 19:51:47.26
IDありの方でいい感じに自演してるけど楽しい
こっち見てない人多そうだししばらくバレなそう 今日は yukicoder と Educational なこどふぉです まあIDなしスレの方でこのスレについて適当に煽るやつが出てくるのも自然ななりゆきだな ABC unrated なら インド優先でいいんでないか
トーナメントは知らん 直近コドフォAの考え方教えてください
自分は小中大のスライスの数が3:4:5なので、その辺りから必要な枚数をO(1)で導こうとしたのですがうまくいきませんでした
答えが小中大の枚数に関わらず(n+1)/2*5だなとわかった人はどんな発想でそうなったのか知りたいです
よろしくお願いします
ちなみに関係ないかも知れませんが女子中学生です >>64
小中大も単位枚数当たりにかかる時間が同じ
拡張ユークリッド互除法の観点から、ある程度大きな数の偶数は、6 と 8 のペアの組み合わせで作れるみたいなのがある (実際には 6 以上の整数すべてが 3 つのペアから作れる) 8問ABCか
黄パフォラインは1-2-3-4-5-6の組み合わせで6完とかかな？ 4問から6問への移行のときも参加者増えてたし今日は少なくとも9000人は参加しそう
多けりゃ1万 4問から6問のときはrated対象変化のほうが大きそう
今回はそこまで変わらないと予想 問題数の多さに嫌気さして減るまであるかもね。実質何にも変わらないとしても 解説放送、スタイル変えないなら深夜3時コースじゃん Fが実装難でGが数論の中レベル典型という感じで難度逆転か
数学問はAtCoderだとみんな解くからね Fが実装辛すぎて震撼してたが、終わってみるとこれに数十分掛けてるようでは。。という気持ちになるんだよな
実装難問題はだいたいそうなんだけど 今日の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)に替えたら全部通った。
ドンマイ、俺 つまらない実装ミスでF問題落として魂抜けた
ちゃんと大きめのサンプル作って試していればよかったのに Aの提出者数8554 -> 7822か
700人くらい減ったな ratedの人でGH解けてる人どれくらいいるのかな G は知識があればなんとかなる
H は畳み込みをブラックボックスとして使ってた人は厳しいかも rated だけど E までは簡単で考察も実装も F より G の方が軽かったし、G は無限人解けてそう
H は知らん 難易度若干シグモイドっぽいの解消して欲しいな(難しいとは思うが) Gは位数とか原始根みたいなちょっと進んだ整数論を学んでたら知ってるような概念割とそのまんまなので、考察負荷も確かにそんな高くない
Fも考察の本体は「あるバスに乗ったあとに乗るバスがあるとすれば一意に定まる」に気づいて超頂点を作るだけな気がするけど、ダブリング二分探索みたいなおまけ部分が重い
AtCoderで重実装問の後ろに軽い数学問出したらそらそっちに流れるわなという >>83
C茶、D緑、E水、F青を目指してたんだろうなと思ってる
CDEはその点ちょっとブレただけで割と悪くないのでは？
Fは運営がユーザーの実装力を過大評価してたといういつものやつ >>85
いまグラフ作ってたんだけどまさにその通りだったわ
https://i.imgur.com/tQx8HP0.jpg
Fがもう少し低ければめちゃくちゃいい勾配のセットだったんだな、惜しい >>86
やっぱFだけおかしいね
どうすりゃよかったんだろう
最初から逆有向森？みたいなのを明示的に与えてあげるか、バスに乗ってる時間を無視してよいとするか Fは100分6問のFならもっと解かれたはず
解けそうなやつがGにいっただけ 同程度の難易度の問題が500と600にあったらコスパ良い600の方が解かれるのは当然
600の方がちょっと難しかったとしても、つまり難易度は逆転していないとしても、diffが逆転することは全然ありうるよな
そういう意味でdiffを重視しすぎるのはどうかと思う 今回のE問題までのほぼ直線的に解いていくしかないような問題配置以外では、diffは問題難度を評価する指標として微妙だとは思う 確かにこの難易度帯が解ける人にとっては実装が重そうなこの問題よりも発想さえ出来れば解ける得点が高い方に流れるか
そうなると問題数増えて時間同じままだから、実装重い問題は忌避されていくんだろうなあ 問題単体の難易度をより正確に評価できるようなdiffに代わる指標ってありうるかな？
diffの定義式にちょっと変更を加えるとかでも 昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた 昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた Eは俺はTDPC-Rグラフの変形だと思って解いたね
全頂点対だとO(N^3 logK)だけど一頂点対についての問題だから大分計算量節約できそう的な tdpc-rってsccしてdag作ってトポロジカルソートするやつじゃなかったっけ？
共通点が見えんけど Heuristicの方ってABC全完できるくらいの地力ないと難しいかな？
楽しそうだけど実装の方針がよく分からないです 多分 EDPC R と間違えてる
自分には補グラフの形式で与えられてることが本質だと思った >>98
マジだ
すまん、EDPC-Rのwalkの方だな
どっちもRで大体この辺にあったグラフの問題だよなあって感じで覚えてて、問題開いてよく確認してないから間違えた 遷移の節約がメインって考えると確かに補グラフが本質か
むしろ行列累乗の発想を使えないからwalkの本質的な部分とは遠いかもしれない
そもそも俺はDPを一から生やすのが苦手な方だから、DPのテンプレとして既知問題が役に立ったという感じかな >>99
俺もheuristic全然できないけどそんなことはなさそう
基本的なアルゴリズムの組み合わせで解を探索してあげるのが主だからそんなに高度な知識はいらないって聞いたことがある ナップサックだと嘘になるような貪欲でもheuristicだと十分な解法になり得る
ちゃんとした貪欲が書けるだけどもかなり強いよ >>99
Heuristicsは貪欲書けてBFSとDFSができれば何もできないってことはまずないと思う
あとは勇気を持って噓貪欲書いて、結果をビジュアライザで見ながら改善していけばいい クエリのやつABCで復習したのですんなり解けてうれしい 制約がn=2*10^5とかで想定解がO(n)なのって出題者の優しさでしょうか
それとも定数倍とかの関係？
O(nlogn)解で通った人← N と NlogN の区別はなかなか厳しいことが知られております
N 個の入力を与える問題なら問題を解くより入出力を捌く時間の方がネックになるなんてこともある 入出力数がO(n)ならn=10^7とかにするとそこがボトルネックになって非本質ゲーになりがち
あと遅い言語でO(n log n)落としてO(n)通すように設計するとC++ではO(n log n)が普通に通るなんてことがある
logを落とす力を評価するコンテストサイトもあるっぽいけど、AtCoderは入出力ゲーとか言語格差とかそんなに好きじゃないのであまりそういう力は問わない 一応ABC189-Cがlogの有無を意図してるっぽい セグ木上の二分探索とかlog二つをlog一つに落とせて嬉しいパターンが結構ある気がする log x × log xのことじゃね
log log xではなく 最近競プロで必要そうな知識を整理してて、集めるとそれなりの分量になるなと思った反面、AGCの難問には基本的な知識しか問わないけど難しいものが結構あるよね
多分知識入れただけじゃ解けるようにならなそう
どうやって練習してる？ 高1でatcoder赤になった奴、東進全統高で上級生抑えて一位だな。
プログラミングと受験勉強の配分はどうなってるんだ? 全方向に才能が溢れていた結果としてAtCoder赤になったのであれば、受験勉強も軽くクリアできてもそんなに不思議じゃない AGCもなんだかんだで練習量でそこそこ溶けるまでは解ける
個別の練習はやってないや >>123
結局演習量という話はよく聞くね
>>125
ありがとう、読んだことないや
目次を見たけどかなり競プロと相性がよさそうだね なんかのめり込んでる時期はAGC全然勝てなかったけど一旦離れてたらいい感じに力抜けて苦手意識なくなったな あるある
めちゃくちゃやってた時期よりもレート伸びてるわ今 ここしばらくコンテストしか出てないけどレートなんやかんや上がってるわ エレガントな問題解決ポチった
数オリの問題も結構含まれてるっぽくて楽しみ >>130
英語版の公式サイトに解説マニュアルあるよ。載ってるのは選ばれた問題だけだけど PaizaってAからやたら計算量ギリギリな問題が多くなる気がする...
TLEで一発終了なのがキツい >>131
ありがとう
届いたから読んでるけどまさに算数パズルという感じの問題が集まってて面白い
普通に演習問題の中に難しいのも結構あるから世話になるかも 132だけどやっとA取れました...
茶色になった記念でpaizaに挑戦したけど意外と苦戦した
Aの美術館のセキュリティって問題でasin,acosが出てきて三角関数の逆関数の使い方を色々学べて楽しかった(これだけじゃネタバレにならんと思う)
asinは終域が-π/2〜π/2で全単射
acosは終域が0〜πで全単射だからモジュールの仕様で出てくるradianに気をつけないといけないんよね 解答の本質とは関係ないぐらいの書き込みなんだろうから直ちにアウトってレベルじゃないと信じるけど、事前に要求知識が分かるだけでも微妙なのでやめといた方がいいと思う
あれ提出までの時間も評価対象だし 誰も聞いてないのにスレチのpaizaのネタバレを始める茶色 rated砂漠の時ってみんな過去問解いたりしてんの？ 山ほど溜まってるコンテスト中にACできなかった問題を処理してる
rated 砂漠時に限らないけど leetcodeのLISをO(nlogn)で解くってググれば出てくるんで典型なんですかね？
もしコーディング面接だったら解ける気がしないですね diffよりも正確な問題難易度の指標ってないだろうか
chokudaiはdiff信仰をやめろって言ってるけど現状問題点数が全くあてにならないから結局diff見るしかないんだけど >>145
勉強として考えるなら適正問題探す意味は薄いけどさ
今の実力でぎりぎり解けたり解けなかったりする問題がすぐにわかったらゲームとしては遊びやすくて嬉しくない？ >>146
その使い方なら diff 程度の信頼度でも十分だと思うけどどう？ 一元的な指標を作るのは難しいね
ただ点数、diff、平均AC時間、ABC or ARC or AGC、コンテスト中の問題の位置あたりを使えば何かしら予測できそうではある
あと難易度評価と言えばAOJ-ICPCの投票システムとかも悪くなさそう Tree Gameとか問題だけ見たら黄diffがいいところなのにAGC-Fに置いてあるってだけで赤diffなんだよな
diff、点数、出題時期、傾向、コンテスト時間、点数、問題位置あたりをパラメータにしてなんかすごいパワーで問題単体の指標が出来たら嬉しそう >>150
そんなことあるのか…今回のABCも8問になったから多すぎて終わらんくてHが赤difとかになってしまったのだろうか 分割統治FFTはtwitterの人々の反応をみても知識レベル的に橙〜赤はあるようには見えるし、今回はそんなに極端に上がったわけではなさそう
ただ、今回のFレベルの問題が仮にHの位置にあったら橙diff上位になるみたいなことは普通にありえそう 8問制になったことで今まで以上にdiffの信憑性がイマイチになりそうなんだよな
EFGHのうち典型3問、実装1問だとしたら
実装問が難易度的には一番易しくても橙diffとかになりかねないし
diffにとらわれず全部覚えろという意見ももっともだが、なるべく効率的にやっていきたいので
やっぱりよりよい指標ができたら嬉しい EをFGHと同じ括りにしてるのよくわからないけど
毎週高々三つなら全部やればいいじゃんとしか 新しい知識週3つ身につけるのって結構しんどくないか Fは500点問題としては難しかった。6問の時のFのままの難易度では。 くまくまここ見て誕生年変えただろ、案外見てるもんなんだな ABCで明らかにRatedが解けない様な問題たくさん出してるのってどういう意図なのかな 高難度典型枠は高レベル向け典型90としてみるとありがたいけど、だったらストレートに高レベル向け典型90という形で出してもよかったんじゃないかなあとも思う
界隈の知識レベルを向上させる？みたいなコンセプトそんなに悪いとは思わないからさ ratedが解けない問題出す云々は他のコンテストでもそうじゃないか？
ARCの後ろとかもそんなもんだと思う ARCもAGCもratedで全完が出るかどうか、くらいの回が多いしABCもそうなっていくのかね
一般論としてはratedが全完同士のスピード勝負になるよりは上から下まで点数の勝負になるほうが健全と思うけど、
ABCは上位のかなりの人数が2400になるから全完多めでも問題ないはずなんだよな 平成ABCでのまぐれ全完が最初で最後の全完になった ABC全完しても2400パフォ出ない簡単回が続いてた頃より今の方が好みだな まあ色々文句も出てるけど、e問題までは確実に以前の難易度に戻ったから良かったと思う それはほんとに思う Eまで大分解きやすくなったよね ありがたい EはABC198以前の難易度になった感じかな
まだサンプル2だしE青パフォとかになることもありそう 社長曰く
Easy/Easy/灰-茶/茶-緑/水-青/青/黄-橙/黄-橙
辺りを狙っていくとのことだったので、E青は全然ありうると思う
現時点ではFが思ったより難しいのがアナウンスと異なる点 それな
試してもないのに解ける問題数が〜みたいな社長の妄想によりそうなってる
初心者にオススメのコンテストは英語に抵抗なければCF Div. 3だわ こどふぉは Div.3 だろうが A の時点で for かけないとキツい >>167
なるほど、たしかにRatedで全完する人がいっぱいいると、スピード勝負になっちゃうもんな
全完をちゃんと狙うのはABC卒業してからだな for文書けない人に配慮する前に気にすべきことがあるんじゃないかとは思う こないだのA問題は実質的にfor書けない人配慮してないと思う ACLにあるけどあえて自作したライブラリあったら教えてください
その理由も 前から持ってたやつが結構あって、自分で作ったやつの方が慣れてるからそっち使うことはよくある
ACLのが基本よくできてるが ACLできた時点で大体持ってたな
floor sumとかconvolutionあたりは持ってなかったからACL使ってる 由は負辺対応してない、双対変数の復元がない、計算量が悪い そういやACLが登場したけどまだABCでネットワークフローの問題でてない？ 全然GH見てる余裕なかったな
Gは時間が十分あったら赤diffというほどは難しそうに見えない、ARC中盤で出したら黄diff上位〜橙diff下位ぐらい？ 包除原理知ってるなら時間あれば解けるはず
多分橙もいかないと思う って思ったんだけど ARC121E で橙あるのか、じゃあ橙行きそうだ 時間足りなくてコンテスト中に見れなかったけど、GよりHのほうが簡単に感じた 問題見たけどまさに負辺対応mincostflowを実装できますか？という感じだ >>193
そういうCSっぽいのを出すと受験を控えた電通のご子息の負担になってしまうんよ >>205
新ABCで3回は出てるし、皮肉が成立してなくないか Eは典型とかFは典型とかいう意見を見たけどほんとに典型なん？あれをはい典型だねと思って解けるようになる未来が見えないんだけど Fはけんちゃんのそのまんまの記事があるから流石にね プログラミング初心者にアルゴ式勧めてる人ちょくちょく見るけど
AOJ の ITP とかのほうが良くないか？ Eは確かにありがちな貪欲っぽく見えるけど、典型だとしたらどんな名前がついてるのか気になるな 先週のDってKruscalとPrimのアルゴリズムを実装したことある人なら簡単だったのかな
緑だと厳しくて水の人らはそこそこ解けてるからこの辺り知識差がでたのか マトロイドは勉強したけど青黄往復レベルの自分だと直接的にそこまで役に立ったことはまだないかな
クラスカル法の一般化として理論は面白い、電気通信大の資料で勉強した
問題に出てくる対象がマトロイドになってるとわかると直感的に明らかでない場合も貪欲でできるとわかって嬉しい
けどそもそもマトロイドであることを初見で見抜いて示すのがそこまで簡単じゃない
自分の認識はこんなもんだけど橙以上の上位陣がよく話してるマトロイド交差みたいな上位典型もあって、自分が把握してない活用法がまだまだありそう あとこの前のABC-Dではあまり最小全域木アルゴは意識したつもりはなかったけど、辺を段々追加して動的に管理するみたいな発想は確かにそのあたりのアルゴの影響で思い付けた可能性はあるかも
どちらかというと主客転倒がメインで、辺が寄与できる範囲の木を作ろうという気持ちだった 辺の寄与考えると小さい順にやるのがよさそうで、これクラスカル法じゃんとはなったな
俺はどっちかというとABC120-Dのお陰で思いつけたかな >>216
ちょうど水色でなんとかそれ解けた、ってレベルだけど、
似たようなアイデアを断片的につかう問題をいくつもやってたからたまたま解けたって感じ。
やっぱ解きまくって典型解法に習熟するのが重要なんじゃない？
初等レベルの算数でも足し算、掛け算、割り算の筆算は練習しまくらないと慣れないし。
ちなみにクラスカルは楽勝に実装できるけど、プリムのやり方忘れたやべえ。マトロイドはなんのことだか知らんがな、って知識量。 Eの後ろから見るアプローチ天才過ぎる
類題あったりします？
ゴールから考えるのに近いですかね E は今日の div.3 の中では一番 adhoc 気味かもしれん
後ろから見るというより最後に付け足した文字列は何になるかというのを考えると自然かもしれん ABC214-Dが茶色予想だったってchokudaiがあーだこーだーで言ってたね
・辺をコストでソートする
・Unionfindで管理する
って普通の人はクラスカル法を理解してないと着想難しいし、あれが茶色は流石にないでしょう 逆にクラスカル法理解してれば無だからなあ
どの知識が何色かなんてこの漢字は何年生で習うでしょうってくらい難しいししょうもない クルスカル法を想起させたいなら最初から木構造にすな あれそんなにクラスカル法結び付く問題かなあ、実装方針が外形的に同じなだけで本質的な部分は別だと自分は感じたけど おれもそう思うわ
たまたま実装方法がクラスカルっぽくなっただけと感じる 解いてるときも、別にクラスカルのことは連想しなかったけど、解けたし。 考察全部終わってからクラスカルだなとはなったけど最初からクラスカルは違う気がする 最小全域木やるだけは水色くらいありそうな気がするが…
ufやるだけが茶〜緑くらいのイメージ 一昔前ならUF使えて茶色なんてこと絶対なかったと思うんだけど、厳しすぎない？ 知識問のdiffはこれからも下がっていきそう
昔より初級者はちゃんと勉強しないとレートが上がらないゲームになってるとは思う クラスカルとは全く違う
クラスカルは最小の和が欲しいから、小さい方から貪欲に見ていくのであって、今回のは各辺の寄与をみるのに小さい方からみるとうまくいくというだけ
アルゴリズムが本質として違いすぎる クラスカルとは違うけど枝を小さい順から見ていってunionするとか、プリムとは違うけど頂点集合のカットから最小の枝を選ぶとかの考え方を1度やっておくと
別の問題に帰着できそうね 今日のFGHなにが出るだろうか
幾何系がそろそろ出てもおかしくないよね 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 は我々に教えてくれます 今回は比較的調整がうまく行ってる方なのかな？
Gは困難というほどでもないし、Fもちょうどいい塩梅 今日のC問題、26^8の並べ替えは全探索は無理と思ってたけど、8^8の並べ替え考えればいいんだな。 原理を知ってると応用がきくって基本だけど大事よな
今回のD 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の平行移動が計算可能 何言ってるのかと思ったけど一般の FPS だと定数項を含む式は合成できないってことか 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 は我々に教えてくれます >>254
>>255
ありがとう
最初Nが有限じゃなきゃ意味のない式だから確かにFPSじゃなくて多項式において適用可能か程度の認識で読んだけど、そもそも根本的に定数項を含むFPSを他のFPSに代入しちゃダメなのか
恥ずかしながら理解してなかった
確かに一般のFPSに1を代入したら容易に定数項が発散してしまうね
0に何掛けても0なので0次の項が爆発してしまう ARC125-DのBIT使って解くパートがよくわからん教えて dp[i]を先頭i個について最後の要素を必ず使う場合の答えとかしてそのままBITに乗せればいい ざっくり読んだけど、大意としては白カピさんが前言ってたようなことと大体似たような感じ？
優秀なITエンジニアを目指すことと競プロを突き詰めることは分けて考えた方がいいというのはまあそうだよねという感じ 独創的な問題じゃなくて、
「このような要件を持ったRailsアプリを作りなさい」
というのが実際に求められることだからな あと競技プログラミングで作ったものって
他の人の役に立たないよね？
あんなに優秀（笑）な人が時間をかけて作業してるのに
競技プログラミングの成果は無駄になる
ものづくりのためにあるプログラミングなのに物を作らない
ものづくりに必要ない技術の競技なってるから役に立たない 入り口の段階でコーディングに慣れたり頭の体操ができる的な効用はあると思うけどねー
まあ趣味なので一定レベル以上でそんなに実用的な期待のもとにやってる人は少ないと思う 黄 abc卒業、一つの到達点
青？
水 アルゴカンスト
緑 業務上は十分
茶 入色！
なんか青だけ中途半端だな。自分の立ち位置をうまく説明できなくて就職も失敗しそう クイズ・頭の体操・コードゴルフ
プログラミングのお題スレとか、上田隆一のシェル芸と同じ Codeforces の時間は終わりました
来週の放送時間は未定です >>266
それ書いた頃から色１つ以上ずれてる予感
最大流が青以下で出てない以上黄色でもカンストしてないし、灰色で高度なグラフや最適化アルゴリズムを実用レベルで使うことも可能でミスリーディング
今のatcoderはアルゴリズムをダシにしたただの算数パズル アルゴ力カンストしてます！とか言われても笑ってしまうわ こどふぉは B で詰まりまくって爆死した
整数1, 2個与えて計算してくれみたいな感じの問題が苦手っぽい グラフアルゴリズムを使えなくても、整数問題と漸化式と関連してdpが使えれば最悪青までいけるように調整してきたのがatcoder、受験生に優しい 門外漢に説明する場合実態よりも社長のブログ記事やから こどふぉB、所謂整数1,2個系っぽくはない気がする 普通のDPであまり数学っぽくはないというか 牛ゲーっていうんだこれ
G問題なのにad hocで妙だなって思ってたけどちゃんと高度典型に関わる問題だったんだね
牛ゲーへの帰着よりad hoc解の方が簡単で結果みんな解けているけど Gまで比較的簡単だったことを考えるとなおさらHが際立つね 公式自体は知ってたけど固定されてるパターンしか見たことなくて応用できなかった ああGは区間スケジューリングみたいな貪欲でいけるんだ
天才では？ 牛ゲー理解したけど、これ知ってても帰着に訓練が要りそう 最短経路問題に帰着したあと、負辺に悩んだ末にグラフの特殊な形を利用して準線形にしたけど
解説見てなるほどなあとなった
初手で反転するタイプのやつ全般、いつも見落としてしまうな Combined で E 通してる人と同室になる確率が低い なんの話かは知らんけど解説そのうち出すよといって何年も放置されてる問題は存在する 日本語圏を掘るだけでもかなりの知見が発掘できるように中国語圏にも知見がたくさん集まってると思うんだけど、なんかまとめてるサイトとか知ってたりする？ ジャッジでよく聞くのはluogu libre uojとか？
個人ブログはcsdnで書いてる人が多いイメージ >>290
ありがとう
csdnはUIがどことなくredditに似てるね
多分zennとかqiita的なサービスなんだと思うけど
競プロは競争性編程(の簡体字)というみたいだ https://oi-wiki.org/
ここにまとまってる知見だけでもかなりの量 大半は日本でも広く知られていそうだがときどきマニアックなのが紛れ込んでるな >>293
これはすごい…
Chtholly Treeとか初めて聞いたな
前のABCに出てきたLGV公式とかも当然載ってる Eみたいなの新しいデータ構造を作ってみようみたいな感じで面白いと思ったな vEB木って俺の考えた最強のデータ構造感があってかなり好き
実践では使わないけど 逆にCみたいなのがプログラミングしてる感あって好き DPだと添字いくつあってもいいのに
幾何学が絡むと二次元でも頭が爆発するのなんでだろう 算数パズルと叩きまくれば普通のプログラミングやアルゴリズムの問題が増える https://twitter.com/kyopro_friends/status/1436693258298482688
を見るとABC218-Gがpriority_queueでも解けるように読めるんだけど、今回みたいにバックトラックが必要な場面でもこのテクニックは使えるもの？
multisetみたいに任意の要素を削除できないと厳しい気がするんだけど
https://twitter.com/5chan_nel (5ch newer account) 誰かが削除可能priority_queueのテクニックを紹介してた 出来はするけど面倒だからmultisetで書いた方が楽だと思うよ なるほど…確かにこれなら削除できるね
言われてるようにmultisetのほうが楽だからあまり使わなそうだけど、勉強になったよ
ありがとう なるほど
priority queueのメリットといえば定数倍の速さだけど、こっちの方が速かったりするのかな？
maspyさんはコドフォでは普通にC++を使ってるイメージ priority queueから削除が要る時は、追加する値を2倍+1、削除する値は2倍にして
同じキューに突っ込んで、取り出した値の下位1ビットが0の数だけスキップする
最強園児の選別でそんな感じのものを使った気がする レート付き園児が出てくるやばい問題ね
min、maxおよび定数個のk分位点の取得はpriority queueでほぼ代用可能ということかな
検索は大体どの言語にもあるunordered_setで代替できる
lower_boundとかは無理そうか
まあ、平衡二分探索木の代用だとクエリ先読みできるんなら座圧BITの方が直感的にわかりやすい気がするけど Ruby だと想定解通りに書いても遅くて通らないの何なの?言語差別なの?俺にCrystalの道を示してるの? Rubyが遅すぎるんじゃないのかな使ったことないから知らんけど
余り遅すぎる言語に合わせるとC++とかでクソ解法が通ってしまうからしょうがないような気もする
一応Pythonなら通せるようにする方針らしいけど Rubyはインタプリタとしては遅いわけではないが、JITコンパイルでもあまりはやくならないのが厳しい。PyPyのように速くなるものがあるといいんだけどね。 C++の軍門に下るかCrystalを極めるかしかないのか
昨日と先々週のD問題は想定解書いても通らなかったし、悔しいけどもうRubyじゃ無理なのか Ruby書けるならCrystalはすぐ書けるようになるよ。ほとんど同じ。
むしろ型アノテーションが使える分、Crystalの方が書きやすいまであるかも。個人の感想です。 crystalはほんとよくできてるよね。静的型、null安全を実現しつつもrubyistがこだわる「rubyらしさ」がほとんど損なわれていない RubyはC++と比べると100倍ぐらい遅かったりするんでしょ？
制限時間を緩めてもらわないとさすがにキツそう コンテスト前に抜くとパフォーマンス出ないジンクスあるからコンテストある日は禁欲してるんだけど、
みんなはそういうのある？ パスタじゃなくて米を食べるようにしている
なんか知らんが気分的に米の方がパフォーマンスが出る、自分にそう言い聞かせてるだけかもしれんが テンションの上がる音楽をかけながらだとパフォーマンスが上がる気がする
だいたいシューティングゲームのボス戦の曲だが... トイレの使用時間がT秒以下の時は「おしっこ」、超えるときは「うんち」と出力せよ Cを差分に言い換えてあぼん
いやまあ差分の方針でもいけないことはないけど見通しが悪い C問題、よく見ると双対取ったら二変数のLPだからSeidel法でexpected O(N)？
気づけなくて悲しい 今回のHは典型知識なのかな
あんまりad hoc要素を感じないけどかなり強い人でも解けてない気がする Gは木を二部グラフ(V1×V2)とみなして大頂点S, Tを追加してSからTに最大フローを流した状態の残余グラフについて考えたら解けた
v1 ∈ V1, v2 ∈ V2がマッチしているとして、v1 → S → … → v2 → v1みたいなサイクルがあることがv1を消しても別のマッチを作れる条件で、
v1, v2, Sがすべて同じ強連結成分に属するなら消してもOK、だめならv1は消せない、と考えると通った
「残余ネットワーク上の貪欲は正しい」としか覚えてないので厳密な証明はよくわからない…… ↑別に難しくなかった
最大フローを流した状態の残余グラフを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)))とかで解けてそう >>337
いまいちわかってないんだけど
V1 = {2}
V2 = {1, 3}
2-1
2-3
という二部グラフで S->2, 1->T, 3->T みたいに張るとS を含む強連結成分ってSのみにならない？
ST両方について解いてる？ >>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を消すと増加パスが見つからない フリーランスに立ちはだかる「常駐」の壁。慣例を打ち壊し、
“テレワーク”案件3割→8割へと成長を遂げた「クラウドテック」の軌跡
リモートワーク求人専門サイト「プロリモート」がリニューアルオープン、業務委託契約の求職者と企業をマッチング
1/3以上が採用につながる高マッチング率、リモートワーク×エンジニア・デザイナー専門の
人材紹介サービス「ReworkerAgent」正式リリース場所からも時間からも自由な働き方を実現！
茨城県日立市、県外からの「テレワーク移住者」に最大151万円の助成金
長野市、市内に移転・事業所設置し、移住することで最大550万円の支援金を支給
フリーランスが活用できる「最大1,000〜3,000万円・補助率50%〜75%」の
『ものづくり・商業・サービス補助金』とは？概要や条件を解説
『ReWorks（リワークス）』リモートワーク特化型転職サイトとして 3月5日 リニューアル 最近某ngtの質問箱に毎日のようにキモいのが送られていて、流石にかわいそうになってきたな。 最近始めたけどついさっきああでもないこうでもないおかしい計算が合わないみたいなこと延々とやってC問題一つ解くのに2時間半かかった
辛い 数学ではよくある考え方やテクがABC-Cから登場すると思うけど、基本的なものでも初見だと難しいものが多いと思う
最初からスムーズに解ける人たちは散々似た考え方に慣らされてきた人たちだと思うし
ABC-Cぐらいの数学的思考の素養ぐらいは身に付けておいて損はないと思うから、慣れてみるといいんじゃないかな グラフや木の問題だったら手癖でよくあるケースを作れるようにしたりして実験そのものをスムーズにできるようにしたり
愚直解の実装を早めにやるように心がけたり
ありがちな注目すべき量(パリティー、剰余、木の葉の数、木の直径、頂点の次数、連続する二項の差分、転倒数、総xor…etc)の知識が増えてくるとエスパー精度上がりそう、俺自身実験エスパーそんな得意じゃないから知らんけど C問題ぼちぼち解けるかなくらいのレベルなんだけど時々手も足も出ねぇ…ってのが紛れてて辛い
まぁそういうのは大体みんなの正答率も低いんだけど AGCの問題の解き方わからんね
昨日も、Bは不変量見つける感じで典型要素があるといえばあるけどAとかアドホックすぎる AtCoderの「第二回 アルゴリズム実技検定」のテストケースはどこにありますか？ dropbox に上がってないのなら無いんじゃないか ちょっとずれた話題になるけど競プロ好きな人ってどういう方向の就職が向いてるのかな
よくある金融系とか医療とか販売サイトとかそういうのが全然ピンとこない。ロジックを考えるのが楽しいのであって何を作るかにあまり興味ないというか… paizaのSを全解き目指してるレベルの者だけど、>>345の意見には納得するところがある。
競プロやる前は、クラス定義してDictionaryでどうこうすれば、大抵の問題は片付いた
わけだが、競プロの問題ではクラスなど定義していたら時間切れになってしまうので、
配列だけで何とかするという、文法的にはレベルの低い書き方をして、いかに実行時間を
短くするかということに主眼がおかれていると思う。ビジネスで使うには10の何乗という
データ数はない場合がほとんどだし、計算に１週間程度掛かるのも問題ないことが多い。
競プロ的な書き方をすると、他のプログラマーとコーディングスタイルがかなり異なって
しまうと思う。 paizaはatcoderと比較して時間制限が緩いし、その制限に間に合わないときは、
他に最適なロジックがあるってことだと思うよ
あと競プロを解いていると、自分が知らないやり方とか、効率の良いやり方を
知ることができるということが大きいと思う
意外と文字列と時間の細かい扱い方とか知らないことがあるので
それを知るきっかけになるので勉強になる その是非や影響の議論は置いといてAB難化は事実だと思うんだけど、copilot対策という噂は本当なのかな？ ソースは特に見当たらないけど、それ以外にABを難しくするモチベがあまりなさそうだからそう言われてる
あとは精々、企業コンではあまりにもひねりのない問題の出題は避けてるとか？ 競技プログラミング的なロジック組んで金になる方法考えてみようぜ
とりあえず俺は自動取引系ソフトに一票 ABC226-H の解説に類題として挙げられていた以下の問題が解けません
> 区間 [0,1] 上に一様ランダムに区切り線を n−1 本入れて n 個の区間に分けた時、 k 番目に短い区間の幅の期待値は？
ABC226-H 自体はすんなり解けたのですが上の問題は正直N=3の時点で自分には手が出なくて、困ってます まず、k=1はわかりますか？
これは期待値がx以上になる確率を考えるとできるはず（累積分布関数を考えているという点が類似ポイント）
で、一般の場合は包除原理を適用するとできる
途中式省くけど答えは1/n (1/n + 1/(n-1) + ... + 1/(n-k+1))になります ええと、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
みたいな感じでいいでしょうか >>367
355だけど、役に立つよ。頭の体操になる。数学の問題を手で解くより面白い。 問題解くときの計算用紙代わりにブギーボードとかの電子メモ帳を買ったんだけど書き心地良いしかなり良かった
おすすめ >>366
0とmax取るか積分範囲を1/nまでにしないと壊れると思うけど合ってる 「ゲームで金儲けする時代止められない」ＣＣＰゲームズ代表インタビュー
「CCPゲームズ」のヒルマ・ベーガー代表は14日、オンラインインタビューで最近、
話題に浮上した「プレイトゥオン（Play to Earn 儲けるゲーム）」について「世界のゲーム業界には、
すでにゲームアイテムを取り引きする2次市場が存在する」とし「儲かるゲームは以前にもあったし、
これからも止められない流れになる」と診断した。
CCPゲームズは、世界的な人気ゲーム「イブオンライン(Eve Online)」を開発・運営する。イブオンラインは、
世界で4000万人以上が楽しんでいる。
CCPゲームズは最近、NFT（代替不可能トークン）コンテンツを披露し、注目を集めている。
「アライアンス・トーナメント」というゲーム内の大会商品でNFTコンテンツを配った。 最近勉強始めたばかりの初心者だけど動的計画法でつまづいている
部分構造最適性っていうけど、損して得取れというか一部では損でも全体で見れば最良になるような問題やケースは無いのか？って思う 枝刈り全探索だと思うとよさそう ナップサック問題でいうと大きさは同じなのに価値が低い組みたいにどう頑張っても得にならないケースは使わないように大きさごとに価値が最大のものだけ持っておく感じ？ 動的計画法がいまいち理解できない人には、メモ化再帰バージョンを試してみてほしい
と、個人的には思うんだけど、再帰呼び出しそのものが難しいかしら？ 馬鹿みたいだけどちょっと大きめの表を手で埋めてみるといいんじゃ 近頃再帰少しずつ書けるようになってきてメモ化再帰も試してはいる
ただたとえばフィボナッチなんかはわかりやすい。同じ計算してるからメモしておくっていうのは
でも経路とかの問題でmemoは違う値にならえないのか？ってなる。値が更新されてたらそれを返すっていうけどさらに更新される可能性はないのか？って >>381
違う値になりえる場合は使えないよもちろん
正当性が証明できるときだけ使うし、正当性が担保できるようにアルゴリズムを組むんだよ
これ以上は具体的な問題見ないとなんとも >>386
新スレはここです
向こうに新スレは立ちません 別にわっちょい怖くなんかないけど、人がおらんとどうしようもない。向こうのスレコンテスト後の数時間はクソスレ極まってるけど、日常のバカ話で人を引き止めてるところはあるのかもしれない >>390
>コンテスト後の数時間はクソスレ
すまん「コンテスト後の数時間以外はクソスレ」の間違い どうして制限時間内に解けないのに、制限時間が終わった途端解法が思いつくのか……俺こういうことよくあるんだけどなんでだろうね >>395
何物にも縛られない「自由な動き」が創造性を高めると判明！
https://nazology.net/archives/103764
多分これが一番近い理由だと思う
創造性とは少し異なるけど競プロも発散的思考の要素はある
拘束とも少しずれるけどそれに似た緊張が不調なタスクには絡んでると見てる
>>396
結果だけみて判断するのは他人をフィルターにかけるときは傾向が収束するから合理的だが、個々の事案に向き合うときには不十分だと思うで 風呂に入ってたら思い付いたアルキメデスの原理の逸話もあるし、精神状態に応じて辿り着ける思考は違うんだろうね
特にコンテスト終了前後じゃ劇的に違うだろう
考察得意な人は意図的にその辺のモードをコントロールするのが得意だったりしたりするのかも？ ロシア情勢がキナ臭いけど、CodeForces大丈夫だろうか ややズレるがchokudaiもコンテスト中は自分は天才だと思い込まないと解ける問題も解けなくなると言ってるな
強い人はメタ認知が上手いと言っていいと思う 昨日のABC-Ex, 答えの値が求まるのはいいんだけど復元ってどうやるの？ 解説読んでも理解できないとなかなかつらいものがある それは本当に実力が足りてなくて悲しくなるやつじゃん フリーランスに立ちはだかる「常駐」の壁。慣例を打ち壊し、
“テレワーク”案件3割→8割へと成長を遂げた「クラウドテック」の軌跡
リモートワーク求人専門サイト「プロリモート」がリニューアルオープン、業務委託契約の求職者と企業をマッチング
1/3以上が採用につながる高マッチング率、リモートワーク×エンジニア・デザイナー専門の
人材紹介サービス「ReworkerAgent」正式リリース場所からも時間からも自由な働き方を実現！
『ReWorks（リワークス）』リモートワーク特化型転職サイトとして 3月5日 リニューアル
副業・兼業マッチングサービス「クラウドリンクス」登録者数2万人突破
中小企業で進む副業人材の採用、96％が継続採用を希望
茨城県日立市、県外からの「テレワーク移住者」に最大151万円の助成金
長野市、市内に移転・事業所設置し、移住することで最大550万円の支援金を支給
フリーランスが活用できる「最大1,000〜3,000万円・補助率50%〜75%」の
『ものづくり・商業・サービス補助金』とは？概要や条件を解説 競プロ関係のツイートに対して言及するならまだしも写真に対して色々言うのは終わってる EFGHも50点ずつでもいいから点差欲しいな
ABCDF>ABCDEだろうし 低レベル帯は上位アルゴいらないって誰かが言ってたけど今回のEとかみたいに考察省略できるのはアドだよなぁ ワッチョイ有りだとガイジスレとイクが居なくなるのでは？ Bがこの重さってまじ？
もう新規囲い込む気ないよねこのサイト >>420
>>421
ワッチョイ一致してるけどスマホをwi-fiに接続しただけで自演の意図はないです
紛らわしくてごめん 普通にナイーブだったし何も気にしてなかったけど、diff見るとたしかにB高いな
Fもなんかむずかったし、また文句出そうだな プログラミング入門者で、競技プログラミングやってみよーって人が今回のABCのBをみたらどう思うだろうね
これじゃあ人なんて増えないわ bよく読めばそんなに難しくないんだけどな
出題者がdiff低く見積もったのもわかる気がする ABC255のBのdiffを余裕で越してきたな
歴代最難関Bか ABCで今回のよりもdiffが高いBが出たのは少なくとも5年前 灰や茶にとってはちょっと難しい要素が複数詰め込まれてた感じか？
問題文がちょっとむずい
8方向遷移がちょっとむずい
順番に並べて整数を作るのがちょっとむずい
みたいな 二次元配列の8方向見ていくやつはスニペットとして持っとくべきだよね 水色の自分にとってはEが面白くて、頑張って解いたらレート上がって楽しい回だった Bはchokudai作問だったか
確かにC問題の難易度だよなあこれは B問題はdiff200くらいにしてあげるのが新規ユーザーも心折れずに、それでいてチャレンジできるから良いと思うの 競技プログラミングって実際にはプログラミングというより
基礎学力、算数の力を問うようなものだろ
実際超有名進学校の生徒が多いし >>437
そもそも競技プログラミング(計算機科学)は数学の一分野 >>436
diff200くらいだろうと思ってb問題にした結果です 昨日のBは実際難しかったね
あまり競プロ界隈は読解力で差がつくということを認めない傾向があると思う(実際は高校生大学生レベルでもそこで差がつく層はかなり多い) >>439
chokudaiさんだっけ？B問題作ったの
確かにただのループだけで解けるならdiff200くらいで済んだかもしれんが
マスの外に飛び出しても良いってのが難易度上げちゃったんだろうな Bはcodeforces div3, 4あたりで頻出だし個人的に簡単だったけどAtCoderだけやってる人は実装めんどかったと思う chokudaiがそんなこと言ってた気がする
基本的に考察できたらすっきり解けるパズルが多いみたいな O(1)の数学問題はめっちゃ解かれるよね
文系の俺、順位表のAC数見ていつも涙目 AHC012、ずっと任意の向きの直線考慮しててラスト一時間でようやく縦横だけのほうがスコア出るってたまたま試して気付いたんだけど、
初期から縦横だけでやった人はどうやって縦横だけで十分って気付いたの エンジニア力を養成するためにコンテスト途中で仕様変更があるatcoder 実装弱者だから、斜めの線引いたときのスコアの計算方法が分からなかったんだよ 任意の向きで考え始めると時間かかるからとりあえず縦横に制限すれば楽だな→意外と点取れるな
って感じだったが
苺はランダムだから、まずは直線の向きどうこうよりは囲んだ面積のほうが個数に寄与しがちだと思った まともにスコア計算を高速化できない方針に短時間コンで手を出すべきじゃないんだよな
となると縦横が第一候補になるのは自明じゃないか？WaveletMatrixとか使えるのだから 色々ありがとう
初手とりあえず広めに解を取ってしまいがちなんだがもうちょっと色々考えてみる アルゴは解けなかった問題を解けるようにする/解ける問題を速く解く、で強くなれるけど、
ヒューリスティックはどうやったら上位勢との差が縮まるのか分からん 焼きなましや山登りは試行回数が命だからアルゴが役に立つとか言ってたな ヒューリスティック頑張るとしたらやっぱりマラソンマッチの過去問やりまくるとかがよかったりするんだろうか 自身が解けない問題をしっかり理解するきっかけになるからあえてレートよりdiffが高い問題を解説したら実力伸びる気がしてきた
ただ解説の精度に著しい問題が発生しそう 他人の実力を下げることにも貢献して、レート上昇に効果的かもしれない 競プロ得意じゃない人が競プロ解説するの、実務能力のない層がプログラミング教材作って荒れてる駆け出しエンジニア界隈となんら変わりないのでは 一色上のdiffくらいなら許されないかな
大筋は公式解説に則れば間違いも少ないと思うし 黄色か橙くらいあれば diff 関係なく理解さえできれば解説書けそう
それ未満は自分が正しいこと書いてるかの判断もつかなさそう 書いた時点でのレートもつけとけば別に書くの自体はご自由にという感じだけど そもそもインターネットを汚さないでください
勝手に書くのはもちろん自由だけど公開せずに非公開のまま独りで満足してね 寒色の人に限ってはすべてこのようによろしくお願い致します🙇 これでqiitaに2色上の問題解説してるやついたらスレ民バレしそうだな
ちょっと温めとこ 炎上、身バレに対する一番の対処はやっぱり沈黙なんだな ムイタerの集合とマイタerの集合は背反なのでム板に書き込んでることがバレてもノーダメのはずです＞＜ 最近か？
酔ってる時はずっと発言ひどいイメージだけど >>489
コンテストに出て「実力を発揮できないパフォーマンスだった」と病むんだから全然めでたくねえよ 競プロやるな、まずはvimをやれといわれたけど本当ですか
手がホームポジションから離れるだけのロスですら命取りらしい >>493
ABC卒業したらそういうところも気にする必要あるのかもね 競技プログラミングで思考が入力に追いつかないなんて入力が遅すぎるか本当に天才的に冴えてるかどっちかじゃない？ そもそも競プロよりvimのほうが役に立つから合ってる お前が何をやりたいのか知らんけどやりたいことをやるのがいいよ ど偉い人が不遇な亡くなり方をしてしまいましたね
自粛してABCに参加します 許さんぞ チーのもの
チーのもののくせに大それた事を
気分が悪くなったわ 犯人見て思ったこと
現実では関わりたくもねー チーのもの ユーザー解説を書いて認められたいって承認欲求が病む原因だからやっぱTwitterを復活させるべきじゃなかった >>468
競技のコード観てると汚いのが多いし
そういうのが勝ってしまうのもどうかと思う そもそも与えられた課題に答えさえすればいい
しかもACしたら見返す必要はない 競プロにとってのコードは計算用紙みたいなものだから、汚してなんぼのもん 100行もない、自分以外に理解させる必要もないコードについて、速度優先して汚く書くのも無駄な工数をかけないという実務感覚の一種だと思うよ 実務じゃないような気がするがｗ
綺麗さ云々いうなら、コードの綺麗さを競うカテゴリー作れって働きかければ～ コーナーケースを潰すために書く分岐処理とかはしっかり検討すればこれもっと綺麗になるなとコンテスト後に提出したコードを見て気づくかな tourist のコード(マクロがほぼない)を実務erの視点で見たら変数名が短いこと以外にどんなところがダメなんや？
アルゴリズム部分はかなり洗練されてると思うけど ・情報系の枠を増やすのが急務。なぜなら進振りで行けないから(東大ローカル事情)
・枠を増やすのが急務だけど新しい大学はレベルが低いから不可
めちゃくちゃじゃね？ めちゃくちゃだね
誰がツイートしてるのかしらんけど灰かな >>514
変数名はむしろちゃんと付けてる寄りな気がするけどな
後は575やめて適当な長さで関数に切り出してコメント付けとけばレビュー通る気がする vimとsublimeだったどっちが有利ですか？
言語の勉強の前に先にエディタをマスターしようとしています Sublimeはさすがにもう選ぶ理由が少ないよ
VSCodeより軽いけど、vimにもVSCodeにも機能面で劣る
というわけで勝手にvimとVSCodeの比較のつもりで話すけど
マスターするっていえるぐらい気合があるならとりあえずvim使ったら？
そもそもどっちも使えるようになっておくといいけど、気合があるうちにvimに慣れておくといいよ
VSCodeはマスターっていうほど気合を入れることなく、お手軽に使えるようになるだろうし 前からエディタの話ばっかりしてるアホが一人おるな
しかも聞いてばっかで実行しようとしない エディタ選びで数日かけてるなら競プロも業プロも向いてない このスレ以外とｶﾞｯｸｼワッチョイの書き込み無いんだな
お前らネットリテラシーあるやん apiadのwinning runかと思ったらtouristまさかのまくりw またネトストスレになったね
正当性のある言い分ならリプで言えばいいのに またネトストスレ監視スレになったね
正当性のある言い分なら本スレで言えばいいのに ネトストスレ監視スレになったこと一回もないだろ
うまいこと言えてないよ てかマジで誰かリプで言ってやれよ
なんで引用RTしか無いんだよ まともな感性のフォロワーならとっくにミュートしてるはずだし、誰もリプしないのはそういうこと もう彼のフォロワーお気持ち表明楽しみにしてる奴しかいないでしょ ARCやこどふぉの話題がねえ
自分はtwitterで書き散らして終わるのでこっちに書き込まなくなってしもたが AGC1回分の作問で40万円か
率直に言うと割に合わないし夢がないと思ってしまった… いや、十分じゃね？
Agcは全く収益産まないんだから年間240万円ドブに捨ててるようなもんだろう ABC8問作って5000円だったとしたらキツすぎる 慣れた人がやると時給2000円くらいにはなるんじゃないの？ 点数*10円くらいちゃうのかな
efで差つけろって話題のときそんな話が出たような GとEx逆転は珍しい
Gで崖ができると今度は青ぐらいの人が被害食らうな G解説を読んだ
状態の持ち方さえ決めてしまえば飛躍はないけど、この状態の持ち方を思い付いて実装してみようって気がなかなか起きなさそうだし、やっぱり難問だな
なまじGっていつももっと簡単に解ける印象だし Eをセグ木でやる方法、各作用が要素数4のモノイドの直積になっているからできないことはないけど、そこまで考察が進んだ累積和の要領でやるのが自然かな よく考えたら直積モノイドなのか
あまり考えずにビットごとに処理したわ chokudaiがアルゴリズム力不足を感じるようなタスクに取り組んでいるみたいだけど、なにをしているんだろう 代表だし単にやることをたくさん抱えてるだけじゃないのかなあ ・フリーランスに立ちはだかる「常駐」の壁。慣例を打ち壊し、
“テレワーク”案件3割→8割へと成長を遂げた「クラウドテック」の軌跡
・リモートワーク求人専門サイト「プロリモート」がリニューアルオープン、
業務委託契約の求職者と企業をマッチング
・1/3以上が採用につながる高マッチング率、リモートワーク×エンジニア・デザイナー専門の
人材紹介サービス「ReworkerAgent」正式リリース場所からも時間からも自由な働き方を実現！
・『ReWorks（リワークス）』リモートワーク特化型転職サイトとして 3月5日 リニューアル
・副業・兼業マッチングサービス「クラウドリンクス」登録者数2万人突破
中小企業で進む副業人材の採用、96％が継続採用を希望
・フリーランスが活用できる「最大1,000〜3,000万円・補助率50%〜75%」の
『ものづくり・商業・サービス補助金』とは？概要や条件を解説
・茨城県日立市、県外からの「テレワーク移住者」に最大151万円の助成金
・長野市、市内に移転・事業所設置し、移住することで最大550万円の支援金を支給 フリーランス向けエージェント「クラウドテック」会員数8万人突破
〜働きやすい環境構築のため、単価向上・全年齢の活躍の場創出・
地方企業のDX推進の取り組みを強化します〜
フリーランスエンジニア専門の案件一括検索サイト「フリーランススタート」、
累計掲載案件数25万件突破！リモートワークの累計掲載案件数35,000件突破！
新規人材の80%がフルリモート希望！ IT人材市況動向レポート2021年12月版を公開
人口移動報告 家賃高い、首都圏脱出 「コロナ禍、仕事フルリモート」
クラウドテック、地方企業向け『クラウドテックDX』を開始、
7万人を超えるDX人材が、地方の非IT企業のDX推進を支援
新潟県、移住してきたテレワーカー／フリーランスに最大50万円を支給
テレワークの一般化により、11月にはテレワーク可能案件83.7%へと増加。
2021年、フリーランスのトレンドは「移住＆テレワーク」と予測 D解説読んだら化かされた感があるな
なんか前見た覚えあるのになんで思いつかなかったんだ E全然分からなかった
解説見たらへえって感じだけど、なんで急に赤色の頂点の次数の総和を考え出すの？
解けた人の考え方聞きたい 模範解答的な思考過程は知らんけど、
ある頂点1つに着目してそこを塗ったときに、色が異なる辺が増えるかどうかを考えたら気づいたぞ
周囲の頂点が赤色だとしても青色だとしても同じやんってな 隣接した頂点を塗ってみたら偶奇が打ち消し合っているように見えて、絶対これ使うやろと思って睨んだら出た お絵描きして考えてはいたんだけど、何も見えてこんかった... 違う色の頂点間を結ぶ辺の数そのままだと上手く解けなかったので、
他の扱いやすい数との関係を考えてたら次数合計と偶奇が同じことに気付いた Eは爆速で解いてる人たちがいたからどうせ簡単な解法なんだろうと思って次数の遇奇だけでできないか考えたら行けた >>565
ああ、解けてたからあまり気にしてなかったけど、解説のやつそういう意味だったか
やっと理解した
たしかに解説の流れだとなんでそれに気づくんねん、って感じするが、
まあ求める辺の数と次数にさえ着目できれば気付けるね ＼ 丶 i. | / ./ ／
＼ ヽ i. .| / / ／
＼ ヽ ／
わ た し で す
＼ _,, ---一 ー- ,,,_
、 ＿,,,, ＿,, -.'" ` 、 -‐
ー ミ三ﾐ三ミ三ﾐミ ヽ_,
-=＝三ミ彡三ミﾐ ,,=-＝= ==、 iﾐ=-、＿
＿,,ンミミ三ﾐ三ミﾐ] -彡-一 ー-、 r一 ーミ、|ミﾐ三ﾐ=-' --
_＿ _, -=＝彡ミ彡ミﾐミ| ン| ,=て)> (|ー| ,て)>、 ||三ミ彡＝=-'
＿ ,彡彡三ミ三ミﾐレ'~ .|. ' | ヽ ` |ミ三彡三=- ＝ 二
（＿彡三ミ彡ミミﾐ' ヽ、 ノ ＼＿＿ﾉiミ彡ミ三=ー
ー-=二三ンーﾐミﾐ `ー /(＿r-、r-_） .|彡ミ三＝-、
）（＿ミ彡ﾐ| i' ヽヽミ | : : : __ : :__: :i .|彡ミ三=-、 --
と彡ミ彡ミヽヽ<ヽﾐﾐ |: ﾝ＝-ニ-ヽ、 .|彡ミ三＝=-
彡ミ彡ミミヽ ) ` 、 .' <=ｪｪｪｪｪﾝ | |彡ン=-＝ --
-‐ -=＝彡三ﾐ `ーヽ : : : : : :i: : `ー--一'' : : ﾉミ三＝=''
'' てノこミ彡三ﾐ`i : : : : : :ヽ: : : . .:, :/ミ三=-、
'' 三ミ＝三三ﾐ|ヾ、: : : : :ヽ: : : : : : : : :_ノ:./三=-'
-=＝''￣ . :￣￣￣ 彡 `
／
/ ヽ ＼
／ 丶 ＼
／ / / | i, 丶 ＼
／ / / | i, 丶 ＼ モノホンなら真面目に相手しちゃいかん
またなんか言うてるわ程度で流しとけ >>570
このAAにあえて寄せに来てるだろってぐらい似てて草 アピールできるのギリギリ黄までってすごく真っ当では
水なんて4級やろ？
囲碁や将棋に学生時代打ち込んで4級になりました！
ってアピールされたらどう思うんよ 逆に赤橙だと競プロしかやってこなかった奴だと思われん?大丈夫? 本当にそれだけしかない人なら暖色上位あった方がいいのかもしれないけど、one of themとして使うんなら別に緑とか水でも十分だと思うけどね
大手企業でも別にそんな新卒はハイスペだらけじゃないよ Eは昔六問ABCでFの位置に置かれてた問題に似てるな
やっぱりちょっとずつ問題のレベル上げてる？ Eをmodとった値になんの意味があるのかｗｗｗ
近似値で良いじゃん 業務でも浮動小数の誤差が嫌なときは確率や期待値に素数のmod取ったりするよ シミュレーションとかでものすごく小さな誤差も気になるときには実際有理数体と有限体のどっちが取り回しがよいんだろうね
そういうのやったことない トヨタでのバイト、AtCoderとして受託して業務提携でプレスリリースを出すみたいなことはできなかったんかね
いい実績作りな気がするけど 社長がいなくても回るんならもう副社長が社長でいいやん AtCoderが受託開発を始めるのはちょっと違うでしょ 今回は前半の方がいつもより難しめで後半の方は簡単め？ 自称ユーザー解説については、コンテスト中に書いて終了後即座に提出したか、testerが書いた（writerじゃないから非公式という認識？）みたいな感じじゃないか 切断クエリを逆順に見てUnionFindによる結合に読み替えるやつ本当にABC-Eって感じのテクニックだな 今さらだけどchokudaiが忙しい理由ってトヨタのアルバイターだったからか 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/ 1完ちょっと早め解きでおそらく微減...
でもまだARCどころかABCですらギリレート上がる範囲だから悲壮感はない🤗
よくやったほうだ😎 もう政治の話する人と金玉ネタ擦ってるキッショい誘導しかおらんのか ABが解けて2800-2000だから
黄青にはいい難易度だった 180分のコンテストでB早解き競争ってしょっぱくない？ アドホックで難しくて分かれば綺麗に解けるような問題が都合よく無尽蔵に作れる保証はない以上、AGCもそのうち考えたことがあるor見たことがある勝負に帰着するのかもな 遂に異常精進erが黄色止まりじゃなくなる時代なのねん 情けない話だが AGC より ARC, こどふぉ、インドのが楽しい 3-5-6-8-8-12か
なんとか四完したいなー ・ ｢1万時間の法則｣の元ネタ（被引用数: 9847）、再現されず。むしろ、一番上手なグループは累積練習時間が少ない傾向
競プロer的にはやっぱこれが大きいな 政治erもみんなこっちにこないとダメそうだな・・・ こっちならワッチョイでNGすれば1週間は見えないからありがたい😎 二次元セグ木、存在は知ってるけど実装したことないやつだ 競プロから離れろ
俺なんてアンレで下がっても得したわくらいにしか思わん 間違えてワッチョイスレにくんの書き込みしちゃった😭 アンレでやらかしたらむしろ得したって気持ちにならねえか？ ２冠、難易度上がりすぎて長年維持してた緑脱落しそうｗ Eってにぶたんが想定なのか・・・
ヒープ使って貪欲にやるほうが自然じゃない？ どうせこんなん二分探索でしょ(ﾍﾗﾍﾗ)って感じで半端な考察でコーディングしてたら、別に小さい順にとって全然問題ないことに気づいて結局ヒープ貪欲になったな まあたしかに、最大値の最小化だからにぶたんぽい、って思えるか
おれは実験してたら貪欲でいけるってすぐ気づいてしまった (コスト,インデックス)の配列のヒープでやってたけど中に手を入れられない事に気づいて２分探索にして時間切れ・・・ 更新があったらpushすればいいだけ
更新前の残りカスがpopしてきたら枝刈り
要はダイクストラと一緒 C++ でいう std::set を持ってくれば中に手を入れられるので……？ G蓋を開けるとそんなに捻りがあるわけでもない挿入DPだな
なんで思い付けなかったんだろう 最近昔よりARCが解けない気がするし、いよいよ俺も過学習erかぁ〜？って状態
頭が悪いのはどうしようもないからあきらめてるけど、CF div1過学習とかでARCはなんとかできる？ 深さ優先探索でのグラフの点への後行順のリバースオーダーがトポロジカルオーダーになるので，
それを利用しています． ところで，アルゴリズム専門の大学教授が参加したら強いと思いますか？ むしろ、東京アルゴリズム専門学校を設立すべきでは？ Erik Demaineとか強そうじゃないですか？ >>628
次数が0の頂点からdfsを始めないとqがトポロジカル順にならないかな
あと、PythonとかPyPyなら
import sys
sys.setrecursionlimit(10**5+10)
とかを書かないとREになるよ >>634
ありがとうございました．
その再帰のリミット設定を追加したらパスしました．
プログラム自体は変更しなくても大丈夫でした． 後退解析チックなトポロジカルソートしか知らないからそういうトポロジカルソートのやり方は知らなかった >>633
強い人はめちゃくちゃ強いだろうけど、全般的にそうかは微妙かな
年齢も大きい
アルゴリズムの有名な実力のあるおじいちゃん研究者がこどふぉ水だったりするし ARCはまだ訓練でどうにかなるレベルらしいから、気長に難問に取り組むのがいいんじゃないか
知らんけど >>637
確かに人によって全然違うでしょうね．
極端な場合，プログラミングをやったことがないという人さえいるみたいですし． みなさん，アルゴリズムの本はどんな本を読んでいますか？
クヌース
CLRS
セジウィック＆ウエイン
Kleinberg & Tardos
何かおすすめの本はありますか？ 超高速グラフ列挙アルゴリズム−〈フカシギの数え方〉が拓く，
組合せ問題への新アプローチ
ERATO 湊離散構造処理系プロジェクト・湊真一、2015
計算時間が何百億年も掛かるのが、数秒で解けた
「おねえさんの問題」で有名な、
湊真一の超高速グラフ列挙アルゴリズム ZDD
プログラミング・コンテスト・チャレンジブック、第2版、2012
3人の大学院生が、様々なコンテストの問題を集めたもの。g++ 用のC++
オライリーの「入門 データ構造とアルゴリズム」は、インド人の著者
他にはセジウィック、石畑清、川中真耶など >>641
ありがとうございます．CLRSですか．第4版が出ましたね．
>>642
『超高速グラフ列挙アルゴリズム』ってトンデモ本ではないんですか？
>>644
その本って，高級な話題を扱っていそうですが，競技プログラミングに結びつきますかね？ こんなところで聞いても灰しかいないぞ
赤か橙に直接聞け >>645
コルテ組合せ最適化の内容に関して言うと、LP、フロー、マトロイドはじめ、競プロサイトの中でも知識が要らない方と言われているAtCoderでもそれなりに見るような話も結構扱っているように見える
ただ、それらをコルテで勉強するのがいいのかはちょっと自分はよくわからない 在庫管理系の面接受けたけど、競プロと関係なさすぎて。簡単な最適化くらい出せば良いのに。 業務はアルゴリズムとか関係ないからな
プログラマの仕事は基本的にデータベースの出し入れだけ
でも業務知識や設計はなかなかバカにできない難易度だな いや、アルゴリズム、数理最適化使うんだけどatcoderパズルが的外れすぎて役に立たない。線形計画もラグランジュ法も出さないで何がアルゴリズム人材だと。 問題にもよるけど昔より難易度上がってるし一般的な業務だったら灰色上くらいで、アルゴリズムっぽいのでもせいぜい茶色くらいまでかと。数え上げとかmod,xorなんちゃらみたいなのがなければもっと上まで役に立つ可能性があるといっても良い気がする。精進は時間の無駄と考えて気楽に参加してる。
AHCのほうはかなり役に立つと思う。 普通にLP解いたりラグランジュ双対とったりする問題は頻出だと思うけど
同じ数理最適化でもニュートン法とかもっと機械学習っぽい連続最適化問題出せみたいな話は分かるが ただその辺はABC-GとかExとかARC-C以降とかに放り込まれているから、数論や組合せ論系の問題が元から得意じゃないとそこで阻まれてたどり着きにくいというのはそう え、脳死でソルバーに突っ込んで解けるのがG以降にあるの？
だとしても普通に最適化系の科目をで履修中の人が解ける3-400点程度に押さえてCDあたりで出すべきかと >>657
いや、さすがにそんな脳死解法が想定解の問題はいくらABCでも後半じゃ出ない
https://atcoder.jp/contests/abc216/tasks/abc216_g
例えばこれは数列をうまく変換して条件言い換えるとLPが出てきて、その双対LPが最短経路問題になってるからダイクストラ法で準線形に落とせるって問題
ソルバーに投げず別のアルゴで解けるようにしないと通らないし、また、LPに帰着させる部分が大体非自明なのがAtCoderで出るLPの特徴
一方、本当に一目でLPだとわかり、脳死でソルバーに投げればいいタイプのLPをABC-Cとかに出せって話もわからなくはない
個人的にはつまらない問題だと思うけど教育的ではある そもそもAtCoderのアルゴの方のコンテストだと確率的に正解になる解法はコンセプト上想定解にしにくいから、脳死LPが出てくるとしたらソルバーに投げるんじゃなくて普通に頂点全探索が間に合うような問題になるかな
二次元ですら実行可能領域求めるの結構大変だから、ABC-Cで出すとしたらかなりかなりわかりやすい凸多角形にする必要がありそう ABC-Cに虚無LP入れたら荒れそうだな
崎になにか教育コンテンツで啓蒙した方がよさそう 2021年以降のARCみたいな問題て他にどこで練習すれば https://atcoder.jp/contests/abc087/tasks/arc090_a
にある
左上および右下のマスにもアメが置かれており、あなたはこれらのマスに置かれているアメも回収します。
ってどういう意味？
単純に通ったマスの飴だけとったらACになったんだけど、問題の意味が分からんかった >>664
確かに一瞬、意味が取れなくて(i,j)を通ったら(i-1,j-1) or (i+1,j+1)の飴も回収できてますよ、的な話かと思ってしまった
(1,1)と(2,N)の飴も回収しますとか書いた方が紛れが少なそう >>663
これは俺も気になる
相性が悪いのかもしれないけど、かなり難しくなってないか？ 競技プログラミングの問題には人間の作者がいるので，それほど独創的な問題を量産できるとは思えません．
とすると，ある程度の訓練を積んだ人間にとっては，同工異曲な問題群に見えるのではないか？
と考えたのですが，あっていますか？ そらそうだよ
数オリだろうが過去問たくさん練習すれば解ける確率上がるからね 数学オリンピックの問題はおそらく数学者が作っていると思いますが，AtCoderの問題は学者が作っているわけではないですよね？
だとすると，問題の独創性はかなり低いのではないかと推測しますが，あっていますか？ さすがにAGCとかになると作問者もかなりハイレベルだし既出かどうかをチェックする体制などもあるのであまり関係ないと思いますが、作問者じゃないしわかりません
そんなに気になるなら高橋社長に聞いてみたらどうですか
TwitterでもYouTubeでも匿名で質問しても回答をくれますよ AtCoderの出題者は今のところ、一般の学生、たまに会社員って感じではありますね 別にそんなことはないよ
ABCは典型問題だらけだけど、AGCはかなり独創性の高い問題を出すことを志向している
そもそも数学者としての能力と競プロの独創的な問題を作る能力はそもそも微妙に違う、良くも悪くも
もちろんAGCすら世界10位以内とかのクラスから見たらパターン見えるのかもしれないけど、大体の人だと二十年頑張ってもパターン学習できないと思う 数オリ勢の成績見た感じIMOとAGCだと多分AGCの方が難しいと思うんだけど、実際のところどうなんだろう ABC224HなんかはLPの定式化は自明でソルバに突っ込んで解いた人もいるらしい >>677
これソルバ解けるのか、思ったよりLPソルバ優秀だな…
というか想定解の双対とってMCFもかなり見えやすい問題だ AGCも問題にバラツキあるから、ハッキリとは言いづらいけど、
全年齢対象なのになかなか全完が出ないAGCのほうがやっぱ難しといえるんじゃない？
ちなみに今年の数オリは中国からの参加者は全員が満点を取ったらしい
簡単だったのかな chokudaiも以前に何かの放送で、新しい問題つくるのがほんと大変だって言ってたな E8くんなにするんだろう
新書籍発売？
新コンテストサイト公開？ まあ大概学問もパターンゲーじゃないか
むしろアドホックな考察力が求められる分野の方が少数だと思うね >>687
なるほど、そういえば発売まだだったのか
確かにそれが一番可能性高そうだな E8くんって最近コンテスト出てない？
前のAGC見かけなかった気がするな E8くん、すごい執筆速度だ
このアウトプット力は素直にすごい
ただ、やっぱりABC-ratedが対象読者みたいで、暖色を押し上げる本は相当難しいんだなと 新しいE8本、俺はヒューリスティックできないからその部分は読もうかと思う でもこのPDF、ビームサーチの解説が「後で追記」のままになってるな・・・
chokudaiに通報したほうがいいね 競技プログラミングをやっている人で強い人でも、アカデミックな匂いのしない人
が結構いるように思います。 学者じゃないから、そりゃいると思うよ
数学や情報科学が得意な人も少しいるゲーマーコミュニティってだけで 暖色向け本の話だけど、今のAtCoderで黄色より上に上がるのに別にそんなに知識って寄与しないイメージ（というか知識だけならみんなもう持ってる層での競争）で、こういうデ/アの知識を入れた方がいいとか、知らないデ/アの知識を手に入れるにはどうしたらいいのかみたいな話はあんま”本質”って感じがしないんだよな 12年前に蟻本出したってよう考えたらすげえことだな 競技プログラミングは独創的な問題に価値を見出しているから、年々新しい問題がたくさん作られているんだけど、未だに12年前の本が中級者（ここでは水〜黄ぐらい？）向けの本としては定評があるから 蟻本って、プログラミング・コンテスト・チャレンジブック、第2版、2012 の事か
色々なコンテストから、3人の東大大学院生がまとめた本でしょ。
ほとんど全てのアルゴリズムを網羅している
言語は、g++ 用のC++
読んだ感じ、すごい学生達だと思った。
商売はアイデア。これはニーズがあるから売れると思った まあ蟻本の知識的な内容を全部理解しててもちゃんと考察力がないと橙にもなれないと思うけど >>702
独創的な問題といっても，アルゴリズムとデータ構造の本に書いてある知識で解ける問題ですよね？
みなさんはアルゴリズムとデータ構造の本を読んで勉強しますか？ ある一定レベル以上行くと要求知識と難易度ってそんな関係ないんだよね
小学生でも理解できる単純な貪欲アルゴリズムが解法の問題が永続赤黒木を要求する問題より難しいということがままある 解けないよ
小学校の計算ドリルじゃあるまいし
AGC解いてみればわかると思うけど、知識は大前提で、それ以上に閃きみたいなのが必要
つまりアルゴリズム知識問題というよりは、どちらというとやたら頭を使うパズルやなぞなぞといったほうがいい AtCoderに関して言えば、正直、ABCの問題（Exまで）や典型90を解いて蟻本を読むだけでもほぼ知識的には網羅できていて、学術的なアルゴリズムとデータ構造の本を読む必要性があるかというとそこまででもない
ただ、アルゴリズムとデータ構造を題材としたゲームをやっているので周辺知識に興味がある人も多くいて、趣味で勉強している人は結構いる雰囲気
学術的じゃない人もいるけど、学術的なことが好きな人も他より多めだと思うので、そういう人と話してみたら面白いのではないかな アルゴリズムとデータ構造の網羅性のある教科書の知識があれば知識面では十分問題が解ける水準にあると思う
ただそれには前提があって、発想力がないといくら知識があっても解けない（そしてここの要求水準が結構厳しめ）
って感じかね そうだよ
AGC解いてみろよ
AGCでも、AとかB問題ならアルゴリズム知識すら不要で、発想力のみ問われてるようなのが多いぞ >>705
AtCoderの社長のchokudaiとかは、アルゴリズムイントロダクションを昔読んでたね
競プロで強くなるために最適な道かは知らないけど、読んでる人はいっぱいいると思う 10^8回以上のループを書いてしまったら、実行時間制限に引っかかりそう
っていう程度の知識はいるけども というか、典型を嫌うのでアルゴリズム全然使わなくても水とか青になれちゃうじゃん 蟻本は著者の頭が良いから簡潔に書かれてて、それ故に俺の頭じゃ理解できん >>718
単に説明が下手なだけだと思います。
完成度も低いと思います。 蟻本の説明がへたくそだとは思わないし、行間も一般的な数学書より狭いと思うけど、実際海外の競プロ本ってどんなのがあるのか気になるな Springerの"Guide to Competitive Programming"は読んだことある。
けんちょん本と同等程度のレベルって感じだけど典型テクニックへの言及はこっちのほうが多いかな
アルゴリズムの説明だけで実装が書いてないところが結構ある 蟻本は簡単な説明だけ。
個別のアルゴリズムは検索して、理解するまで自分で図を描いて勉強しないと無理
だから、>>642
に書いたように、個別の著書で調べる
湊真一、セジウィック、石畑清、川中真耶、インド人とか
例えば赤黒木なら、どの本だったかな? みたいな >>724
ありがとう
聞いた感じ、英語圏の標準的な入門書って雰囲気だね
やっぱり気になるのは中国だからいくつか調べてみた
・算法竞赛入门到进阶
・算法竞赛入门经典
・算法竞赛宝典
調べた感じまず目についたのはこのあたり？算法竞赛で競技プログラミングらしい
いずれもペーパーブックしかないところが惜しい
俺は機械翻訳しないと中国語読めないので
入门は日本で出版されている平均的なものとあまり変わらなそうな予感がするけど、宝典とかいうのは気になるね と思ったら電子書籍もありそうだ
amazonだけで調べて電子書籍ないと思い込んだのは我ながらネットリテラシー低いな しかし中華サイトは技術サイトでもキモい広告の表示のされ方がするな 今日初参加するわよろしく
本番の回答ここに貼ってくれてもOK！ なんで久しぶりに参加したときだけDが異常にムズいの
EとかFとか挑戦すらできず… D解いた時点でひどい順位だったけどFGが軽実装で救われた Exの最後のパートの「区間集合が与えられて、その集合に属する任意の区間内に*が存在するように*を配置するとき、*の数を最小化せよ」って問題、定期的に出る典型だ
これもmincut maxflowの要領で双対とると蟻本でも有名な区間スケジューリング問題になって双対すごいってなった問題
なお今日はそこまで至れなかった模様 Dみたいなプログラミング的に普通っぽい問題の難易度が高いｗ >>738
dfsで全列挙みたいなのが地味に一番実装難易度高い気がする G、実はabc...とzyx...のときの順位を足して二で割るだけでいいって流れてきて、嘘だろ！？って思ったけど式を見てみたらそうだった
実はTrieもsuffixもprefixも要らんかったんや… >>730
競プロ強いのは中国語圏とロシア語圏だし、日本で出版されているよりすごい書籍があるとしたらその辺かなと思って あと、Exの解説ではSA使ってるけど、長い文に対する複数文字列の位置検出といえばAho Corasick法がまさに使える C、絶対位置を相対位置に変換して考えるのって初見でできたらかなり頭いいと思うんだけど茶diffなんだね
みんな頭いいな（もしくは典型で染みついている層が茶まで下りてきてるか） パソコンに向かって解法や実装で延々と悩んでたのに、
疲れてベッドに横たわるとすぐにアイデアが出てくるのが謎 上位者は本番中に問題を解ける思考モードへの入り方がうまいっぽい
chokudaiか誰だったか忘れたけど、本番じゃないとAGCの問題解くの難しいって言ってたな
かなりメンタルが影響するらしい 数オリで中国チームが全員満点って話あって、情オリ見てみたけどこっちでも上位4は中国チームのメンバーで独占してるんだなあ・・・
https://stats.ioinformatics.org/results/2022
と思ってもっとよく見てみたら6位まで全部中国人やんけ >>737
Exというのはどの問題のことでしょうか？ >>747
ABCの八問目で一番最後の問題
昔はHだった >>748
ありがとうございました。
『プログラミングコンテストチャレンジブック第2版』のp.325に、
「したがって、先ほどの長方形を左半分と右半分の一辺dの正方形に分けると、それぞれの正方形には、
点はたかだか3個しか含まれません。」
と書いてあるのですが、たかだか2個ではないですか？
3個になる例はありますか？ 3点となる例がわかりました。
でも4点の例がないことはどうやって証明するのでしょうか？
直感的には3点であろうと思いますが。 >>743
競プロ初心者だけどC、40分くらい考えた末解けて自分天才だろと思ったのに茶diffだったんだな
みんな頭いいな >>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)のいずれの場合においても矛盾が生じる。
（証明終） あ、(1)も(2)も不等式評価で角度が180°以下であることを使ってるけど、ちゃんと書いてないからキモい雰囲気の証明になってるな 凸包の最遠点対という特徴量、いかにも重要そうだけどあまり競プロで使った覚えがない
ABC234Exなんかは最近点対問題の解法と似た発想かもしれない、さすがにABC234Exの方が難しいけど 逆に最遠点対どうやってNlogNで求めるんだっけって思ったが、凸包求めてキャリパー法でくるくるか
幾何系はド典型でも全然頭に定着しない 昨日のABC、Dの実装でバグらせる予感しかしなかったからEから解いて何とかギリギリ解けたけど難易度E>Fだったんだな
F典型って聞いたけど青くらいまで行けば典型に見えるんだろうかたしかに取り組みやすそうな問題ではあったけど >>753
証明ありがとうございました．
うまい証明ですね． >>751
今，解こうとしていますが，難しいですね．
素朴な方法だとΘ(N^2)ですね．
回転前の喜ぶ人の人数から，回転後の喜ぶ人の人数が簡単に計算できないかと考えているのですが，うまくいきません． >>751
幅3のパルス波が押し寄せてくるイメージを思いつきました．
なんとなく解けるような気がします． >>751
半日かかりましたが，Θ(N)のアルゴリズムを作ってパスしました．
これじゃ，コンテストでいい成績は残せませんね． 最終的にはわからない問題を考え続けるのが一番の練習法らしいから、解説を見ないで解く体力が長い目で見て実力に寄与する気がするし、ABC-Cを半日考えて解くのは上等
ただ、ABCだと知識ゲーの要素があるから、最初のうちは解説見た方がサクサクレートが上がる場合もあるし、悩みどころだ 「Closest pair of points」を求めるアルゴリズムについてですが，『プログラミングコンテストチャレンジブック第2版』の
説明だと説明が全く不足しています．
この本を褒める人がいますが，信じられません．
確かに他に少し高度なこの類の本がないというのは事実だと思いますが．
CLRSの計算幾何学の章に非常に詳しく解説が書いてありますので，そちらを読もうと思います． 『プログラミングコンテストチャレンジブック第2版』ですが，完全な解説ではなく，スケッチ程度の説明集だと
思います．
ネット上の解説などもそのようなものがほとんどだと思います． 4点の証明よりめんどい行間ある？って思ったけどマージソートの部分か
x座標で点集合を分けたあと、各ステップでx座標的に隣接する点集合を合わせることを繰り返すわけだが、そこでマージソートの要領でy座標をソートすることで、時間計算量を増やさずにy座標のソートができる
ある程度のレベルの学術書で単体で行間埋められる本の方が珍しいし、別に行間だらけだから良書じゃないなんてことはないと思うがな >>769
確かに有益な本だとは思うのですが，もう少し解説が丁寧だといいなと思います．
完全に理解するために，ソースコードに頼ることが非常に多いので．
何かおすすめのAtCoderの問題はありますか？
難しすぎると解けないので，初心者でも解けるくらいで面白い問題が希望です． >>770
このサイトはAtCoder Problemsといって、各問題のdifficultyという数値を見ることができる
https://kenkoooo.com/atcoder#/table/
difficultyとはなにかと言うと、半分ぐらいの確率でその問題を解けるであろう人のレートを推定したもの
ここでdifficultyの二分探索でもすれば自ずと丁度いいぐらいのところに行きつくと思う
基本的には自分のレートと同じか一色上ぐらいがやってて楽しい
初心者でプログラミング自体はできるんなら、最初はABC-C、ARC-Aぐらいの問題が丁度いいレベルと思う
面白さについて言えばAtCoderの問題は大体パズル的には面白いはず、ただそこも好みだな
高度な知識をたくさん使いたいんならCodeForcesの方が面白いかもしれない >>771
詳しく丁寧にありがとうございました．
時間をかけて解いていきたいと思います． 蟻本が解説に関して親切設計な本ではないのは確か
今は蟻本よりもっと初学者向けの競プロ本がたくさんあるから、その中から選ぶのも手ではある
最近は鉄則本なんていうのも出て、それも蟻本に比べたら多分初学者向け
https://kato-hiro.github.io/AtCoderClans/books/
ただ厳密数学的な意味で丁寧な本ってあるんか？自分は蟻本以外読んだことないからよくわからん こどふぉで自分のレートのdifficultyの問題をずーっとやってるんだけど、
簡単に解けるのと全然歯が立たないのがある… github.com/drken1215/book_algorithm_solution/blob/master/solutions/chap04.md
この4.6のコードですが、本当にO(N*W)ですか？
ボトムアップ型の動的計画法がO(N*W)というのは分かりますが、4.6は違うような気がします。 >>777
これは、部分和問題のコードのメモ化再帰のコードです。 issue 立ってるけど放置されてるな、やる気はその程度か 文字列の編集距離について質問です。
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)
です。 「S[i-1]==T[j-1]のとき」と書いてありますが、これは
「S[i]==T[j]のとき」が正しいというわけではないですか？ >>782
は『問題解決力を鍛える!アルゴリズムとデータ構造』という本に書いてある解説です。 >>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番目の文字を変更したとしてもトータルの編集の手間が少なくなることはないというのは証明が必要ではないでしょうか？ >>782
の他のところについても同様の疑問があります。 適当なこと言うけど
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番目までの操作と考えることができるっていうことだと思う 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文字目のどちらかを使わなきゃいけないことに注目する >>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に
編集する最小の手間である。 間違えました。以下のように訂正します。
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に
編集する最小の手間である。 また、間違えました。以下のように訂正します。
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に
編集する最小の手間である。 SをTに最小の手間で変換するオペレーションが以下の画像の通りだとする。
オペレーションを実行する順序には関係なく、SはTに変換されることに注意する。
imgur.com/GSQfWoU.jpg
(1)Sの最後の文字の右にInsertオペレーションがある場合。
Sの最後の文字の後ろに、Tの最後の文字を付け加える。
Sからその最後の文字を除いた文字列を、Tからその最後の文字を除いた文字列に最小の手間で編集する。
これが(1)の場合に、SをTに変換する最小の編集方法になる。 (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に変換する最小の編集方法になる。 多分、dp[i]を、i番目まで揃えたときの最小手順数だって定義してると思う
その次のインデックスの文字を揃えるために出来ることがその3パターンしかなければ、そうなんじゃないかなぁ
dpを更新したときに、定義が崩れてしまわないか？を集中して考えてみると良いと思う 最近競技プロ出来てねー
まぁ2年くらいやったし飽きたのかも パイザってサイトに『エンジニア騎士とクエリの魔女』の『暗黒の地』って
競技プログラミング風味のものがあるんだよ。まあまあ面白くて
これで12位になったので、ソース公開するね。
https://paiza.io/projects/Me-9l8aRopclovpRhczITg
ソースを読んだ感想を書いてくれたりしてくれると嬉しいです。みんなもやってみよう 平方分割すればできるのはわかるけど、想定解はそうじゃないっぽいし Lだけの話に限定するけど、
Lの効果をインデックス毎に保管しておいて、（入力例１なら[-1, -2, 2, 0, 1]）
それのセグメント木を作れば区間最小値をlogNで取り出せるようになるからいけるんちゃうか？ >>804
問題は、Rも同じようにインデックス毎に効果を保管するとして、区間内で和が最大になるLの効果とRの効果のペア（Lの効果のインデックスよりRの効果のインデックスの方が右になければならない）をO(1)とかO(logN)で取り出さなきゃいけないことだと思うけど、そこが難しくないか？
>>805
耳DPというと、左の区間外、Lの区間、元の値をそのまま使う区間、Rの区間、右の区間外みたいな感じの状態の持ち方？ >>806
たし蟹
ぱっと考えただけだとペア探しにO(N)かかってまう
ちょっと分からんわ まずaについて、各項の隙間ごとにLはその左でRはその右にあるような置き換え方での和の最小値を求めておいて、区間が限られたらその区間にある隙間に対して区間minして端の分を補正したらいいんじゃないの >>808
なるほど、と思ったけど、
N=4
A=[0,1010,1010,0]
L=1000
R=1000
Q=1
l,r=1,3
みたいなときに厳しそう 普通にx毎に最小になるyを取れるようにする方針だけど
それだと幅*Qぐらいだから多分無理なので改良として
セグツリーかなんかで[x,..)の領域に対して一発でy取れるようにすりゃいんじゃねって思った
ちなワイ茶色 超思いつきだけどさ、
L<Rの場合、Lのテリトリーを譲ってまでRの幅を広げる必要はない気がするんだよな
だからLについては貪欲に最小拾っていいとかないかな？ 耳DPのトロピカル行列をセグ木に乗っけて終わりとちゃうんか 全区間についての答えの和とかは解けんのかな
オーバーフローはないもんとして 耳DPの遷移を表すトロピカル行列が
L ∞ ∞
A_i A_i ∞
R R R
になってて、積についてモノイドになってるからセグ木に乗る
区間積求めてあとは(0,∞,∞)^tに作用させればおｋってこと？ >>813
なんかこれはこれで正当化できそうな雰囲気がある 結局正解っぽいやつについて自力で全然思いつかなかったの悲しい >>800
paizaってOpenCV使ったりするような問題出るんだ 行列積の定数倍が重いせいで平方分割落とす制約にできないのか >>819
あ、opencasは私個人的な
ローカル環境での
動作確認、デバッグ用です
そういうのつけとけば
参加してくれる人いるかな
的な意図もあります ふつうにLとの差分の累積和とって右から全探索でいいんじゃないのか？ N,Q≦10^5の制約だけど、それは2secで通る？ 具体的なやり方が読み解けないけどクエリごとに全探索したらO(NQ)なのでは？ もしかして、元々の問題ABC263Dの解法の話してる？ 昔のadminがりんごさんだったころのSRMってAGCとかに役に立つ？ >>828
ごめん話題変わってた？
左からLとの差分の累積和とって、左からi番目までで1番値が大きいやつのインデックスメモっておくのがO(N)
右から見てってiより右側はRにして、iより左側でLにするべき境目はさっき求めたからiの全探索でO(N)でいける認識
説明やばいけど勘弁して ABC263Dの解法としてはそれでOK
リンクされたツイートではさらに、元々の数列のうち区間[l,r)の部分に限った数列について元々の問題を解く×Qって設定になっていた
その解き方だとO(NQ)でTLEするので、これがちょっと難しかった(もう解法は発表されたけど) 正直、4つ持つことになんの意味があってどう嬉しいのか全く分からんぞい
耳dpってやつなの？ 4つ情報を持ってないと、モノイドにする（≒結合則を成り立たせる）上で情報が足りないからセグ木に乗らない
このモノイドが代数的な言葉で言えばトロピカル行列に対応している
ちなみにこのトロピカル行列は耳DPの遷移だから、そっちから考えても同等の解答に行き着く的な感じ
明日気が向いたらこの辺ちゃんと書く
何か言葉は仰々しいけど別にトロピカル代数の知識なくても、上書き区間左側確定 T/F 上書き区間右側確定 T/Fで値持って区間をくっつけること考えたらどういう演算をしたらいいかは発想できると思う 自分の理解だとさらに区間の長さも必要そうだから厳密には必要なのは5つの情報かな？ 半環上の正方行列が積が結合則満たすのって実正方行列での証明考えれば自明だけど、それが行列積だと分かってない状況だとかなり直観的に分かりづらいよな
そもそも行列積自体、初見で線形写像の幾何学的な話もなしだと結合則が成り立つと見抜くのが無理そうな意味不明な演算に見えるし 大槻の本に、比較によってソートするアルゴリズムの最悪計算量は、 Ω(n * log(n)) であると書いてあります。
最善の計算量が O(n * log(n)) よりも良いようなものって存在しますか？ >>837-838,841
ありがとうございました。確かにバブルソートはそうですね。でもマージソートとか最善の計算量と最悪の計算量が同じ計算量のものが多いですね。 Aこの難易度でも良いけど、ビギナーコンテストなんだから9割くらいが解けるDくらいまでにすべき、１０問は多すぎ
Dも昔は愚直にやって通るくらいの難易度だった気が D問題が greedy じゃダメな理由がわからん……
解説に反例があるのは見たけど納得できない 確かに直感的にはDはgreedyでもよさそうだけど、ナップサック法よろしく、整数が絡むと途端に直感greedyが壊れる
ABC-DからABC-Fぐらいの問題だとコンテスト中はgreedyがダメな理由を考えるより簡単に正当性を示せるDPを思いつくことを意識した方がいい 反例に関して言えば2個取るという選択肢がないのが効いてる ExのFPS解面白い
確かにDP遷移で途中\sum_n {n a_n}みたいな形の式が出てきてめんどくさそうと思ったけど、こういうのはFPSならただの微分か Dが水という事は、ビギナーコンテストだからC問題までの３問で良いじゃん 8問ABCは言うなればCodeForces Div. 2 + Div. 3 + Div. 4みたいな状態だから、Div. 3単独開催やDiv. 4単独開催が欲しいって話は分からなくもない
4問時代のABCがまさにそんな感じだったけど
コドフォが最近Div. 4増やしてるし、AtCoderも現ABCの下の区分のコンテスト作っていいと思うけどね 自分の感覚だと
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がカバーしている状態ではあるのは確かだと思っている 昨日のEってどういう思考過程をすれば二分探索が思いつけるんだ
言われたらそれはそうってなるけど >>845
肉を切らせて骨を断つ
無傷でいようとすると勝てないってわけよ 昨日のEは別に二分探索なんか使わなくても素直なやり方で解ける気がするが、判定問題が簡単で単調性がありそうならとりあえず二分探索試して損はない Twitterみた感じEのO(NlogN)解は重実装扱いなのか
個人的には二分探索解と大して変わらんやろと思ったが 愚直にシミュレーションしようとしたらバグらせまくったから二分探索の発想が早い段階で思い浮かぶように出来たら便利だなって 端数は後でなんとかすることにしてだいたい何周すればいいか知りたくなって、周回数を決め打ちすれば何個減るかはO(N)でわかるから二分探索すれば良さそうとなる ユーザー解説にO(NlogN)の実装があるから見たけど、そんな重実装かこれ？
二分探索より楽に見えるんだが 本来二分探索の実装ってかなりバグらせやすい方だと思うんだが、めぐる式で教育が行き届いている？のか、最近はみんな脳死で書ける印象
O(NlogN)解は量や内容は大したことないがアドホックなのが効いてんのかな にぶたんの最後のシメを考えるのが苦手すぎる…
LRがどうなったら終わりで、どっちに答えが入ってるのか分からなくなるよ そこでめぐる式よ 継続条件はwhile(abs(ok-ng) > 1)で答えはokに入る その式だけだとokがleftかrightか分からん 別にleftでもrightでもどっちでもいいからバグらないと言える
位置関係より意味内容に忠実な表記 ok、ngとかいいつつちゃんと定義域を渡さないといけないところらへんで、慣れてないひとは混乱するんだろうと思う
ok、ngではなくて、明確に定義域を指定するようなインタフェースに整えてあげると初学者には優しいでしょう
おれはいつも混乱しないように詳細を積めてから実装してるからok、ngなんて使わずhi、loで書いてるけど ok(ng)の初期値は条件が真(偽)だとわかっているところ
もしくは定義域の一個外にするけど
そんなに混乱するか？ 自分は二分探索、毎回コピペしてる
値が小さい方から大きい方にかけて、条件式がTrue, True, ..., False, Falseになるのと
False, False, ..., True, Trueになる2パターン用意しといて毎回コピペしてる ん、めぐる式二分探索って、上の2パターンを一般化しますよっていう話か...
3年半も競プロしてんのに初めて知ったよ... 別にlo, hiやleft, rightの実装で全く困ってなければ知らなくてもいいと思う
位置と判定、境界を一緒に考えると頭がこんがらがる初心者にとって、めぐる式は判定関数とok,ngの初期値さえ与えておけば二分探索部分のコードは位置関係すら考えず貼るだけなので楽 LRをどっちもokにしちゃうと無限ループしちゃうんだよな
まったくもう あー、そういえば、めぐる式で一番重要なノウハウは、[left, right)の半開区間にすると処理が簡単、ってことだと思うわ
閉区間にすると考えることもコードも増えてキツイと思うんだけど、外人のコードだとかなり見かける
こないだのABC1位のひとでもこれでやってるんだよな
if check(mid)
l = mid + 1
else
r = mid - 1 中国って割と1-based・閉区間の派閥がいるイメージだわ 取り敢えず区間扱うときは全て半壊区間が安定してるなぁ そのあたりは情報処理能力やライブラリ化でごり押せるから、上級者でも筋の悪い実装方針でやってたりすることがあるイメージ
特に軽実装のAtCoderでは、まず算数パズルができるということが何よりも大事だから DAG上の最短路問題について普通のアルゴリズムとデータ構造の本には載っていません。
これはトポロジカルソート＋動的計画法によって、最短経路の求め方が自明だという考えからでしょうか？ さあ、ダイクストラでも大体十分だったりするから需要ないんじゃない？ ABC263のDやってるんだけど、
kyopro_friendsさんの解説に出てくる累積minってググっても出ないんだけど、
nok0さんの解説のf(k+1)=min(f(k)+A[k+1], L*(k+1))のこと？
累積和使って最小値求めると、全体でO(N^2)になっちゃいますよね >>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
この６パターンの内の最小値って意味だよ AtCoder Problemsが独自に算出したという「difficulty」ってどこで見れるんですか？ >>882
Show DifficultyをONにしても表示されません。 大槻のAtCoder入門を図書館から借りてきましたが、やさしすぎますね。 >>883
左の円の色とか円の中のゲージがdifficulty >>885
ありがとうございました。マウスのポインターを円の上に持っていったら表示されました。 大槻のアルゴリズムとデータ構造の本に、クラスカルのアルゴリズムの計算量が、
O(|E| * log(|V|)) であると書いてあります。
なぜ、 O(|E| * log(|E|)) と書かないのですか？ 文脈が分からないけど、単純グラフって仮定があるんなら|V|^2>|E|だからってことで深い意味はないと思う
強いて言えば|V|の方がlogのお得感が出るとか？ 大槻のAtCoder入門という本に、頂点の数 N、辺の数 Mのグラフの構造の入力の受け取る処理に
O(N + M) の計算量が必要だと書いてあります。
O(M) が正しいと思いますが、どうですか？ 入力長はO(M)だけどvectorの確保にO(N)かかりそう 本当にグラフの構造情報を受け取るだけであればO(M)でいいけど、後続の処理で結果的にはO(N+M)かかることがほとんど
ただ、たとえばN=10^100, M<=10^5みたいなパターンの問題も考えうるから、O(N+M)よりはO(M)の方が正確かな、特に他に但し書きがないのであれば
かなり自明な話なので、そこのO(N+M)の記述で混乱して問題を解くのに支障が出る人はいない気がするけど すべて入力から受け取る必要があるならそら入力にO(N+M)かかるやん
入力の辺は重複しないみたいな条件がついてるなら、O(N^2)あるいはO(M)になったりする >>891-894
ありがとうございました。
明日の午後9時からの「AtCoder Beginner Contest 271」に参加予定なのですが、
何問くらい解けるのが平均的なんですか？
100分しか時間がないのでおそらく2,3問しか解けないと思っています。 大槻の『AtCoder入門』という本を図書館から借りてきて第5章の中級編の最後まで読み終わりました。
そこまでの問題であれば、時間がかかったものが多いですが、すべて独力で解けました。 東大出身のNTTなら敬称は殿だろね。
本もたくさん出してるし。 参加者の過去の成績や練習量はすべて公開されています
実力のある参加者は大量の問題を解いています
自分の成績が今ひとつでも気を落とさないことです 例えば、大槻の『AtCoder入門』という本の上級編の1問目の「abc115_d」の問題ですが、独力で解けました。
基本的なアイディアはすぐに浮かんだのですが、パスするのに1時間もかかってしまいました。
そして、練習を重ねてもこの時間を短くすることは難しいのではないかと思います。 あと一つ質問ですが、問題の解答(AC)を、計算時間の短い順にソートすると、上位の
解答の計算時間が異常に短いです。
ソースを見ても、アイディアは同じなのになぜあんなに速くできるのでしょうか？
計算時間のコンテストではないので、レーティング上は、あまり重要ではないと思いますが、
気になります。 解ける問題数については、三問解ければまずOKで、あわよくば四問解くことを目標にするぐらいじゃないかな
初回参加だとC問題解けない人の方が多そうな気がするし四問解ければなかなかだと思うよ
ABCは毎週開催されるようなものだし、一回一回の結果を気にしない方がいい、特に最初は
レートには直近10回程度の結果が反映されるから、今回失敗しても続けてればすぐにその影響を消せる
あと、参加回数が少ないとレートがめちゃくちゃ低く算出される仕組みなので、パフォーマンスを自分の成績指標として見よう 平均的な話をすると、どうなんだろう
AtCoderから競プロ始めた人だったら一から二完の間じゃないかな、そもそもプログラミング初心者も多いし
あと、上級者のコードが速いのは、再帰関数を非再帰にするとか、キャッシュ効率をよくするとか、入出力を高速化するとか、コンパイラのオプションを変えるとか、そういう細かい工夫の積み重ねだと思う
C++だったら別に意識しなくても問題ない気がするけど、Python使いだったら再帰を非再帰にするとか入出力高速化ぐらいはやっとくと、ABC-E問題以降楽そう つけくわえるとABC-Dまではかなり典型度の高い定型的な問題が多いので、練習すれば解答時間は縮められる方の問題だと思うよ レートでいうと100で上位50%みたいな感じだった気がするし、平均的なひとだったら最初は2完で上出来かね
強い人だと初参加でも3完か4完らへんをやってパフォ1000超えてるのが珍しくないけど こどふぉもやりたいけど23時半から2時間ってのが微妙だな～
眠くなっちゃうんだよなぁ schemeだけちゃうんけ？仕様で定められてるのは 再帰だとPyPyよりもCPythonのほうが早いらしいけど、なんでそうなるのか気になる ヒューリスティックコンテスト向けのおすすめ本ってあります？ A, B, Dしか解けませんでした。
Cはソートして、巻番号が小さい順に見ていって抜けている巻を、巻番号がもっとも大きな2巻を売って買う
ということを繰り返せば良さそうでしたが、実装が面倒だと思い飛ばしました。 >>903-906,909-911
ありがとうございました。 Cはにぶたんが楽だったな
愚直にシミュレートしたら3wa,2wa,1wa,1wa…って感じになったぴえん >>917
おれもシミュレートしたけどWAを潰しきれなくて、二分探索にしたら瞬殺できてなんか悲しかった 8月から競プロ始めて現在レート337の雑魚
Dは楽だったけどCでwa出してしもうた。。
明日のレギュラーも参加するか (N-最初に持っている本で読む本の数)/2 >= (これまでの不足している本)で判定すれば別に二分探索もいらないと思うけれど Exってこれ典型なのかな？
解説見てみたらどことなくARCの難問っぽいけど ABCのDまでは安定して解けるようになったけどEになった途端全然安定しなくなるのシンプルに過去問解き進めるしかないかな というかCの制限時間が4秒だったのってどういう想定？二分探索でもシミュレーションでも割と余裕ある気が 確かにCの制限時間よくわからないね
set使うと結構定数倍重くなるのかな？ パスの復元じゃなくDpの値にそのままパスぶっ込むのでもokにしたかったとか？ ABC-Eは典型90の内容抑えれば結構戦えるレベルな気がするなあ
あとEDPC埋めとかね 入力が 3 × 10^5 コ以上あるときは、解法に関係なく少なくとも3秒以上になってるような気がする 2*10^5でもいい気がするけど、それだと速い言語で二重に走査するだけのO(N^2)回とかが通ったりすることがあるのかな てか2*10^5でO(N^2)が2secで通るんなら、3*10^5のO(N^2)も4secあれば通りそう
あとは初心者が筋の悪い入力受け取りをしていたときにそこのオーバーヘッドで落ちるのを予防するとかかな なんか文句いってたら数え上げとXORの頻度が減った気がする。このあたりほんとアルゴリズムと関係ないので燃やすべし。 G問題がちょうど数え上げ+XORだったけど
組合せ論嫌うのもよくわからないね >>934
数年前はこの類が毎週出てて違和感しかなかった、統計学でも数理最適化でも観測範囲内で組合せ論は二項係数くらいしか役に立ってないハズ C、線形で解こうとしたんだけど、謎の1WAが出て困ってる
同じ1WAの人結構いたけど、みんな二分探索に切り替えてACしてる
https://ideone.com/yD7l3P
誰か教えて欲しい 「競プロは自分にとって離散数学パズルだ」ってりんごさんが言ってるし、整数論とかやるのと同じような立ち位置じゃないかなあ
そもそも初等組合せ論の考え方は初等確率論の基本なんだから、役に立たないというのも違うと思うしね
今回はGも数え上げ問題だったわけだけど、DP遷移部分について俺は幾何分布の考え方をイメージしたね >>937
そう、別に個人的にはそんなに嫌いじゃないんだけど、好む層の魂の元が中学入試あたりで、自然数の各桁の和とか数学的に大した意味もないトピックがやたらドヤドヤしていたのがちょっと不快。プログラミング、アルゴリズム、情報科学というより、IQ高めの算数エリートの娯楽という感じ。 >>938
貯めてるsellが足りないときに貪欲に大きい方の本を売ってるけど、そこで順当にいけば読めるはずだった本売ってるんじゃない
一冊残しておいた方がいい場合とそうじゃない場合がある >>940
魂の元が中学入試なのはまあそうって感じ
俺も算数パズルや離散数学よりも比較的連続最適化とかの方が好きっちゃ好きだから分からなくもない
まあでもCSでは離散数学は基礎教養だし、離散数学と中受算数は親和性高いよね >>941
ありがとう ACできた
シミュレーションしながらsellを貯めていくのはダメで、sellをシミュレーションの前に計算するようにしたら通った 重複する本は∞巻目ということにしてからシミュレーションしてもうまくいくよ 小数点の精度はどうすりゃいいのか未だに分からん
興味がないねんな… 米田の新しい本を買いました。
PASTの公式本とどちらを先に読むか迷っています。 大槻のAtCoder入門という本は買わなくて正解でした。
図書館で借りて読めば十分な内容です。 >>946
大槻さんの本で初級用の知識は入ったんだろうから問題集に移ることをオススメする。 >>950踏んだけど立てられなかったから誰か立ててくれ AHC、他の人の解法を参考に自分のを高速化しただけで60M超えてつらい
自分が高速化だと思ってコンテスト中やってたことが逆効果になってただけだったし 今ランキング見てるけど日本人多いんだね
まだまだこの国も未来がありそう（他人事） コンテスト中に呟いちゃいけないんだろうけど
1時間以上Aを考えてるがわからん 匿名の書き込みでも普通にやめた方がいい
そのぐらいなら大丈夫だと思うけど、それを見てまだラインがわからない人が勘違いしてさらに際どいことを書き込んでしまう危険性が わかった。少なくともコンテスト終了後に呟くようにする
今日のAわからなかった。。
どうやっても10^10**5がmで割り切れるかを10^5回するし
ゾロ目数に規則性はあるっちゃあるけど、ないから
全くわからんかった 桁数大きい整数がある整数の倍数になるみたいな問題は類題があるから、それで早解き出来た人も結構いるかも D、平衡二分探索木のsplit-mergeみたいなのでどうにかできないかなというのは自分も少し考えたけど、反転と組み合わせてそういう操作ってできるんだっけ Aって出力形式変えたらN, M<=1e18 とかで解けたりしない? 上から全探索だとO(N)はかかっちゃいそう
(10^N - 1) % M自体はO(log(NM))で計算できるけど N<=10^18,M<=10^5ならグラフ作ってBFSとかでいけそう というか別にグラフ作る必要もないか
f(x) = (x-1)/10を作用させ続ければO(M)で解が見つかるか、不能判定ができるという話 というか10^(10^5)なんて数を扱う事あるのかｗｗｗ
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1463346279
＞1m3に10個程度の原子（ほとんど水素）なら10^79となります。多めに見積もっても10^80は妥当なところだと思います。宇宙の半径130億光年であっても1桁増える程度です。 解説読んでなかったわサンクス 本番(10^n-1)/9とEulerの定理方針が最初に見えたんだけど300点なことを思い出して引き返せた 累乗modの問題だしオイラーの定理で高速化できるか
頭固かったわ atcoder.jp/contests/abc137/tasks/abc137_d
この問題の解答を作ったのですが、一部の入力例に対してしかパスしません。
どこにバグがあるか分かる人はいますか？
解答は以下です：
ideone.com/uZ1cUa >>970
のバグが分かりました。
大槻の『AtCoder入門』ですが、結局、独力で解答を見ずにすべての問題を解けました。 >>949
ありがとうございました。
>>950
問題集ってPASTの問題集ですか？
米田の本はまだ見ていないのですが、売れ行きはいいですよね。 ideone.com/z97s8q
バグの修正を上のようにしました。
パスしなかった入力を見ることができれば、バグ修正もやりやすいでしょうが、
実際には見ることができません。
みなさんはどうやって、バグ修正していますか？ 大槻の『AtCoder入門』ですが、普通の「アルゴリズムとデータ構造」の本に書いてあるようなことは
ほとんど書いていない変な本ですね。
競技プログラミングで「アルゴリズムとデータ構造」の知識をほとんど必要としない問題用の本ですね。 その本はプログラミング経験もアルゴリズムの学習経験も皆無に近い人(中高生も含め)がatcoderのC問題あたりを解けるようにして、本当に簡単なアルゴリズムを触れるようにするぐらいのレベルのもの
not for youだな
というかそもそも大多数の競プロ本はアルゴリズムとデータ構造の教科書を志向していないから デバッグは自分でテストケース作ってやるのがいい
実は過去コンテストのテストケースを見に行くことはできるが、競プロコンテスト本番のデバッグ力を鍛えることができないからオススメしない >>976-977
ありがとうございます。
過去問の入力データを見に行けるんですね。
解答を見るのと、解答を見ずに入力データは見るというのだったら、後者のほうが勉強になると思います。
独力で正解を作るのがベストだとは思いますが。 乱数で入力を発生させ、計算量的に悪いけど簡単に思いつけて実装できる部分解法で正しい出力を出せばいいわけで、そんなハードル高いものじゃないぞ
上位層はコンテスト中にちゃちゃっとやってると思う 独力で頑張ってるようで応援してるよ
典型的なアルゴリズムも自分で思いつけるようなものなのか興味ある >>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];
}
とまずすべての入力を受け取ってしまってから、後で処理を書いても良い。 >>972
atcoder probremsってサイトで自分のレートに合った問題をひたすら解くってこと
codeforces ladderとかで検索してもいい。 https://atcoder.jp/contests/abc271/tasks/abc271_b
https://atcoder.jp/contests/abc269/tasks/abc269_b
こういうの問題文読んだだけじゃ何のことか分からなくて、入出力例を見てやっと「あーそういうことかー」となるんですけど、あんまり向いてないのかな？
皆さんは問題文だけで何すればいいのか分かるんですか？ 特にその二つの問題は慣れてても難読だから
問題自体の難易度と問題文の読みやすさは独立 形式的に書きすぎな感はあるよな
こどふぉなんかだと一般的な説明の後に、形式的に説明すると～、って二段階の説明があるから分かりやすい それはそうと直近のこどふぉの問題文全体的にわかりにくくなかった？
ABも誤読しそうな内容だしCですら最初は頭が壊れそうだったのにDに至ってはsetとかいうゲームを遊んだことがなかったせいでルールの理解までにだいぶ時間がかかったわ こどふぉは本当にテストケースから題意を推測することが多い >>986
ありがとうございます。
本が好きなのでつい本を読もうと考えてしまいます。 競技プログラミングの問題の設定ですが、わかりやすさを狙ってだと思うのですが、スヌケ君がどうとか
余計な（？）設定が多いと思います。
純粋に数学的に問題を述べてくれたほうが分かりやすいように思います。 情報を素早くかつ適切に取捨選択するのも能力の一つだし多少はね と思ったらこのDytechlab cupってDiv.1 + Div. 2でratedなのか
https://codeforces.com/blog/entry/105117 このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 433日 19時間 59分 57秒 5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/
▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php レス数が1000を超えています。これ以上書き込みはできません。
