競技プログラミングにハマるプログラマのスレ 24
レス数が1000を超えています。これ以上書き込みはできません。
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)やCTFなどを楽しんでる競技プログラマ(競プロer)の雑談スレ
競プロイベントや競プロ問題や有名競プロerや競プロでよく使うアルゴリズム等について語りあったり、競プロ関連の質問相談なんでもおk
競プロ初心者でググっても解説読んでも分からないことがあったらスレの競プロの先輩方に訊いてみるのも手だよ(分かりやすい解説サイトとか書籍とか教えてくれるかもしれないよ)
次スレは>>950
# オンラインジャッジ・コンテストサイト
## 日本語
yukicoder https://yukicoder.me/
AtCoder https://atcoder.jp/
AIZU ONLINE JUDGE (AOJ) http://judge.u-aizu.ac.jp/onlinejudge/
## 英語
TopCoder
Single Round Match (SRM) 関係リンク集 http://codeforces.com/blog/entry/21879
Marathon Match (MM) https://community.topcoder.com/longcontest/?module=ViewPractice
※TopCoderは初参加までの手順が煩雑です。まずはググってみて、それでも分からなかったらスレで聞こう!
Codeforces http://codeforces.com/
CS Academy https://csacademy.com/
Project Euler https://projecteuler.net/ 和訳 http://odz.sakura\.ne.jp/proj
※前スレ
競技プログラミングにハマるプログラマのスレ 23
https://medaka.5ch.net/test/read.cgi/prog/1581127445 テンプレ続き
# 書籍
プログラミングコンテストチャレンジブック (蟻本)
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (AOJ本, TLE本, 渦巻本)
最強最速アルゴリズマー養成講座 (チーター本)
# 日本人競技プログラマ
Twitter 競技プログラマリスト
https://twitter.com/kinaba/lists/topcoder-jp
https://twitter.com/kobae964/lists/atcoder
TopCoder Single Round Match (SRM) のランキング
https://community.topcoder.com/tc?cc=392&sc=&sd=&cc=392&module=AlgoRank&nr=200&sr=
TopCoder Marathon Match (MM) ランキング
https://community.topcoder.com/longcontest/stats/?module=CoderRank&cc=392
Codeforces ランキング
http://codeforces.com/ratings/country/Japan
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account) AtCoderのプレスリリースで糞グラフ使ってて草
なーにがIT人材()じゃ >>16
俺もこれかと
データをまともに扱う気ないよな atcoder黄色以上で検査増やすな、陽性出ても軽症なら無意味、とか言ってる
競プロ特化型人材に捨てアカで絡んで
遊ぼうかと思ったがそういう都合のいい残念な人は見つからなかった
指数関数の単語を出されて怒り出す橙コーダーとか
面白いと思ったんだがな やっぱ競プロerってリテラシー高いわ〜って 話?よかったねえ ニュースの類にコメントしないだけじゃ
俺黄色だけどリテラシー超絶低いと思ってる ゴッドエイムあきらが鍵アカになってしまったのは悔やまれる おまえら匿名掲示板でコソコソやらずに直接言いたいこと言ってこいよ
https://youtu.be/pkx2gfQeCq0 「文句あるんやったら直接言いに来いや」的なセリフって
定型句みたいなもんで
本当に言いに来られるの想定してないよなって思う >>23
生放送で副社長のツイッターの話に触れた? 競プロの質問サイトみたいなのって無いのでしょうか?
procon-qaというサイトが見つかったですがあまり稼働してないようでした
Twitterは今から競プロ仲間を作るのは難しそうですし… procon-qa
teratail
5ch
テキトーなSlack
好きなとこに投げると良い
今からでもTwitter やるのもおすすめしとく twitterで適当にリプでも投げれば良くないか
コミュニティに入りにくいとかはあるかもしれんが 黄色くらいならこのスレにもいるから適当に質問してくれていいぞ 教えたがりって結構いるからな
手軽に優越感満たせるし相手も喜ぶからwin-win Google Code Jamにはレジりましたか?
明日からですよ!緑色コーダーでも記念参加してみてはどうですか?水色以上はもちろん参加しますよね?
明日の予選ラウンドは早解きではなく30ポイント獲得全員進出できますよ!
明日の朝から27時間コンテストと時間たっぷりあるので機械翻訳使いながらゆっくり解いても大丈夫ですよ!
https://codingcompetitions.withgoogle.com/codejam 開催スケジュールを見て分かるとおり今年のGoogle Code Jamは日本の競プロ勢が参加しやすい時間帯!Tシャツ狙ってゆきましょう!
https://codingcompetitions.withgoogle.com/codejam/schedule >>36
予選ラウンドはABCのC,DくらいからARCくらいの難易度
その次のラウンド1はARC級の中堅
その次のラウンド2はARC級の高難易度
AtCoderで例えるこんな感じだったかな? Tシャツが欲しいけどこどふぉで1000位のレーティングは2232なんだよな
厳しい 最近やってないけどGCJだけは出るみたいな人結構いるからもっときつくないか 最近やってない人は早解きやコーナーケースに弱い
コドフォのレート順位は18歳未満を含む 仕事に忙しいオッサンになると競プロのノウハウやテクを忘れっぽくなるからGCJだけ復帰勢で驚異になるのはごく一部 明日のABC、参加者数が楽しみ
プロ競技プログラマーの誕生のために! GCJの参加は16才以上、オンサイトは成人年齢以上、? GCJ、これからやるんだけどQualifiedにレがついてるのはなんだろ そのコンテスト自体の参加資格っぽい
特に制限がないから全員ついてるんじゃない? デキューしたものをxとする
(x%10)≠0なら10x+(x%10)-1エンキュー
10x+(x%10)エンキュー
(x%10)≠9なら10x+(x%10)+1エンキュー >>56
1~9を順番にキューに入れといて
1取り出したら10,11,12をキューに突っ込む
2取り出したら21,22,23をキューに突っ込む
これを繰り返すってだけ >>55
これが正しそうだね
珍しいミス
>>56
ただ小さいほうから列挙するという話
Kが小さいんでうまくいく また引用RTで晒し上げやってんな
そういうとこだぞ 全く関係ないお受験とか言い出して、コンプ丸出しでワロタ
化けの皮が剥がれてる草 みんな何処みてるんだ
chokudaiくらいしかフォローしてないからvtuberとか何の話かわからん きりみんとか言う奴だろ
キャラ崩壊とか言われてもそもそもどんな奴だったか知らんが Educational Data Structure Contestが待たれる でも実際今日のBとかCは何がしたいんだと思う
アルゴリズムとか何の関係もないし方向性がわからん B問題はいつもと変わらんくない?
「繰り返しや条件分岐を使ったプログラムを正しく組めますか?」っていうよくあるやつだと思うけど 何がしたいも何も昔からこういうゲームじゃん
競プロは結局競プロに過ぎないしアルゴリズムが勉強したければ専門書で勉強すべきだし、プログラミングがやりたいならアプリでも作ってりゃいいんだよ
最近就職に役立つ!とかプッシュし始めたせいでその辺り勘違いしてる奴多そうだが vtuberのやつ意外と長く持ったなっていう感情しかねえわ
対して競プロしてない癖に毎回うだうだ言っててすぐやめると思ってたわ >>71
Writer本人が「整数除算でハマる人が多かった」ってツイートしてるけど
それだと「繰り返しや条件分岐を組める」からちょっと逸脱してる気もする >>ABCの問題で解けない問題があった人
問題の傾向に文句を言うのではなく「プログラミング/アルゴリズムに関する知識や論理的思考力が身についていないことに気付けてよかった」と考えるのがオススメ 就職に役立つは本当で、コーディング試験/面接がクソ余裕になるんだな
楽しくもないのに就職のためだけに毎回コンテスト出るのはコスパ悪いし、1ミリも実務開発経験の足しにはならんけど
>>74
順位表を見て正解者が多い問題から解くと吉じゃ CとDのAC数差5000人超えてるんだな
5000人にとってはただのC早解きゲーでしかないってことか
BやめてCとDの間のDIFFでもう一問作ればいいのに データ構造総当たり選手権の人にクソリプ送る奴がいるからツイ消ししてる
こうやって敵を作っていくんだよな
晒した本人は自覚ないから本当に厄介 パズル解くだけならまだしも、たくさん問題解いて典型を身につけるっていう作業は、どこが楽しくてやってるのか聞きたい まぁ晒されるようなしょうもない発言するな って感じはする。
しかもエアプっぽいしなあ。 元々有名な人だからしゃーない
>>82
俺はそれはそれで楽しいけどなぁ >>84
競プロだけに役立つ能力を伸ばすためにわざわざいろいろ覚えて時間を費やすというのが自分は好きになれん。
パズル問題は、解いて全能感を味わうのが好きだがw ペンシルパズルの類も強くなろうと思ったら大抵定石覚えるフェーズがあると思うんだけど あー「パリティを考える」「逆から考える」とかの定石は楽しいが、「全方位木DP」とかそういう高度定石が嫌 解けそうにない問題がこういったデータ構造/方針で解けるようになる
ということを知る快感を味わいたいんじゃないか、自分はそう >>81
マジで教祖と信者で草
昔のヤバい奴らと同じ構造だな 競プロ界隈って信者ファンネル流行ってんの?
荒野行動みたいだな 馬鹿野郎レート上げるためにやってるに決まってんだろ >>81
chokudaiがクソってより一部の競プロキッズがクソ
てか調べた感じ競プロキッズの一人がクソ >>81
普段のchokudaiは意図して信者をけしかけてるフシがあるけど
今回の晒し方的にはちょっと予想外なんじゃね >>81
自分は悪くないとか思いながら、嫌われていくんだろうなあ >>95
俺も今回は思わぬ方向に行ったと思ったが、その後のフォローが一切ないのはさすがに悪手 信者に突撃させて気に入らないブログとかツイを消させるのが気持ちよくなってるんだろうか
好きにすればいいけどリアル企業としては関わり合いたくない >>98
何かあれば一瞬で燃えるやつだからな
関わらない方が賢い 周りに苦言できるのがいないから勘違いしちゃうんだよね
本人が自分は平均的にやってると思ってるところも逆に作用してるし わざわざ苦言を呈してきた人間も一人ひとり潰していったし SNSで他ユーザーや界隈に挑発的意見や攻撃的言動する人たちの意図は何? >>105
反応してもらえないからってイライラすんなよ笑
小魚でもポリポリ食ってろ >>109
これ向こうのネタだから反応しなくていい 5chのスクショ撮ってtwitterで晒してるやつ何なん クソほどどうでもいい内容だった...
言語アプデコンに備える 赤とかwriterならいいけどそれ以外の人をさらすのはやめようね 昨日初めてatcorderをやってみたのですが、gccのc言語でabcのbまでしか解けませんでした。c ++は何回か触ったことあるのですが、回答を見たところ読めないところが多く、手始めにこのスレで紹介している書籍のどれかを買おうと思うのですが、どの本が一番おすすめですか? 教科書的につかえてC++前提なのって「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」だけ
あと公式でC++入門あるのでこれでもつかめてくると思う https://atcoder.jp/contests/APG4b
蟻本は辞書的に使う感じある 本は全体的に内容が古いし、ABCレベルの初心者にオススメできるものじゃない
蟻本は強くなったら役に立つけど今はまだ要らない
AOJ本はアルゴリズムとかデータ構造一通りさらうにはいいけど、どっちかというと競プロって感じじゃない
チーター本は読んだこと無いからよく分からん
C++まだちゃんとやったことないならAPG4bをやるのがいいんじゃないか
https://atcoder.jp/contests/APG4b ありがとうございます!アルゴリズムとかデータ構造って本買いました。届くまで時間がかかるのでapgってやつやりながら待ちます! 何を良問と思うかは人によって違うし実際どう思っている人が多いか知りたいならTwitterの投票機能で調べてみるといいかもね パソコン甲子園、早く解説を公開してくれ
作る時間は十分にあるよね? 負荷テストとやらは終わったが真に言語アプデされるのはいつになるんだっけ 早ければ来週のABCらしいが
まあ今月中には移行できるんじゃね 会津オンラインジャッジはいつコンテストやってるんですか?
コンテストバリバリ参加しないとレーティング上げられないじゃないですか 今度はbits/stdc++.hか
競プロ初心者にとっては紛れもなく有益ではあるがまあ競プロ外に持ち出すべきではないよなぁ 競プロ外に持ち出させるべきではないというのもまあ正論 C++界隈と競プロ界隈では言語に対する姿勢がほぼ真逆だから荒れるのはしゃーない この手の話題はお気持ち問題だと思うので遠目に眺めます bits/stdc++.h滅べ派の過激派は@kazatsuyuとか@SaitoAtsushiとか何人か見るけど、別に良いだろ派の過激派はどのへん?
滅べ派が目立ってるから頭の中で中和したい 1つの分野しか取り柄が無いエンジニアはアイデンティティ保つ為に無意識にマウント取ってしまうの実際よくある事やから気を付けるんやで 良いか悪いかの意見は割と別れてるけど、過激派はただAtCoder叩きたいだけの人達でしょ
Qiitaを質問サイトとして使うアホをAtCoderが責任持って管理しろみたいなレベルのツイートしてる奴が1人じゃない訳で 初心者にC++教えようとしてる時点で間違ってる
Rust教えていけ >>146
他人の意見でバランスとってると何かある度に流されまくるだろ。中和なんか必要なくて、自分の判断で確固たる立場をとればいいと思うよ。 重要なポイントとしてとりあえずbits/stdc++.hって書けって書いておいて
処理系依存だから注意みたいな話は初心者は読まなくていいってまとめられてるゾーンや付録にしか書いてないのは不親切だとは思う コドフォとかトップコーダーの問題のアイデア、
バンバンAtCoderに取り入れて欲しい
AtCoderさえやり込めば、最新の知見が手に入るように
して欲しい 最新の知見ってなんだよ
先月publishされた論文に載ってたアルゴリズムで解けるようになった問題を出します!とかか? segment tree beats の例題がatcoderに見当たらなくて苦労している
全方位木dpも500点くらいの欲しい みんなからAPG4bってやつすすめられてやってみたけど,なんだこれって思ったらちょうど話題になってるのね、includeなんちゃらってやつ、 全方位木DP、600点以上のアルゴリズムじゃないか?
そもそも木DPを書かなきゃいけない上にそれを高速化する訳だし、低く見積っても600点だと思うが
beatsは知らん segment tree beatsって英語ではなんて呼ばれてるの? beatsで殴れる問題ならある
ratedでは知らない たんなる木DPなら塗り絵とか今だと500点で出そうだけど
500点って水diffでしょ?全方位木DPで水は典型そのままでも怪しそう 名前が付いてるものを勉強したがる病か?
だからレートが上がらないんやぞ 勉強は別にいいじゃん
AtCoder のレートにはまあ直結しないだろうけど >>160 beats自体がこどふぉブログで付けられた名称だから海外でもそう
アカデミックだと知らん(そもそもアカデミックのセグ木は平衡二分木にモノイドを載せるやつを指したりするし) 全方位は練習として再遠点を求めてみるといいよ Verifyは全点のMax(=直径)でできる 最近問題を解くだけではレートが変わらなくなったんだが
レートに直結する勉強って何? >>167
問題を解くことに直結することしかしてこなかったから成長が頭打ちなんじゃないか? >>154
Atcoderなんて所詮計プロで遊びなんだしそんなの期待してもなぁ
それにdata structure algoなんてnp解決とかない限り従来の知恵何らかに適用とかで大きな革新なんて殆ど無くね?
Kaggleとかの方がそうゆうのあるだろ(´・ω・`) chokudaiが強くなるための一番わかりやすい方法はバチャって言ってるよ バチャで食い散らかしたら復習キューが山積みで消化しきれん GCJ1Aってレーティングどのぐらいなら通過できそうですか? Round1は1500人ずつ抜けていく形式だからAが一番厳しいよ
2200くらいはないと無理そう パソコン甲子園、何故解説を公開しない?
作る時間は十分にあるよね?
AtCoderなんて毎週開催でちゃんと公開してるよ 全世界でみると時間帯の影響がどうなるかよくわからん 夜型の人は知らんけどもBの時間帯は厳しすぎるしCは最後だし
Aから頑張るのがいいと思うけどなあ 5chみたいに匿名かつその人がどんな人か分からないなら攻撃的な口調の意見とかそこまで気にならないんだけど、
Twitterだとアカウントと本人との結びつきが強い場合が多いから「あ、この人こんなこと言う人だったんだ……」って感じで残念な気持ちになる。
もちろん人それぞれ考え方は違うだろうけど、競プロ界隈の雰囲気を少しでも良くしたいのなら、せめてTwitterくらいは大人しく使うべきなんじゃないかな。 火のように時間にせかされ
ろくな助力もなく問題の根拠も確かめられない
なんでみんな冷静にやれるんだ? Educational Codeforces はじまるぞー Springerがコロナ禍で無料公開した教科書に競プロに役立ちそうなものもあります
Guide to Competitive Programming
http://link.springer.com/openurl?genre=book&isbn=978-3-319-72547-5
The Algorithm Design Manual
http://link.springer.com/openurl?genre=book&isbn=978-1-84800-070-4
Computational Geometry
http://link.springer.com/openurl?genre=book&isbn=978-3-540-77974-2 英語読むの厳しいな〜
TOEIC950くらいまで勉強すべきかな
950取ったところでスラスラ読めるようになるとは思わんけど… どなたか、競プロについて気軽に雑談できるDiscordサーバを知りませんか?(Discordでなくても構いません)
実力は水上位です。今年中に黄になることが目標です
とあるサーバは見つけたのですが、そこでは既に緑の人が仕切っているのでコメントしづらいです あと話は変わりますが、一度1000点の問題を解こうと思っています
目的は「目指すべきところを明確にしたいから」ですが、効果はあるでしょうか?
もしあるのでしたら、おすすめの1000点問題を教えていただけると嬉しいです
もうひとつ、700〜800点問題はいくつか解いているのですが、
700〜800点問題と1000点問題の違いなどを教えていただけると嬉しいです 点数は飾り、ですか…
700点問題と1000点問題はあまり変わらないということですかね? >>205
明確な違いなんてないんだから、人に聞かずに自分で解いてみればいいだけだろう 簡単な高得点問題の話題でRow to ColumnとTree Gameがないとかエアプか? game on tree って証明辛くない?
row to column はコンテスト全体の点数がインフレしてるだけに見える >>206 >>208
具体的に問題を教えていただきありがとうございます!
早速「Road of the King」から解いてみます
Twitterで探すといっても、具体的にどうすればいいかわからないんですよね…
競プロerをフォローしまくることから始めるのが良さそうですが、そこからどう行動するか…
いきなり話しかけるといっても、何を話せばいいかがわからないです… これで簡単な方なんだろ?
とてもじゃないがD解ける気がしなかったわ JOI難易度11?と思ったら1<=j<=N/2全部かよ
そんなの解けるのか >>198
必要ないのは確かだが
TOEIC0なら英語問題そもそも読めないだろアスペかw D速攻で解答できてたのに掛け算のオーバーフローに気づかずオワタ >>219
そうだった
これからint全部long longで書こうかな >>200
自分はもっと下のレベルだけど雑談できる場所は確かに欲しいですね
twitterも大体既に繋がりができてて入りづらい twitterは垢つくってコンテスト後にぽつぽつ呟くだけになってる
AtCoder のプロフにtwitter ID 登録してあるからかそんな垢でもぽつぽつフォローが飛んでくる、使ってる言語がC++以外だからかも知れんが >>224
O(N^2)は出来てたんだけど答えをintにしてた レート変化-65wwww笑うしかねえ
Eにハマりまくって終わってしまった、なんか再帰でいけるくね?とか思って方針ミスって時間が溶けていった atcoderは
#define int long long
してまず問題なさそう 昨日のF、とりあえず2乗のDPをメモ化再帰で実装して枝刈りすれば計算量とか考えてなくても通るか というかまともに枝刈りができれば計算量がO(N)なのは明らか Dで4000のO(N^2)はスクリプトだと無理だと思ってた、
Cの想定解の200^3ですら怪しかったので Cは何も考えずに書くとlogつかないか、前計算できるけど >>223
そうなんですよね〜
ということは、友達のいない人(僕のような人)がDiscordで競プロのサーバーを立ち上げたら、
ある程度人が集まったりするのかな… 一から実装した二分探索に比べてlower_boundのほうが圧倒的に速いんだけど何でだろう?
・一から実装→1000ms
・lower_bound→500ms
みたいな結果になる >>236
エスパーに期待してるのかもしれんけど
「一からの実装に無駄があるんじゃない?」
としか言えん気がする >>236
lower_boundのソース見たら? ある程度、作問した人には敬意を持つべきだなあ と思う。まあ学生だし仕方ないかって気持ちもあるけど。みっともない。 CとEのGCDを足していく行為は、数学的に無意味でアホなんじゃ無いかと思う 無意味でアホかもしれない問題に真剣になるのが競技プログラミング 競技プログラミングはもう数学ができるかどうかで
本質的な意味を失っている。 蟻本に載ってるようなアルゴリズムに詳しくなりたいというモチベーションがあるならatcoderよりコドフォやaojの方がいいのかもしれない CってO(N^2logN)でできるよな
いくらなんでも愚直解が想定解なのはC問題としてはダサくないか 一律給付への頭悪いコメント
誰か止めるやつは居なかったのか・・・ >>260
去年のbyeは最低でも2000越えてたのに今年は1700台もいて草生えるなw
去年 https://tco19.topcoder.com/competition-overview/algorithm/algorithm-byes
どうせ今年はコロナの影響でオンサイトは無さそうだし
最悪スポンサー付かなくて賞金なしになったりしてなw
りんごさんがGCJに出なかったのはオンサイト見込みが無いからだろうか? パソコン甲子園は早く解説を公開してくれ!
たった年1回の行事だぜ? 世界には何十億人といる人間のうちたった1000人にしか与えられないGoogleCodeJamTシャツを日本勢は何人獲得するだろうか 修正前のbyeを信じてRound1を逃した人いたらかわいそう コロナ、頼むから収束してくれ
ICPC含め、競プロオンサイトイベントが死んでしまう 競プロ、どう考えても影響が小さいしいくらでもやりようがある界隈なんだよな 競プロはまだましだからいいよね
ある程度の実力がついてきたからオンサイトにチャレンジしたいが まあオンラインでどうにかなるけどさ、あのTシャツ着るのと強豪チームがアホみたいに風船増やしてくのを見たいんよな atcoderのここ最近ABC人数見ても引きこもりで、競プロ人口は増えてるイメージ
オンサイトみたいなお祭りもあった方が良いとは思うが、他と比べても別に無くても特に困らなくね? コドフォより安定してたのは参加者が少なかったからってオチか 3ヶ月ぶりか?
Unratedのときに限って調子良い法則。 オンサイトはコロナで人集められず終わり
オンラインはコロナで人集めすぎで終わり こどふぉ散々でぃすっといてこどふぉより悪いのウケるな まあ無料でこんなことやってくれるだけでもありがたいから残念だけど責める事でもない unratedも難易度やジャンルの偏りも慣れた
色が変わりそうなときにはやきもきするけど >>293
Atcoder Jobsやってるし一企業のやってることなんだから失敗続きはまずいだろ 自分にとって不快だったからwriterやめろねぇ......
とは思うが、運営もよく利用者に不快だからサービス使うなとか言うし、そのしっぺ返しみたいなもんやね 社長やらwriterからして治安が悪いにも関わらず競プロ界隈は治安が良いと言われてた時期があるらしい
(どんだけ信者に我慢させてきたんだ) 相変わらずのうんこ具合で安心した
巨大な糞を集めるんだなw 社長の囲い本当にうぜえ
今までの流れあった上でまだ鯖代ケチってunratedしてるのはマジで無能だろ 計算量は嵩むが解ける
高速な実装なら通っても驚かない レッドコーダーが居ても適切なサーバーの個数を見積もれないとバレるのは痛手だろうね You can use DeepL or Google Translator ;) 参加権を抽選にすればサーバ負荷を軽減できるのでは? Eの解説を読んでもよく理解できなかったのですが、
要するに、活性度の大きいものから順に端へと配置していく、という認識で合っているでしょうか?
たとえば、A = { 1, 3, 4, 2 } であるとき、
1. 4 を右端か左端に配置
2. 3 を右端か左端に配置
...
というふうに配置していく、ということでしょうか? あってる
端に配置するという操作で貪欲にやると死ぬのでDPをしている >>313
ありがとうございます
追加で質問なのですが、
「活性度の大きいものから順に端へと配置していくのが最適」
であることを証明したいのですが、うまくいきません
一応自力での証明を試みたのですが、場合分けが多すぎて綺麗に証明できそうにありません
よければ、綺麗に証明する方法などあれば教えていただきたいです >>314
確信はないけど、まったく同じアルゴリズムで解けるはず 競プロをする上での証明力を鍛えたいのですが、
おすすめの書籍やWebサイトなどありましたら教えていただきたいです
(具体性のない質問になってしまい申し訳ございません)
「〜を昇順に選んでいくのが最適」といった貪欲は、
大抵きちんと証明せずに提出してしまいます(本番でも練習でも)
この癖を改善するためにも証明力を鍛えたいです
皆さんがどのようにして証明力を鍛えたかどうかも教えてほしいです
ちなみに私は青です
アルゴリズムの知識は豊富にありますが、それらを組み立てる能力がまだ足りなく、
今のところ黄色になれる気がしません >>315
解説の説明ではダメなのかな
コンテスト中は私はまともに証明してない
発想としては活性度が 1 3 2 みたいに凸な並びが変換後にあるなら3 を端に寄せた方がスコアは良くなる
-> 変換後の最適解の形は 凹
みたいな観察で解いた
証明力は私も欲しいと思ってる... 貪欲の証明は、それをしなかった結果を仮定して、それより結果が悪くならないというロジックが一般的だね
上から順に端に寄せなかった場合、それより小さい数字が両端にあるから、どっちかと入れ替えても値が悪くならないって考え方でいけるはず アルゴリズムイントロダクションにその辺のこと確か書いてなかったか >>298
今回Writerの悪口って観測できなかったんだがあったん? なんかEの「原始的なDP」って言い方を煽りと取った人がいるらしいよ
俺の見てたTLでは大喜利になってたけど 原始棒銀、原始中飛車を使われたら煽られたと見てよろしいか? 将棋ってカードゲームでもないのに環境かわったりすんの? 対戦ゲームは流行り廃りがあるだろう
将棋がそうかはしらんが流行してる戦術のメタ、改良考えるのは基本 いくらABCとはいえ中世DPまでは使えてほしいですね(呆れ) 原始的なDP、std::vectorが使えなさそう >>324
それか…煽りかは知らないけど何の情報量もない言葉だとは思う
普段から説明不足でヘイト溜めがちなんだから余計な事書かなければいいのに ○○dp みたいなのが多いんだから
原始的なdp と言うことによる情報はあるだろ。 >>318 >>321
ありがとうございます
証明できそうです
---
移動前の位置を i, j, k、移動後の位置を Pi, Pj, Pk とする
そして、Ai > Aj, Ai > Ak, Pj < Pi < Pk を満たすような (i, j, k) が存在するものとする
[1] Pi ≦ i の場合
Ai と Aj をスワップしたとき、Ai のスコアは Ai * (Pi - Pj) 増加する
そして Aj のスコアは最大でも Aj * (Pi - Pj) しか減少しない
Ai > Aj より Ai * (Pi - Pj) > Aj * (Pi - Pj) を満たす
よって、Ai と Aj をスワップすることで、全体のスコアは必ず増加する
[2] Pi > i の場合
Ai と Ak をスワップしたとき、Ai のスコアは Ai * (Pk - Pi) 増加する
そして Ak のスコアは最大でも Ak * (Pk - Pi) しか減少しない
Ai > Ak より Ai * (Pk - Pi) > Ak * (Pk - Pi) を満たす
よって、Ai と Ak をスワップすることで、全体のスコアは必ず増加する
[1] と [2] より、
Ai > Aj, Ai > Ak, Pj < Pi < Pk を満たすような (i, j, k) が存在するとき、
全体のスコアが必ず増加するようなスワップの方法が存在する
このスワップ操作を繰り返すと凹の形になる
したがって、最適解は必ず凹の形である(証明終了)
---
自分の証明を人に見てもらったことがなくて不安だったので、証明を投稿しました
証明として不十分なところや間違っているところなどありましたら指摘してほしいです >>322
Amazonで調べたのですが、けっこう高いですね…
購入するかどうか悩みます 原始DPを煽りと捉える人は低レベルプログラミングも煽りと捉えてそう こどふぉの Editiorial 見てたら, 尺取法のことを Two Pointers Like Algorithm って書いてあったんだけど,
英語圏と日本語圏で用語が違うケースもあるんだな >>345
低級言語、低水準言語はlow-levelの訳だし語句自体は適切だと思う
フクザツなメンタルの方々へのお気持ちへの配慮については知らん パソコン甲子園、いつになったら解説公開するんだよ
時間はたっぷりあるだろ?
参加者のこと何だと思ってるんだろうね? AtCoder、攻撃的な言動がお得意なのが多いからその手の人間が書いたと思うと引っかかる気もするな
書いた人が実際どんな感じか知らんけど 解説からじゃわからんがwriter自ら公開してるから少々のネトスト力があれば特定は容易 フルマネージドなサービスがスケールしなかったってことかな?
急激にトラフィック増えるサービスと相性悪そうではあるが。 unratedな上級者は10分遅れスタートでいいんじゃない 会津オンラインジャッジのそれぞれの言語で使用されるコンパイラのバージョンはどこで知ることができますか? AOJで根付き木の問題(Rooted Trees)を解いてるのですが、根はどうすれば求まるのでしょうか?
Solutionsのコードを見たり「根付き木」で調べても分かりませんでした 木を「辺が親から子への方向を持つような木」とみなせば、
「入ってくる辺の数が0なら根」と判定できる System Information
update: 2018.01.25 読んでる本で
int sum[MAX_N];
int t = lower_bound(sum + s, sum + n, sum[s] + S) - sum;
というコードが出たんですが、(s, n, Sは整数)
これをvectorで実装するにはどうしたらいいんでしょうか?
sum.begin() + s
などはエラーを吐きました >>363
符号なし整数を符号つき整数に暗黙キャストしようとしたから出た警告では? >>364
すみません言葉足らずでした…一応累積和の問題だったんですが
改めて読み返すとこの文では読み取れませんね
完全にこちらのミスです申し訳ありません
>>364
ありがとうございます
原因なんですが色々弄っていたら最終的に
int t = lower_bound((sum.begin() + s), (sum.begin() + n), sum[s] + S) -
sum.begin();
でうまく動いたので自己解決しました
おそらくvectorでの実装の時イテレータと整数をどこかで間違えてたんだと思います
ご迷惑をかけてしまって申し訳ありませんでした >>361
すみません、基本的な事が分かってないかもですが
木は接点同士が繋がっているので必ず入ってくる辺が1以上にならないでしょうか?
(親が一意に決まるなら親のいない接点が根だとわかるのですが) http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A&lang=ja
この問題か
子の情報だけ与えられるからぱっと見で根が分からんってことだよね
根の判定だけなら、例えばn要素の配列を持って、子として与えられたノードに1を足していく
最終的に0で残ったノードは誰の子でもないので根
とか >>369
すみません、その問題です。例えば出力例2だとnode1が根になってますが、
他のnodeが根でも根付き木が作れると思うのでルールが分からないです…
node1の接点がnode0という事は、node0から見るとnode1が子という事ですよね? >>370
そういうもん
無向木の根に特別な性質はない。恣意的に決められただけのもの 入力例2は
1の子は{3,2,0}
0の子はない
3の子はない
2の子はない
「根」は「一番上にあるノード」のことだから1が根だよ 自分の書いたコードを人に見せたい欲が抑えられないのですが、
どうすればいいでしょうか? 時間があるならブログ作ってサンプルコードをpythonにして難しめのアルゴリズムの解説記事をガンガンアップしていけば見る人は多いはず
cppは既存記事を押しのける必要があるから微妙 >>340
この証明が証明として成立しているかどうかが知りたいのですが、
どなたか教えていただけないでしょうか?
社会人になってから競プロと数学を本格的に学び始めたので、
指摘してくれる人もおらず合っているかどうかが不安です… >>371-372
なんとなく理解できました。無向木と言っても親→子は一方通行なんですね?
同じ形状の木でも問題の書き方によって根が変わるんですね…
何度もレスしてすみません、有難うございました >>340
正しそうに見えます。もっと厳しくできて、Pi<=iのやつを←、Pi>iのやつを→と書くことにすると、完成形は←←←...→→...の形になることが言えます。
この形なら一番左の←が最大、一番右の→が最大なのも比較的明らかです。 蟻本の第二版を読み始めたけど、36ページのLake Countingの実装例、微妙に変じゃない?
char field[MAX_N][MAX_M + 1]
って定義されてるのにメイン処理では field[x][y] のように参照されてて、xとyの使い方が逆のように思える。
変数名だけの問題だから、競プロやる人はあまり気にしないもの? >>379
確認していただいてありがとうございます!
正しいのですね。安心しました https://atcoder.jp/contests/abc161/tasks/abc161_e
こちらの問題の解法がわからないため質問いたします
とりあえず、考えたところまで書きます
Sの'o'の数をMとしたときの、頂点数Mのグラフを考えます
そして、次の'o'までの距離が+C以上の頂点に長さ1の有向辺をはります
このグラフ上での最初の頂点から最後の頂点までの最長距離がK+1以上であれば、
どの頂点を消しても最長距離はK以上になるため、必ず働く日は存在しない
↓ここから質問
それ以外のとき、各頂点について「自分自身を削除したとき、最長距離がK-1になるかどうか」を判定したいのですが、
その方法がわからないです
愚直にやると、最長距離を求めるのにO(N)かかり、全体でO(N^2)かかってしまいます
どのような工夫をすることによりこの計算量を減らせるでしょうか?
それとも、この方向性では解けない、または解くのが難しいでしょうか?
長文失礼しました。回答していただけると嬉しいです それだと全部"o"でC=1の時に辺の数が(10**5)**2にならない?どうやって辺張るの >>383
実際に辺を張るわけではなくて、
考察のときだけそのようなグラフを考えるという感じです
このグラフをそのまま実装するとO(N^2)になりますが、
このグラフの最長距離を求めるだけであれば、セグ木を使うことでO(NlogN)で計算できます ただ、500点問題でセグ木を使う時点で、誤った解法の気がしてならないです…
セグ木を使い始めるのは600点問題からだと思う… セグ木と言ってるが更新もしないし、前からと後ろからしか使わないんだろ?
だったらセグ木じゃなくてもいけるということだ >>380
xyを横縦に対応させるか右手系に対応させるかはよくある宗教問題 dp[i] = (dp[0 ~ max(i - C - 1, 0)] の最大値) + 1
という更新を前から行うことで dp[N] に最長距離が入りますが、
「dp[0 ~ max(i - C - 1, 0)] の最大値」をセグ木を使わずに実装できるものでしょうか?
なんとなく、setなどを使うことで可能な気もしますが… >>388
ああ、>>380ってそういう意味だったのか
数学つよつよのりんごさんが、いつかの解説放送で「Xを下方向、Yを右方向が一番好き」と言ってたから、
「競プロする人はあまり気にしない」は違うと思う
蟻本の著者のこだわりやルールがあって、その変数名を選んでるんだと思う 今気づいたのですが、普通に累積maxを取ればできますね
セグ木必要なかったです 下方向が第1座標、右方向が第2座標だと数学での座標平面を時計回りに90度回転させたものになっていて綺麗だし、普通にループ書けばメモリアクセスも連続する >>392
画像処理では右にx座標正、下にy座標正をとることが多いから、プログラミングでは左手系がデファクトだと思ってる
こういう宗教戦争が起こるからそもそも競プロ以外で使うべきでない変数名なんだけど 右手系!そういうのもあるのか
こだわってる部分をこだわりがないとか言ってしまって失礼しました。教えてくれた人ありがとう。 OpenGLでは基本的に右手系だし、プログラミングでは左手系がデファクトってわけでもないと思うけどな 左手系って例えば回転とかするとき頭壊れないのか?まあ慣れるかもしれんが >>373
競プロ系ユーチューバーとしてデビューするといいです https://dotup.org/uploda/dotup.org2125825.txt
このUnionFindの実装でsizeの時に返り値が連結成分の大きさになる理由がよく分かりません
この場合のparは根とはまた違うんでしょうか >>399
連結成分の根かどうかで、parの値の意味が少し変わります
・根である:parの値はマイナスで、絶対値は連結成分の大きさ
・根でない:parの値は非負整数で、値は親の頂点番号
普通に実装すると根のparは-1になりますが、
ここに連結成分の大きさを保存しておくと少しだけメモリ使用量を節約できるので、
こういった実装をしたのだと思います >>400
本当にありがとうございます!
根とそれ以外でparの意味変わってくるんですね…ずっと悩んでたんですが言われると納得しました
そういう問題が本当にあるのか私のレベルだと分からないんですが、万一UnionFindで連結成分の大きさと
各成分の根を求める問題が出た場合はその場で根を求める関数とかを追加していく感じなんでしょうか? >>401
そんな感じだと思います
追加する場所としては、UnionFind自身とそれ以外の2つの選択肢がありますが、
僕の場合はUnionFind自身を拡張することはあまりないです
既に完成されたUnionFindには手を出さず、
UnionFindの外側で、別のデータ構造(setやmapなど)と組み合わせて解くという感じです >>398
AtCoderって、同一人物が複数アカウントを持つことは許されていないんじゃ… chrome portableで
ブックマークが競プロ関係のみの意識高いブラウザを作った Atcoder Beginner Copy-Paste Problemsでcがレート0だったので、プログラミングっぽい問題はいきなり1800近くになる 今回のDはABC158のEで既出だからそっちの解説記事探すのが良いかも コピペして青パフォ出したけどEで撃沈したからすげぇ虚しい D 2019で割った余りを保持する割と典型問題なのに解くのに1時間もかかってしまった Dは2019*200000回まわすようなうんちみたいなコードでもACできる E解けなかったの悔しいなー
いくつかのパラメータ持ってDijkstraに落とし込む問題に苦手意識あるな 数時間粘っても問題が解けなかったとき、どうするのが最適でしょうか?
解説を見る前に、「これだけはしておいたほうがいい」みたいなことはありますでしょうか?
たとえば、どういったことを考えたかを文章化しておくとか…
それとも、そういった行為にあまり意味はないでしょうか? 数時間粘っても問題が解けなかったとき、どうするのが最適でしょうか?
解説を見る前に、「これだけはしておいたほうがいい」みたいなことはありますでしょうか?
たとえば、どういったことを考えたかを文章化しておくとか…
それとも、そういった行為にあまり意味はないでしょうか? ABC164のE問題の解説が理解できません
助けてください >>420
i文字目で終わる数xの右にもう一文字y追加して終端をi+1文字目にすると、10x+yになる
0〜i文字目、1〜i文字目、…、i〜i文字目を用いてできる数をmod 2019ごとにカウントしておくと、
0〜i+1文字目、1〜i+1文字目、…、i+1〜i+1文字目を用いてできる数のmod 2019ごとのカウントが、上のやり方で求められる
一回の遷移に2019回ループするから全体で2019×200000回 わからないとだけ言われてもどこが分からないのかがこっちがわからんわい 「最初に銀貨を Amax(N - 1) 枚持ってることにして捨てていく」という問題と
元の問題が同じとはとても思えないんですよね
私が何か勘違いしている可能性大なので、どこが間違っているかを指摘してほしいです >「最初に銀貨を Amax(N - 1) 枚持ってることにして捨てていく」
こんな文章は見当たらないぞ 今、信じられないほど全てを理解できました
>>425さんレスありがとうございました
といっても、まだ辺の数が多すぎて間に合いそうにありませんが、
そのあたりは自分で考えてみます >>422
まさにこの解法考えて、計算量見積もってあきらめてしまったけど、これでいけたのか… 頂点数125,000、辺の数375,000のときのダイクストラの計算量は
O((125,000 + 375,000) × log (125,000)) ≒ O(8 × 10^6)
という認識で合っていますか? 書き方間違えました
8 × 10^6 という認識で合っていますか? うっざ
言わんとしてることはだいたいわかるだろ
答えろよ 演算回数と言えばいいのですね
次からはそう言います
話は戻りますが、頂点数125,000、辺の数375,000のときの
ダイクストラの演算回数は約8 × 10^6ですか? V頂点E辺のDijkstraの計算量がO((V+E)logV)なのかO(VlogV+E)なのかよくわからないやつじゃん
Fibonacci heapなら後者なんだっけ??
まあV+E<=500000なら通ると思っとけばいいよ >>438
回答ありがとうございます
特に実装上の工夫はしていないのでO((V+E)logV)だと思います
>V+E<=500000なら通る
わかりやすい目安を教えていただきありがとうございます
覚えておきます 演算回数って言葉も微妙じゃ…
ヒープの実装見て解析とかまでしたんかな?って思う おおよその見積もりで十分だろ
お前はO(N)の演算と言われて10000000*Nの処理をすることでも想像するのか? オーダーにそのまま数字突っ込むのがそもそもよろしくないという話だが、なんか広まってる以上ぼんやりとつかっている そのあたりの用語の使い方については誰かに任せることにします
続いて質問させていただきます
ダイクストラの実装には以下のように2つの方法があると思いますが、
計算量的にはどちらも変わらない(両者共にO((E + V)logV))と考えてよいでしょうか?
https://dotup.org/uploda/dotup.org2127461.png
1(左). キューからデータを取り出したときにdp配列を更新する
2(右). キューにデータを追加するときにdp配列を更新する できれば@で書きたい(簡潔なため)のですが、
本質的に@よりもAの計算量が優れている場合はAで書こうと思っています
(定数倍程度であれば@を選択します)
回答よろしくお願いします 1の実装はあまり見ないな
計算量は同じだと私は思う. 定数倍は2の方が良好なはず >>445
競プロの文脈で想像するか?
例題あったら教えて欲しい >>447
オーダー記法は競プロの文脈でのみ使われるものではないため >>446
@の実装はあまり見られないのですね
そうなると、たとえ計算量が同じでもAを選択したほうがよさそうな気がしてきました
よくよく考えると、コードの短さ以外でAに勝っている部分はないです
定数倍はAのほうがいいですし、
dp配列の更新タイミングとキューへの追加タイミングが同じなので書きやすい気がします
Aで書くことにします
回答ありがとうございました オーダー記法の使い方に関してうるさいくせにN→∞の省略には何も言わないし定義の理解も曖昧なやつっているよね 普通は2の方が速いけど枝刈りができないようなグラフを与えると最悪同じになる
あと37行目のifを削除してもO((E + V)logV))だと思う なんか2は負辺あっても正しい答えが得られるらしい(計算量は壊れる) pythonってクラス作ると遅くなるの!?笑えるな https://github.com/atcoder-live/library/blob/master/mint.cpp
上記URLの公式のmodintライブラリについてお聞きしたいのですが
.x を付けた時と外した時の挙動って何が違うのでしょうか
例えば提出したコードを簡略化したものが下なのですが
https://dotup.org/uploda/dotup.org2128689.txt
このコードで一番上の宣言部以外で .xを外した場合
入力例では通っても実際のケースでWAが多発しました
自分でも色々入力を変えて試したのですが違いが分かりませんでした
回答よろしくお願いします どの問題?
.xつけたらただのlong longと変わらないはず
外部から直接xにアクセスすることは基本想定されていないと思う 情報が少なすぎて回答のしようがねえ
MODの設定ミスとかa[i] がMODから溢れてるとか
.x つけるとACになるってのがよう分からん と int mを比較するときとか?if (n.x < m)
基本.xとはしないんだと思う 全ての問題を解くときのコンテストペナルティの最小値と、
(そのような解き方が何通りあるかを1e9+7で割った余り)を答えて下さい。 ペナの総和は剰余を取ってはいけない
ペナの総和はMODを超えうる
だからサンプルは通るみたいな https://atcoder.jp/posts/20 にテストケースが見たらないないんですけど
square869120Contest #4 って公式コンテストではないからテストケースはありませんという理解であってますか?
D Driving on a Treeを解いていて
コードテストでは問題ないのに提出するとと全てREになって困ってます テストケースはないのが普通だよ
手元で考えられるだけ試してみるしかない。人によってはランダム生成したりする
ところで
2
2 1
みたいな単純なものも失敗するみたいだけど? (別の人ならすまん 無向木の問題ならサンプルの頂点番号を入れ替えてみるとかもデバッグの手助けにはなるはず >>467
もしかして過去の提出を見てあたりを付けてテストしましたか?
入力のフォーマットが別の問題前提のものになっていたようです。
確かに単純なデータでエラーが出ます。おかげで気づくことができました。ありがとうございました。 >>461-462
ありがとうございます!
ansをlong longに変えたらACだったのでおそらくそれが原因でした
完全に問題文の誤読で申し訳ない… みんなのデータ構造 オープンソース版だと結構誤訳があって辛いんですが
ラムダノート版だと修正されていたりしますか? Asprova プログラミングコンテストって美味しい? ABCのC問題あたりから難しいんだけどアルゴリズムどうやって勉強したらいいですか? 昇順に整列された整数の数列a_1, a_2, …, a_nが与えられるとき、この中からk個選んで(昇順に整列された)数列b_1, b_2, …, b_kを作る。数列bの隣り合う2つの要素の差b_(i+1) - b_iの最小値をmとする。すべての数列bの作り方を考えるときのmの最大値を求めよ。
この問題が解けなくて困っています助けてください あ、>>479は>>477に対してね
>>478
mを二分探索すればよさそう >>482
ああ、なるほど!
ありがとうございます https://twitter.com/kobae964/status/1255834128408211456
東大卒社会人でもスクショ晒し文化を踏襲する人がいることが心証が悪いという意見を強めてしまっていると思うけど
小林弘季さんがどう思われようと知りませんが…
https://twitter.com/5chan_nel (5ch newer account) 「自分が採用担当なら競プロの話してるやつ全員落としそうなぐらい競プロへの心証は悪い」とか公言してしまう人が採用担当になるような会社があったらそんな会社には行きたくないので落としてくれて結構。 競プロ、東大だけ異次元
卓球における中国みたいな感じ
ICPC国内やるか分からないけど、やったら今年は
超激戦になるはず 競プロ上位勢は人格破綻者多いしな
心象悪いのは分かる 二分探索の対象が整数ならwhile、小数ならforで書くといいらしいのですが、
どういうことでしょうか? >>490
適当に答えると、両者とも正確なループの回数は分からないという前提のもと、
前者は「差が1より大きいとき」という条件式で書きやすいから
後者は「こんだけ回せば誤差がいい感じになるだろう」という考えで適当なループ回数(100回とか)を設定するから
これで合ってる?自分、緑レベルなので信じ過ぎないように >>491
ありがとうございます!
後者は、一応 while (x >= 0.000000001) みたいに書くことはできるけど、
浮動小数点の誤差が悪く働いて x が 0.000000001 未満にならないことがある → 無限ループになる
そうなるのが怖いからループ回数を設定しておく
という感じで理解できました!
回数としてはどれくらいが適切なんだろう…
2分の1ずつ減っていくと考えたら、相対誤差10^-9のときは最低30回くらいですかね?
50回ほどループすれば安心かな 関数内で巨大なベクタ配列を生成するとREになり、
それをグローバルな配列にするとREがなくなることがあります
その原因がわかる方教えて頂きたいです >>492
おれは二分探索なら100、三分探索なら200にしてる
実数の問題でTL厳しい問題がそうそうないという認識もあるな それが主眼となる問題はない
意識にいれとくと定数倍の改善の手助けにはなる >>495
制約が厳しめでない限り、50でも100でもそれほど変わらなさそうですね
安心のために100にします。三分探索は大きめに設定するというのも覚えておきます
ありがとうございました! >>494
ベクタ配列の実データもスタックに積まれるんですか? >>467 >>470-471
無事一部AC/他TLEまでたどり着けました
根から葉までの方向と逆方向の入力がない木の直径の問題用のコードを流用したのが原因だったようです。
ありがとうございました。 巨大ながどれくらいをさすかは知らんが
ベクターのヘッダだけで溢れるなんて普通に有りそうだ >>501
ベクタ配列のヘッダってそこまで巨大なんですね
ヘッダはスタックに積まれるという認識で合っているでしょうか?
大きさとしては、vector<vector<int>> dp(5000, vector<int>(5000));
なので、計算すると200MBでした >>493
ACしたコードのvectorをもういっぺん関数内に戻してもREになるか確かめてみろ atcoderの環境ならそれくらい普通に確保できると思うが どうせ未初期化のNで配列サイズ指定したとかそんなんだろ 解説みても誰かのACコードみても何言ってのか分からないバカなんですけどどうしたらいいですか >>508
ここで聞けばたいていの人が反応してくれると思います
というか、コロナで暇すぎるので私が反応します。青でよければ 聞くにしてもレベル(色)が近い人に聞いた方が理解しやすい気がする
2色より下の人に分かるように説明できる人は少ない 赤コーダーが解説見てもコード見ても分からないってことはなさそう りんごさんの2718点問題ってどんな風に難しいのですか? 高度な数学的知識が要求されている印象 >2718点 >>516
まずサンプル1の理解が非常に難解で、「ランダムに座る」を解析的に計算可能な形に読み替えなければいけない
それがうまく行くと次は数Vの積分が待っていて、それを理解することでサンプル1の答えがわかる
ACを取るためにはこの思考をまた天才的なDPに落とし込んで複雑な状態遷移を正確に書けないといけない
という感じ >>521
回答ありがとうございます
実際のところよくわかりませんが、何となくイメージは掴めました あの極限値が初等的な議論で出てくるのはビックリ
CFのインタビュー記事でも強い人たちが結構好きな問題として挙げてた chokudai氏が競プロerの社会性の無さを嘆いてるぞ 競プロがそのまま仕事になると思ってる奴多すぎんの
そんなわけねぇだろ TLにもそんな感じの学生が多くてちょっと可哀そうになってくる
競プロだけ頑張ってれば成功するみたいな 競プロってほとんど趣味ではあるが
応用が容易ではない
深いところの基礎の補強という認識 赤あればどうにかなるというのも真実な気がする
ほとんどの人には関係ないけど 競プロ強い人はだいたい良い大学で計算機か数学やってるイメージだけど
そんな人の就活は凡人とは違うだろ ABC155のDが解けないです
x以上の数の個数を数える方法は理解できたのですが、
個数を求めた後にK番目の数を求める方法がわからないです
何とか頑張って解こうとするのですが、複雑すぎて途中で投げ出してしまいます
どのように工夫すればスムーズに解けるでしょうか? x以上の数の個数が数えられるならあとはもうすぐで、
「積がx以上になる組がK個以上になるような最小のxを求める」
と考えるとxを二分探索すればよいかと。 >>534
回答ありがとうございます
そのあたりを自分で考えようとすると、
x 以上とか K 個以上とか最小の x とかが混在して訳が分からなくなります
具体的にどう混乱するかというと、同じ数が連続するようなとき、
たとえば数列が { 1, 1, 1, 2, 2, 2, 2, 3, 3 } であって 5 番目の数を知りたい場合、
x = 2 であれば x 以上が 6 個
x = 3 であれば x 以上が 2 個
そして 5 番目の数ということは x 以上の数が何個あれば…あーもう訳がわからない
みたいな感じです
このへんを整理して考えられるようになりたいのですが、
どのように考えていけばスムーズに解けるかが知りたいです まずこの問題は最初にやるには考えることが多すぎるので、類題で1ランク簡単な「億ます計算」「Handshake」を先にやることをお勧めする
xを決め打って片方の数aを固定した時にx/a以下の数を二分探索→合計すればよい
不等号は頭おかしくなるから最悪サンプル合う方で提出すれば良い >>536
回答ありがとうございます
解いてみます
不等号が複数絡んでくると頭が壊れるのどうにかしたいです 頭が壊れなくなるなんてことはなくて強い人も壊れる壊れる言いながらやってる 問題の制約に出てくる|S|ってどういう意味でしょうか?
今まで絶対値だと思ってたのですが、例えばABC164-Dには文字列Sが入力のとき
制約が1≦|S|≦200000なのに200000以上の入力例があります |S|は文字列Sの長さを表します
200001以上ってまじ? >>541-542
ありがとうございます!型によって意味が変わるんですね
説明なしで出てくるので常識の範囲なのかもしれませんが、このような
知らない数学記号?が出てきた時はどうやって調べるのがいいでしょうか?
(記号で検索したのですが絶対値しか出てきませんでした) うーんGCJむずかった
Round2に進むみなさんさようなら >>545
記号というのは検索しづらいし、
誰かが「競プロで使われる記号の意味」的な記事を書いているわけでもないから、
今のところ人に聞くのが一番手っ取り早いし確実だと思う 色々検索ワード試してみたけど出てこんなあ
一般論としては「-高校」とか「-受験」とかつけたらいいと思う あ、でもコンテスト本番でわからない記号とかが出てきたら困るか…
うーん、今のところ、これといった解決策が見つからない… そういやたしかに絶対値で文字列の長さを表すってどこで知ったんだろう 開始を遅らせるアナウンスを開始1分前にするって頭おかしいじゃないの? なにが1分前にアナウンスしてF5連打やめてくださいだよw
無理がある >>549
俺は確か集合の濃度から類推した覚えがある 常用できる文字列のノルム的なのが長さくらいしか思いつかない
データ量圧縮したらとかそういうのは強者が考えてくれ 数学的には長さってより同じことだけど空文字列との編集距離って考え方の方がよさそう Cからやり始めたら俺には難しすぎ
Dのほうが簡単だった またlonglongじゃなくてintにして30分以上溶かしたわ
死にてえ 2000↑のパフォーマンスが甘い気がする
ABCやりすぎて少し強い人はみんな黄色になっちゃったんじゃないの 「結論から述べると」の人、問題も解説も嫌い。せめて入試で部分点もらえる位には解説書けよ。 Eリジャッジして順位もう1回出すかそのままでいいじゃん
Unratedの代わりのコンテストでUnratedとかシャレにならないだろ full-feedbackのコンテストだからそれだと公平にならないとか前に言ってた しばらく AtCoder 出るのやめるの検討するレベルにひどいな。
この短期間に何回やらかすの? Cの解説はいいと思う。
全探索で間に合うと気づく所が本質なんだから Cって10重ループで通るから簡単ですよーって事だったのかな >>568
もうわざとやってるっぽいから辞めさせろよ Cは別に良くないか
Dの出題意図の方がよう分からん
っておもったが普段からこんなもんか >>546-548
なるほど、競プロ用語なんでしょうか…
取り合えずは過去問をこなして経験則を高めようと思います
ありがとうございます。 C問題叩いてるやつは解けなかっただけだろwライターのせいにするのやめなよ C別にいいだろ 特定のwriterだけ嫌いな香具師は半年ROMれ Cは良問良解説だったわ
なんでこんな叩かれてるんだ? Cに関しては何千人と解いてるんだから、悪いのは単純に自身の勉強不足と個人的な妬みと嫉妬 いきなり結論から述べられるのが嫌な気持ちは分かる
その解法に至るまでの思考が知りたい所だろうから
俺は公式解説にそこまで求めないが
問題は嫌いじゃないよ 解説はまじでわかりやすいのが人それぞれだからな
評判良かったwriterが全部解説書くとかしたらいいんじゃないすか やっぱwriterに逆らうと5chだろうがボコボコにされるんやなって 無意識だろうがそうでなかろうがファンネルムーブしてる奴ら本当にやめてほしい、ただただ全員が不快になる レートでフィードバックが得られるのがモチベだったから、最近ratedが全くなくてやる気失った
運営が嫌いになって競プロが嫌いになるとかそれ以前の問題だったわ atcoder運営の批判が全部あきらさんに見えてきた僕はどうすればいいの? 黄色底辺だけど、ABCで黄色が大量に増えてきて黄色がどんどんカスみたいになってつらい C>Dっていうのから明らかだけど、AtCoderのコンテスタントたちはそんなに業務能力を有してない思うの。だから下手したらこれきっかけでJobs崩壊しちゃうかもね、ただでさえマイナビとのアレがうまくいってないっぽいし 全探索が書けないの最悪だからCみたいなの毎回出すべき Dみたいな算数パズル解けてもプログラミング力測れないだろ 解説の内容はどっちでもいいけど
わざわざAtCoder運営の立場でヘイト稼ぐの何なんだろうな
副社長が自粛してるのが台無しというか Cは良問だが、今までのCが簡単すぎたのでバグる人多かったんじゃないか。
Dだったら丁度良い感じ。
今回のをratedにしてしまうと今後不具合があっても色々理由つけてratedになっていきそうなのは不安ではある。 問題の質云々よりコンテストサイトとしてヤバいな
開始時刻になってから開催延長告知、問題文修正、再延長
出題不備、更に制約を守れなくてもratedという前例を作るか これ前回がunratedじゃなかったらunratedになってた気がするなぁ
前もあったが2連unratedを避けるために強行しがち
判断が恣意的で萎えるな Cは増加数列の個数が少ないこと知らなかったら詰むのでは? >>621
何か少なそうという直感は働くけど厳密に考えると箱とボールみたいなのが出てきてしまわない? 脳死で数えるコード書いても少ないのはすぐわかるしな レートの再計算というけど具体的にどうやるんだろう
2400配るんだろうか? 競プロが出来ても仕事は出来ないを社を挙げて証明してるな >>624
考えれば分かるし何なら実験してもわかるけどそれはCに要求して良いものなのか… Cのような単調増加列って何個あるの?
M^N/N!くらい? >>604
よく分からないんだけど、WriterレベルでもABCを難易度順に並べるのって難しいもんなの?
それとも並べる気がないだけ?(確かに難易度順にするとか書いてないけど)
初級者としては得点と難易度が対応してる方が嬉しいのだけど… 上でも言われてるけど、棒とボールをもとに考えると (N+M-1) C M くらいのはず >>631
橙レベルだと問題を難易度順に並べるのはかなり難しいと思う
大まかに難易度順にするのはできるけど何回かに一回は逆転させてしまう気がする
赤以上はわからん 政治家が庶民の生活感覚解らないのと同じで
writer陣は最低でも橙だから初心者の感覚は全く解らないから仕方ない 影響少ないってわかった上で今回でrateあがる人もunratedにするのは
ただの嫌がらせじゃないのか? AとBとかも両方簡単すぎるから難易度じゃなくてforとかwhile使う使わないで分けてるって話だし >>632
そうでした…高校数学の典型問題忘れてた 一見計算量が間に合わないように見えるが低難度なので実は通るみたいなのはよくある メタ読みも実戦的には微妙だしいっそ点数均一で問題名のアルファベット順とかでソートして出してもそこまで崩壊しないと思うんだよね この前誰かが置く場所を決めるのはwriterではないって言ってた気がする >>634-636
そういうこと?
強い人はその辺の感覚もあると思ってたからちょっと意外 >>644
ぶっちゃけ相関はかなり小さめだと思う
レート高くてこのへんの感覚がぜんぜんない人もいるしちゃんと合わせられる人もいる印象 >>645
そんなもんですか…
まぁ解説も強い人がちゃんと出来るわけではないみたいだし納得 とりあえず次スレ立てるときにはスレタイを競プロアンチスレなりatcoderアンチスレなりに変えるの忘れないようにしてくれ 最終チェック一人増やすからで許される世界
次またやらかしても最終チェック一人増やすんやぞw副社長あたりか?w
こんな痰壷から生み出されるうんコーダーに
ろくな奴はいないわなww みんな競プロの、ましてやAtCoderの、またましてや1コンテストにどれだけ重き置いてんだ… テスター1: AC確認しかしてないけど最終チェッカーいるしヨシ!
最終チェッカー: テスターがACしてるし大丈夫、ヨシ!
Clar: 制約違反のテストケースが入っていませんか? なんか荒らされてて草
自己顕示欲が肥大した人間は大変ね 荒らし(あらし、Troll)とは、物事の順列を無作為に乱すことで、奪うことを指す語。
またそのような行為に及ぶ物。特にチャットや電子掲示板、ブログ、ウィキなどの、不特定多数の人間が参加する形態のコンピュータネットワーク上のリソースに対して、不合理なメッセージの送信や妨害行為を継続的に行っている様子を表す。
俺はCD30分で解けてEで撃沈したから今回の配点はどうでもいいんだけど
これだけAC数の差ができてる時点で見極め甘いしまともなコンテストにはなってない気がする
あと個人的にはatcoderはこどふぉより数学系の問題が多くて嫌いなんだけどchokudaiのツイートとか見ると勘違いしてる感ある
ライターが頭でっかちというか、応用が苦手なのかなぁという気もする こどふぉが日本語訳あってかつフルフィードバックだったらそれが一番かも、、
と思うけど結局、ハックでテストケースの品質保ってるところあるからまぁなんとも言えんか 東大入ってから競プロ始めた人は大体(他大の)同年代に手軽に勝てる所にのめり込んだ自己顕示欲モンスターだから・・・ 気に入らない書き込みを代わりに叩いてもらって満足したこるとんくんはちょっと申し訳なさそうにしながらツイートを消して何も無かったことにしたのであった
久々のwriter、楽しそうでなにより 社長自らチェックするの?
人材不足過ぎて不安になるんだが…
来年にはAtCoder無くなってたりしない? 企業コンで今回みたいにプチ荒れして企業側から距離置かれる、とかは近いうちにありそう Bはもう少し難しくしてもよくないか?
灰〜茶くらいの間であまりに差がつかなすぎる 開始が10分遅れた原因になった問題も、E問題だったのかな。 灰diffで差を付けるのは難しそうだけど、せめて順序逆転するのはやめてほしいなー
正しく実力も計れないのに検定とか信ぴょう性ないでしょ 難易度順に並んでないのはあきらめたほうがいい
全問目を通して順位表をチェックしつつ解け 出題された問題に回答する形式の検定だと難易度にバラツキがでるのはある程度仕方ないし、検定なんてそんなもんと思った方が良いと思うよ
程度の差はあるだろうけど GCJやった後だと数学要素強すぎると感じるけど、Cは良かったと思うな >>665
それ救われるべき層とか救いたい層の話じゃなくて実際に救われてる層の話だから問題の傾向と関係なくね? リトコとか数式でてこないし、いかにもプログラミング面接ででてきそうな問題ばかりだよな。
(問題パクってるだけみたいだが 昨日のC問できなかった数弱底辺の発想です。
コンテスト中
・全探?→10**10?実際半分くらいとしてもアカンやろ
・ではDPか?→実装想像もつかん
解説を見た後
・ボール???一瞬別問の解説かと思った。
・重複組合せのMとNの使い方が普通と逆じゃないのか?
・組合せ数10**10よりかなり少なくて全探余裕
M種類からN個取る重複組合せだと気付けなくて、やるだけの全探をやれなかった。 今回の件は外から見えてる以上にやばいよ
writerに作問フローが共有されてなかった結果、作問工程で地雷が埋まってて、テスト工程が終わったあとでそれが炸裂してデグレった SIerとかから管理だけ出来るおじさんとか連れてくればいいんじゃないの(適当) レートそれなりに高くてC解けなかった勢は多分その発想な気がする。
全探索はすぐ思い浮かぶが計算量的に無理だなあってなった。 ABCのCD位の数学問、全員数A極めてる前提で出してるだろ 数Aくらいできた方が良いよ。
業務における開発に不要と思ってるかもしれないけど、おそらく、役に立つことに気付けていないだけ。 逆に高校数学すら出来ないのに競プロやってる奴いるのかよ
ウケる 過去問やれって話だけどな
Cの重複組合せパートは過去問にあるし
普段より難しめではあるが Dも数学かも知らんが、けんちょんさんがやってたみたく試行錯誤で周期があるのに気付けば楽勝ではある まぁ無償で勉強させてもらってるからatcoderがサービス終了するのは困る
>>673
そうそう、それが言いたかった
実際にコーディングインタビューするときはリードコードのやつが出易い訳で、数学の地頭とかよりデータモデルとアルゴリズムなのでは?とは思う 学術の巨大掲示板群 - アルファ・ラボ
ttp://x0000.net
数学 物理学 化学 生物学 天文学 地理地学
IT 電子 工学 言語学 国語 方言 など
PS 連続と離散を統一した!
ttp://x0000.net/topic.aspx?id=3709-0 手元の青チャート数学I+Aより(Focus Goldにも同じようなのあった)
次の条件を満たす整数の組の個数を求めよ
1<=a1<=a2<=a3<=a4<=a5<=5 PASTはこの先どうするんだろうね
ずいぶん参加者も減っちゃったのにすぐに次か
とにかく累計参加者数を増やしたいんだろうけど、てこ入れが必要じゃないか? なんでこんな短期間の間に開くんだろうか。
一ヶ月程度ではスキルアップしていないし今回はパスかなあ PASTは年4回じゃなかったっけ
こういうのは時期を決めちゃったほうがいいのに それっぽい範囲で全探索すれば通るからなあ
意図が分からん Dの解説読んだけど本当に何がしたいのか分からない. Dは例によって中学高校の数学の先生に関心を持ってもらうためで、プログラミングをダシにしてるだけ
プログラミングっぽい解き方は、ニュートン法でしょう 制約的に片方固定してもう片方を二分探索やらニュートン法で見つけるって手法無理じゃない? >>700
なので、プログラミングの本筋からは相当外れているかと C問題誤読して1度UnionFindした人手をあげましょう >>702
めっちゃわかる。
はあCからUF!? と思って問題文読み直した。 >>700
無理でもないでしょ
5乗根が整数になるのかを判定できればいいだけだし
でも結局オーバーフローやら浮動小数点誤差を考えようと思ったらある程度範囲は絞りたいし、そうしたら全探索で十分なこともわかるんだよな Dの入力値Xを10億にするとA,Bが見つからないんだけどなんか問題読み間違ってる? 与えられる X に対して、条件を満たす整数の組 (A,B) が存在することが保証されています。 いやACしてるコードコピペして入力値を10億にして実行するとアウトプット何もされないから何か読み間違えたのかと思って (A, B)が存在しないやつがあって、そういうXは入力されない >>708
紛らわしいけど、ペアが存在しないようなXは与えられないということ 10^9以下のすべての自然数に解があるとは言ってない n^5 = 0, +-1, +-32, +-243, +-1024, ... だぞ
X=1,X=2は作れるがX=3はもう作りようがない マジか理解したありがとう
10分で解けてたのに10億の解が無いから無限にバグ探ししてた(T_T) 通らないときに参考にするプログラムを見るために、分かりやすいプログラム書いてる人って誰がいる?
C++で FAに近いコードでテンプレ最小限なコードはだいたい読みやすいんでないか Dは解が存在しない時は、”No”を出力せよ。
とかでも良かったんじゃないか。
提出コード、解ありきで書いてるの気持ち悪かったわ。 数学回はプログラミング部分つまんないからもっと数学回減らして欲しい
TLで実装を勉強してた層が始めたばかりの数学得意勢以下のパフォになって
ものすごく落ち込んでるのを見ると不憫すぎる…
今回Eまで全部中学数学でforループで実装部分で考えることないから数学早解きコンテストになってるし
前回のCで全体的に数学ばかりで実装がボロッボロな傾向が分かってるんだからもっと実装回増やして レートが下がって色が変わったことを、どうTwitterに呟けばいいかわからないです
どう報告すればいいでしょうか
こういうとき、気軽に冗談にできる人が羨ましいです Eの条件式まで分かってたのに出来なかったよ…悔しいね Fは(考察できない場合)DP復元の実装問題だっただろうが Eはなんか前処理するんだろうなぁと思って図を描いたら一瞬だった って聞いてからDP解法がわかった
確かにAの値はmin(A, 3)まで減らせるから、状態数大幅に減らせるね 入水にします
本音では>>726みたいに発言したいんですけど、真面目キャラで通っているので無理そうです
皆さん回答ありがとうございました D 俺も問題文誤読したわ
Eみたいな謎のフレーバーテキストは嫌いではない
英語で出されたらキレそうだけど Eの推定値R1000って、このEまで通せてようやく雑魚コーダー卒業という世界なのか・・・ >>734
意味が分かりません
>>729のレス見て隠す努力してるってわからないの? まず大前提として、なぜレートの上下をTwitterで呟く必要があるの? Eは考察一個っちゃあそうなんじゃない?
でも去年までだったら水diffだと思うなぁ
レートもdiffも相対的でしかないから、特に今年から海外勢も増えて参加者爆増してるのでどんどんお前らのレートは下がるぞ(予言) それより164のD. Multiple of 2019が水下限なのが不思議すぎる
体感青↑なのだが…解説見直してもよくわからんし ちゃんと解説放送見て過去問覚えている人に取ってはコピペするだけだったな。 別に解説すら読んでなくても検索で一発だった
最近類題検索ゲーの傾向ある ・164のD. Multiple of 2019
に似てるのが
・A - Zero-Sum Ranges
っていう話をしている? ABC158-E Divisible Substringでしょ 最近ので検索ゲーというとEnclose All、Pairsあたり思い浮かぶな
後者は検索で解法知っても実装がなかなかに面倒なうえ400点なんだけども F何が難しいのか分からなかった
俺もそうだけど何も考えずに貪欲に場合分けして投げたら通ったって人多そう 今回のFって青底辺diffだから普段のFに比べたら簡単だったんじゃないの? Fだし、そんな単純じゃねえよなあ と思い込んでしまうのはある。 >>718
もうネタ切れ気味なんで今後は量産できそうな数学問が増えると思う
あと問題文を(無駄に)複雑にするとか パソコン甲子園、何故解説を公開しない?
作る時間はたっぷりあるよね
参加者のことを何だと思ってるのかな? 日曜ABC
AGCは5/23?
ARCは5/30にNOMURA(確定)、その次は6/13?
らしい 質問して帰って来たら嬉しいぐらいのつもりなのだが
AOJ 2199: 差分パルス符号変調 のdpの持ち方について
dp[i][出力値0-255]=i回目に出力値を出すための最小コスト が正しいやり方のようなのだけど
dp[i][i回目に選んだコード]=pair<i回目に出力された値(*i+1回目の遷移のために保持), その時点の最小コスト> でやって、うまくいかない理由ってなんでだろう
手計算でやる限りうまくいくし、テストケースも半分くらいは合っているのだが… ↑自己レス
n=2で貪欲だと落ちるケースでもこのdpでうまくいったんだけど、結局このやり方だとi=>i+1の短期で見た時の最善は取れるが(一手先読みの貪欲みたいな?)
nが大きい時だとうまくいかない、みたいな感じなのかな 問題文も主張するDPも雑に読んだ認識ですまんが
> dp[i][i回目に選んだコード]=pair<i回目に出力された値(*i+1回目の遷移のために保持), その時点の最小コスト>
i回目に出力される値ってのが一意に定まらなくないか
ハックとまではいかないが
2 3
6
8
1
135
136
で最後に1選んだ最適値での出力候補は2通りあるように見える ええと、それぞれ遷移の時に前回の各Miの {出力値/トータルの2乗の差} を見ながら、最適な(2乗の差が最小になるような)遷移を見つけてる感じ
たとえば、↑のケースで遷移表を作ると、左から j=0, 1, 2(6, 8, 1) で
i=0, 128/0 128/0 128/0
i=1, 134/1 136/1 129/36
i=2, 140/17 142/37 135/2
になるので、i=2,j=2の時の 135/2 から、2が答えになるはずなんだけど。。 i = 2, c = 1 で137 / 2 が入る可能性 実装によってはハックにならんが
3 4
6
8
1
50
135
136
187 (or 185)
の両方で正しく答えが出せるかという
最後の遷移は135, 137 両方知ってないと最適値に動けないはず ああ、なるほど。。一意にならないってのは、そういうことか
確かにこれでn=3で次が150とかだったら、当然135より137の方が最適だもんね
そうすると、単純にdpとして持たせる情報量が足りず、最適な遷移を実現できない、って感じか
dp難しいなぁ。。
ありがとう! >>759 もありがとう
各iの遷移はたかだかM*Mだからこれでいけるやろと脳死で考えたのがまずかった 最近ARCAGCがあまりに少ないせいで黄色が爆増してるんだな
これがコドフォだとDiv1が十分な回数あるから紫前後をひたすら往復する人になるんだなー
>>761
どうぞ >>763
ありがとうございます
AtCodeに挑戦したい競プロ初心者です
競技のルールについて教えて下さい
回答を提出する時、ローカル環境で動作確認してから提出してもいいのでしょうか? >>764
いいよ
むしろネットでしたらコピペする時間無駄だし 実態は競技数学・パズルなのに競技プログラミング名乗るの詐欺っぽいな 競技のルールを公式サイトを読んで全く理解できていない人は参加禁止。 海外勢含め新規層が沢山増えているときにAGCARCが開催されていないから全員初期レート800計算なの恐ろしい。 AGC043 黄->青:17 黄<-青:21
hitachi 黄->青:30 黄<-青:5
keyence 黄->青:8 黄<-青:15
dwacon6 黄->青:11 黄<-青:7
AGC041 黄->青:19 黄<-青:17
ARC/AGCをやっても思ったより黄色は減らないね AtCoder,本質が数え上げの問題が多すぎる
もう少し実装重視の問題を増やして欲しい >>773
自動でテストしてくれるツールとかもあるから調べたらいいかもね >>771
数え上げガイジな問題が続くとイライラする もう自分の年も数えられなくなってるからそういう問題は辛いわ 数え上げのなにが嫌いなの?DPと二項係数に分けられると思うんだけどどっちが嫌いなの PAST無償でどれくらい結果の分布が変わるか気になる
8800円だと5時間集中力が持つ自信がない人は受けないだろうし 参加者が増えると期間中にうっかりネタバラシする人が現れる可能性が増えそうで心配 二項係数に帰着する系の問題って受験数学そのものって感じがして個人的には嫌い.
俺は競技受験数学がしたいわけじゃない 日立コンって難易度傾斜が以上だった回じゃなかった?
確か灰-灰-黄 とかだった あーThREEが解けなかった黄ボーダーが割と落ちた感じか
たしかにありそう 受験数学レベルのものは面白くないけどそれ超えると結構面白いけどな 競技線形代数と競技解析のコンテスト開けば大学から仕事貰えるんじゃないかな 回答が記述式だったら採点が面倒
コンテスト開催なんて超困難 けんちょんさん、解説記事にはお世話になったことがあるし教育的な視点を持ってて尊敬してたけど
「そっちの頭が悪い」旨の発言が見えて、やっぱり一定より下のレベルはそういう扱いなんだな(それはそう)
ちょうど再帰の記事に質問しようと思ってたんだけど(「分かりにくい事があれば遠慮なく」とあったので)
上のような反応されると思うと質問できなくなってしまった 再帰の記事は対象レベル低めだから何を質問しても大丈夫そう けんちょんさんは競技プログラミングを教える仕事を目指せばいいんじゃないの
それなら自分の競プロ力も上げやすそうだし あの情報量の少ないツイートから勝手な想像でよく色々語れるな なんか頭の悪さというより理解を諦めたような姿勢にイライラしたんじゃないかなあと推察 めちゃくちゃ丁寧な解説書いて, 分かりにくいって酷評されたらイラッともするでしょ 正直理解できない記事も多いけど, 水色くらいになったら分かるのかなぁと思って諦めてる
ヒで下手な発言して叩かれるのも嫌だし あの人競プロ能力は高いけど説明能力は普通だと思ってるんだけど世間的には評価逆なのな Qiita銀冠級だか金冠級とか言ってたから自信あるんだろう ところで区間dpとbitDPって水色になるのに必要?
E8なんとかかんとか君の記事で出てきたのだが、解説記事もいい感じのが見つからないしやるべきか悩んでいる
それより緑diff埋めて底上げと水diffチャレンジで上限アップしたほうが適切かな、という気がするのだが けんちょんさん好きなのであれだけど、解説やらを書いたうえで、わからんのはお前の頭が悪いからだろって言うのは流石にないと思ってしまった 一部からもてはやされれば良いわけで、良いんじゃないの >>789
Twitterじゃとても言えないから許してほしい
あと元レスにも書いたけど参考にさせてもらった記事もあるし感謝は凄くしてます
>>790
そうなのかな?対象レベルが明示されてたらよかったけど 「頭が悪い」はかなり強い言葉なので自分以外に使うときは気をつけようねという話 >>798
水目指す段階ならまだいらなそう
青目指すなら流石に知識として欲しいけど
bitDPのGet Everythingが水diffだし区間DPのEDPC-Nも水〜青diffになりそうな難易度してるしな >>796
一般的かはともかく競プロerの中では高い方じゃないかな?>説明能力
フォロワーからは肯定的な意見しか来ないだろうから本人は完璧と思ってる節はあるけど
(だから今回みたいな言葉が出てくるんだろうし) ツイート通りだとしたら「説明が天才向けで難しくてわからん」と言われたわけだけど、わかりやすく書いたものに対して「自分には難しかった」ではなく「天才向け」とか言われたら自分ならイラつく自信がある。 人によって地雷なワードである天才って言葉が軽々しく使われやすい界隈なのが問題なのかも
「天才以外お断りパズルコンテスト」とか多くの人を不幸にする呼び方だと思う >>803
ありがとう
精選100問をやってたんだけどそれらの問題はもうしばらく置いとくことにします 同じことはAtCoderの解説にも言えそうだな、こっちのが十分難解なことが多い あの人初心者向けの記事も書いてるし言ってることは正しいんだけど言い方の問題でしょ 日が昇るとファンネル達が来てその後ツイ消しが行われます ・けんちょんさん
わかりやすい
書き間違いも少ないし、かなり時間かけて丁寧に書いてると思う
読んでわからないなら「まだ早い」のでしょう
・○色になるのに○は必要?
強い人ほど「どうせ必要になるんだから学ぶ」と言ってるのを見かける >>818
典型的なオタクでドュフドュフ笑いながら早口でキモい >>817
初心者向けの記事読んでるんだけど、理解させるために書かせてるというより、ある程度理解してる人がそうだよねって感じで確認できるぐらいのレベルに思えて、初心者は無理
まだやり始めた人達のブログがかなり分かりやすい そういう風に口に出すような人の記事や本は絶対に触れたくないな
後々面倒な事に巻き込まれるだけ >>821
わかりやすいっていうのはあなたの感想だよね
そう思わない人も結構いるって話
それらの人に対して後付けで「頭が悪い」とか「まだ早い」とか言うなら
最初から初心者向けって看板は外した方が良いと思う いや本人が書いてる本は初心者向けではないらしいし
やっぱ荒れるから赤未満の雑魚の話はやめよう 「説明が天才向けで難しくてわからん」に対して「いや流石にそっちの頭が悪い」はちょっと・・・ パソコン甲子園、何故解説を公開しない?
作る時間は十分にあるよね?
参加者のことを何だと思ってるんだろうね? 甲子園は球児のためにあるのではなく主催者収入のたまにあるのだ >>798
難しい内容じゃないし
知ったら面白いから勉強して当然 >>833
解説の頭にそう書いとけよ
まぁ書いてあろうが見たかったら勝手に見るけど めちゃくちゃ分かる
競プロ強い人, 発達障害みたいな人も少なくなくて幼稚園児並の稚拙な内輪ネタで
キャッキャしてて本当気持ち悪い.
そんなのは全体から見ればほんの一部なんだろうけど,
ネットだとそういうのが悪目立ちするから嫌でも目につく ノリが合わんと思ったらはずしとけ
場合によっちゃブロックでもいい >>836
頭が悪い奴は書いても見ないか理解しない 計算量の表記として O(10000) みたいなのを使う人結構いるけど,
間違えだと分かってるけど分かりやすいから使ってるのか,
間違えだと知らないのかどっちなんだ Pythonでコドフォの問題解いてたら、N=500であからさまにO(N^3)のDPしかなさそうな問題が出てきたのでどうせTLEしそうだなあ…と他の問題解いて、
終わってから解説見てそのまま実装したら普通に通った
今のPyPyは500^3通せるのか >>844
表記としては間違いじゃないだろ
意図した内容を表せてはいないが >>788
わかる。というか強いひとって絶対どこかで見下してると思うの。だからこっちで歯食いしばって学ぶしかない。俺もそうしてる。 >>849
こういう反応ってネタならいいんだけどガチで言ってる奴はマジで要らん 否定だけして理由言わないやつが一番いらん
そうじゃなくてもペテン野郎だらけなのに区別つかん オーダー記法もわからないのは流石にそっちの頭が悪い >>830
いつまで同じことを繰り返してるんだ?
解説なんか無くても自力で学習して解けるようになるだけの十分な時間はあっただろうに、これまで何をしていたんだ? 参加者のことを 何 だ と 思 っ て る んだろうね やっぱコドフォはバチャに限るな
GWでバチャ5本くらい走ったわ まず競プロは健常者の競技じゃないでしょ(笑)
パラリンピックみたいなもの けんちょんさんって平日土日の四六時中つぶやいてるから大学生かと思ってた 社長も副社長見習ってTwitterやめるべきじゃないか? ARC/AGC 少ないのってwriterに逃げられただけなんじゃ 社長のツイートみて気付いたけど日本最強でも10位なんだね
上位30人の中にも日本人4人しかいないし、日本てもっと強いのかと思ってた 人口比でいえば健闘してる方なのではないか
コドフォは5位に日本人いるし… chokudai、さすがブログでtwitterマーケやってるとかドヤってただけあるね
炎上芸人に向かって大切なユーザーの個人情報送りつけるとか、さぞかし効果的なマーケティング手法なんだろうなぁ
天才の考えるアルゴリズムはすげーや 何の話かと思ったらツイ消ししてんのか
それっぽいリプライツリーは見つけたけど ハンドルネームでやってるやつばっかりなんだから本名公開で荒れるのは容易に想定できるだろ >>881
例の自称元競プロランカーの元特任教授が、松尾豊をpython書けないディス(通常運転)
↓
怪しげなユーザーがatcoderのユーザーリンク貼ってこいつが松尾豊という噂がある、とか言い出す
↓
chokudaiが突撃して、そのユーザーの本名所属年齢を送りつけて否定する
↓
社長直々の晒し行為により本名割れてる上位陣が荒れる
こんな感じ
大澤の話題に絡んでる時点でセンスないし、社長直々で個人情報の濫用するなんて恐れ入る
最強最速アルゴリズマーにしか理解できないマーケ手法なんだろうなw やっぱり理系特化で文系が弱いとそういうことが起きがちなのか… 日本最強をFAKEと同一人物と言われて癪なのはわかるけど、、、 企業コン、PAST、jobsなどでAtCoder社に個人情報紐付けしたことがある奴は、悪用されて悪徳業者に送りつけられ可能性があるということだな
ところで次回のPASTは無料らしいよ >>888
もう登録しちゃったけどただより怖いものは無いかもしれないね… >>884
chokudai以外の単語が全く分からんが
取り合えずPAST登録すんのは止めるわ 青木くんがツイ禁したんだから高橋くんもツイ禁すればいいのに
炎上ツイートで人口増やす前にABCを毎回まともに開けるようにしろって すぬけは「俺はレート高い」とか「俺はユーザー数5桁のサービスを提供してる」みたいな変なプライドが見えてこなくてすき adminやめたり社との距離を感じるのでやめるのでは chokudai おじさん結構長いことインターネットやってるはずなのに,
なんでこうもバランス感覚悪いのかな?
もしかして馬鹿なの? SIerとかからコンプライアンスだけわかるおじさんでも連れてきたら? マーケティングがどうこう言ってるchokudaiなんかにとっては違うのかもしれないけど基本的に関わりたくない相手
向こうが公開情報を元に辿り着いてしまったらそれは仕方ない
わざわざ外野の雑談に首突っ込んで強制的に接点持たせるようなことされるともうAtCoderとソーシャルディスタンス取らなきゃいけなくなる atcoder大好きな気持ちも分からないではないけど、大澤相手に個人情報送りつけるのは流石に擁護不能
なんか炎上の仕方もどんどんひどくなってくな
そのうち取り返しのつかないことやらかしそ ARC以上開かれないの、本当に強い人に逃げられてるからな気がしてきたな
先が無さすぎる AGCはともかくARCすら開けないってのはそういうことなんだろうね AGCより炎上が増えてそういうことなんだろうと思ってる 最年少准教と絡むのは最悪手
大学から禁忌とされてる プロマーケはやることがさすが
認知度上がるんだろうな 多くの人は、「余計なことを言わないのが正解」と考えがちで、減点法で評価しがちですが、広報活動などでTwitterをする場合、どこで加点するか、というのを考えなければ、何も生み出さずに終わってしまいます。
どういうツイートをしたら、どういう加点があって、どういうリスクがあるか、というのは、広報活動でTwitterをする上で、めちゃめちゃ大切です。
面白いツイートを楽しく続けた上で、いろんな人を巻き込んでいくのが、Twitterの良い使い方だと個人的には思っています。
↓
最年少教授に個人情報送りつける
天才かな?
こんなんでもまだ社に協力しようっていう上位陣はほんとに聖人だよ 報酬の良さで日本の上位学生を囲うことに成功したとか聞いたことあるがとうとう逃げられたのか? お前らそんなに社の人間嫌いなのになんでatcoder続けてんの? 使ってるサービスの会社の人間なんかいちいち気にしなくない? その社の人間が嫌いなだけでサービス拒否してたら携帯とか一生使えないだろ chokudaiが時々文句言ってるユーザにうちのサービス使うなって言い放つからファンネルは勘違いしてるかもしれんが
誰でも登録出来るサービスってのは(社の人間に対する)思想とか関係なしに使ってええもんなんやで ICPC国内、ぜひ今年中にやって欲しいなー、
東大でどのチームがアジアに進出するか、凄く興味がある 結局世界に行けるのは1チームでそこはもうおなじみの人たちだろうからどうでもよくね こどふぉに Div4 とか言うのが爆誕してる.
最近参加者めっちゃ増えてて, 灰・緑が過半数になってるから,
灰・緑だけが rated のコンテストを作ったんだとか
Div2にもレート下限設ける流れになるのかな?
https://codeforces.com/blog/entry/77028 最近Pythonではじめて、ABCののBくらいまでなら解けるようになったくらいなんだけど、次は何やるのが良いんだろうか
C解きはじめれば良い? やりたきゃやれば?
Bまでなんて基本的な構文覚えてる以上の意味はない
まだ競プロ始めたってレベルでもないからここで聞いても仕方ない >>929
単純にC解くよりもAtcoder Problem見て茶diff解くといいよ >>895
birds of a feather flock together
ドイツとイタリアでもこんな感じのprob見たが忘れた
別に日本のことわざがすごいってわけじゃない人類共通する糞っぷりを言い表した至言なんだろう(´・ω・`) >>928
これ出ようと思ったけど2回以上参加経験ないとダメなんだな
2回以上前に告知してくれればよかったのに… こどふぉは初期レート1500だよ
unratedで出ればよし 初心者で申し訳ないのですが以下のコードの違いを教えてください…
提出した結果上は正しくて下が間違っているのですが処理の違いがわかりません…
c, x = S.popleft()
delete = min(D-now, x)
now += delete
G[c] += delete
if x > delete:
S.appendleft((c, x-delete))
と
c, x = S.popleft()
if x > D - now:
G[c] += D-now
S.appendleft([C,x-(D-now)])
now += D-now
else:
G[c] += x
now += x
です… 両方普通に使ってるわ
c++だとdeleteがまた別の指すのは知ってるけどもnowはなんかあったっけ >>941
話せば事情は長くなりますが
S.appendleft((c, x-delete))
と
S.appendleft([C,x-(D-now)])
のcの大文字小文字をミスしているのが原因でした
[と(が混ざってるのはこちらのミスです(見づらいコードですね)
こんなのに何時間も時間かけたの本当悲しい… 灰色コーダーにはその2つのコードの動き、同じに見える(´・ω・`) >>946
ここに書かれてないコードの前半部分で別の変数Cに数値を代入しているんですけど、
下の間違ってるコードはそっちの変数を参照していたって感じですね 自己解決したならいいけどコードの一部分だけ見せられても困るだろ そもそもこれC++なのか
appendleftとか知らなかった 最近の過激発言はお金のためか
みんな炎上商法好きだな 胡散臭さが出たな
頭悪い奴らから金巻き上げて馬鹿にするんだろうな 愚直という言葉があまり好きでないため、別の言葉が欲しいです
何かいい言葉はありますか? 頭が悪いと煽り、頭悪い奴が簡単なと罵倒する事で宣伝効果を生み出す教材 てかこの内容でこんなにお金取れるんか、そこら辺で無料でやってそうなもんだが 競プロ商売の話でDEGwerが作問テクニック500円でうってたの思い出した
俺もwriterやってみようかな、まだレート1900だけど >>974
マジでこれ
青色掲げて競プロ家庭教師でもやろうか悩む やってることが駅前のパソコン教室と同じだな
駆け出しエンジニアが情弱相手にビジネスしてるのかと思ったらまさかの人 繋がりはなんかどっちでもよくて、検定の試験対策講座はやるだろうな
あとはオリジナル問題集
今後のやることはパソコン教室と同じ レートでエンジニア適性が測れると言うなら、
企業コンでも数学パズルばっかり出せばいいんじゃないですかね
そうすれば大量に作問できるでしょう? 大学の有志でやってる競プロサークルの講座をようつべに上げればお金になるってマ
俺も金になるならやってみてぇ rustとか伸びそうな言語で解説とサンプルをガンガン書いていったら金出してくれる勢力がおるかも さすがにないと思うけど、今まで見れてた記事を有料化とか続きはコチラでみないなことにはならないよね? 客観的に見て良いところが見つからないのだけど、何かある?人がどうこうではなく、割と本気で高すぎると思うんだが 今まで趣味や無料でやってた人がお金取るようになる動機ガチで知りたい
お金に困ってるんか こんなどうでもいいことにお前らどうして興味津々なの TOEICみたいに公式問題集出したら売れるんじゃね 赤未満の雑魚の話してもしょうがないだろ
怪しげな奴らはブロックして視界から消せばいいだけ >>996
嫉妬してんだろw
自分よりレート低いのにイキリやがって…ってw このスレッドは1000を超えました。
新しいスレッドを立ててください。
life time: 41日 14時間 24分 13秒 5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/
▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php レス数が1000を超えています。これ以上書き込みはできません。