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

■ このスレッドは過去ログ倉庫に格納されています
2021/11/20(土) 02:43:43.44
競技プログラミング、オンラインジャッジ、プログラミングコンテストや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/

前スレ
競技プログラミングにハマるプログラマのスレ 74
https://medaka.5ch.net/test/read.cgi/prog/1636865136/
2021/11/24(水) 21:16:47.55
Ruteくんは作文作法の本を読んでくれ
530仕様書無しさん
垢版 |
2021/11/24(水) 21:55:53.42
悪い意味でハマってる
茶色だが解説を見て証明に納得してもそれがどこから思い付いたのかわからん
だが解けた時の楽しさが忘れられずjobsの求人も魅力的だからやめられねえ
531仕様書無しさん
垢版 |
2021/11/24(水) 22:01:31.31
解説から攻略に繋げるコツとかある？
2021/11/24(水) 22:02:52.36
どの問題か言ってみ
533仕様書無しさん
垢版 |
2021/11/24(水) 22:03:19.74
一から発想しようとするのが間違っていて、そういう解き方の典型があるって引き出しを自分の中に一つ増やせばそれでいいんじゃないの
増えた引き出しから必要なものをすぐ引けるようになるには問題数こなして感覚を身につけるしかないと思うけど
2021/11/24(水) 22:11:55.79
ABCの特に青diff以下の問題は全て典型問題です
ここ1年のABCの青diff以下でアドホックな問題ありません
もしあったら指摘ヨロ
535仕様書無しさん
垢版 |
2021/11/24(水) 22:28:01.26
なんか分かったすまん
536仕様書無しさん
垢版 |
2021/11/24(水) 22:28:53.37
ちなみにDPコンのF
2021/11/24(水) 22:30:01.96
A問題が全くわからなかったけどRuteくんの神解説のおかげでスッキリしました
538仕様書無しさん
垢版 |
2021/11/24(水) 22:33:20.65
s[i]==t[j]ならdp[i][j]==dp[i-1][j-1]ってのはすんなりそれはそうだろって分かったんよ
だけどs[i]!=t[j]のときにdp[i][j]==max(dp[i-1][j],dp[i][j-1])っていうのが分からんかった
それの妥当性は分かるし、答えを見れば証明はできるが、どうやって問題からそこに辿り着くのか？っていう話
539仕様書無しさん
垢版 |
2021/11/24(水) 22:41:30.52
ちなみに考え方は
とりあえず答えに影響する部分列だけ分かりやすくABCみたいに書いて可視化したもので示すと
(X)とか(Y)はXが含まれてるかもしれないorYが含まれてるかもしれないっていう意味ね
S=...A...B...C..(Y)..X
T=.A....B..C...(X).....Y
みたいに考えればX!=Y(S[i]!=T[i])のときにdp[i][j]がdp[i-1][j]かdp[i][j-1]であることが直感的に分かるって感じ
540仕様書無しさん
垢版 |
2021/11/24(水) 22:52:02.59
(S[i]!=T[j])だったわ
2021/11/24(水) 23:04:02.71
DPって全探索の効率化だから、元となる全探索アルゴリズムから考えればそうなるよ
542仕様書無しさん
垢版 |
2021/11/24(水) 23:33:29.08
>>541
この問題って元々の愚直全探索からたどってもこの考え方になるのか
しばらく考えてみたけど分からんかった
2021/11/24(水) 23:34:25.31
Ruteくん、報告があるってなんだろ
2021/11/24(水) 23:35:03.62
DPコンのAから解いてるんなら、遷移（探索）だということはわかってると思うんだが、わかってないのか？

二次元配列の中身がどうなるのか書き出して、遷移と照らし合わせてみろ
面倒だけど、最初はそういう泥臭い作業をしないと理解が進まない
545仕様書無しさん
垢版 |
2021/11/24(水) 23:42:07.87
codechef何があった？
2021/11/24(水) 23:43:41.46
ドメイン購入コンテストか
547仕様書無しさん
垢版 |
2021/11/24(水) 23:52:33.22
仕組みがわからないと発想の出所がわからない、は違うだろ
2021/11/24(水) 23:58:30.70
そういうことか
2021/11/25(木) 00:01:02.74
忘年会47歳さんも参戦か
彼がスレ長派につくかどうか見極める必要があるな
2021/11/25(木) 00:06:32.77
R君、競プロの色なんて社会に出たらよくも悪くも誰も気にしないけど、文章力の問題はずっとついて回るから、そっちの方を精進してほしい
2021/11/25(木) 00:15:35.35
発想の出所に関して言えば、ある状態の情報を計算するために近い状態の情報を使うというDPの典型思考そのまんま
DP[i][j]を計算するときに、DP[i-1][j]やDP[i][j-1]などの近場の情報を使ってどうにかしようって考えじゃね
そんな突飛な発想じゃないと思うぞ
2021/11/25(木) 00:29:50.44
忘年会すげー
無料観戦権とかないのか？
553仕様書無しさん
垢版 |
2021/11/25(木) 00:34:49.81
1時間待機したのに延期になってワロタ
2021/11/25(木) 00:36:00.69
理系ならそのうち勝手に文章力はつくんとちゃうか？文系と違って
2021/11/25(木) 00:36:49.09
マルコフ連鎖的とかそういう発想だろうね。
なんかそこまで情報持たなくてよくね？ってな感じだとは思う。
2021/11/25(木) 01:13:13.47
延期って何の話？
557仕様書無しさん
垢版 |
2021/11/25(木) 01:16:52.34
典型っぽいやつは決め打ちで解いてみるってことか
でも最初に斜めを使うのが思い浮かぶDPで縦横を決め打ちで試すの怖いし難しいな
2021/11/25(木) 01:21:49.39
決め打ちなんてしないよ
全く同じ問題なんて出題されないし、そんな考察スキップするようなことしてたらバグだらけになって通らないよ
2021/11/25(木) 01:23:52.24
これは二分探索っぽいな、って解法をある程度決め打ちして、考察を深めていくことならある
560仕様書無しさん
垢版 |
2021/11/25(木) 01:28:32.65
これはDPコンだから最初からDPって分かるけど、これとコンテストで未知のときに遭遇したらDPで行くっていう行為自体がすでに決め打ちだし、その上に決め打ちを重ねるのが怖い
でも証明自体は手際よくやれば3分で済むから袋小路でグルグルするくらいならやったほうが良いな
2021/11/25(木) 01:29:16.91
まず制約の3000を見て3000*3000の二次元配列を取れるなと思う
二次元配列上でS[i]==T[j]の(i,j)に印をつけて、この印の最大数を取るゲームに帰着
562仕様書無しさん
垢版 |
2021/11/25(木) 01:29:24.88
DPの典型思考そのまんまって決め打ちで解くときの話じゃないの？
563仕様書無しさん
垢版 |
2021/11/25(木) 01:30:28.14
それようするに決め打ちじゃね
564仕様書無しさん
垢版 |
2021/11/25(木) 01:31:01.68
559にある程度決め打ちって書いてたわすまん
565仕様書無しさん
垢版 |
2021/11/25(木) 01:32:12.70
まあ自分の決め打ちっていう発言もそういう話を意図してた
2021/11/25(木) 02:49:12.22
再帰で書けそうならかなり捻くれた問題じゃなきゃDPで書けるんじゃないか
567仕様書無しさん
垢版 |
2021/11/25(木) 07:13:56.14
>>556
codechefのコンテスト
2021/11/25(木) 08:45:53.51
Ruteくん
2021/11/25(木) 10:09:12.23
>>567
あざっす
おれも出てみようかな
2021/11/25(木) 11:38:43.72
https://twitter.com/sak_algo/status/1463696057234526208?t=LSXIiO51MZq-tplRCEJfLA&;s=19

最近のABCって赤でも全完できるかどうかって感じだけどアルゴ式の作者ともなると朝飯前なんだな
https://twitter.com/5chan_nel (5ch newer account)
2021/11/25(木) 12:08:05.87
ガイジスレ終了
2021/11/25(木) 12:10:47.07
睡眠不足は脳に重大な影響 「あとで取り戻せる」は嘘｜NIKKEI STYLE
https://style.nikkei.com/article/DGXMZO10215050S6A201C1000000/
　
寝不足はこれだけ頭の働きを悪くする | SLEEP　最高の脳と身体をつくる睡眠の技術 | ダイヤモンド・オンライン　
https://diamond.jp/articles/amp/121720　
2021/11/25(木) 12:11:39.53
やはりABC8問はおかしい
2021/11/25(木) 12:20:21.96
それより夜開催をやめてほし
こちとら朝から仕事してる社会人やぞ
2021/11/25(木) 12:32:39.25
夜以外どこでやるといいの
576仕様書無しさん
垢版 |
2021/11/25(木) 12:33:16.96
こんなガイジの掲示場で見栄はるなよ(´・ω・｀)
2021/11/25(木) 12:35:41.55
お昼すぎのお昼寝どきに開催してほしい
2021/11/25(木) 12:37:13.66
昼だとリア充が困るだろ！
2021/11/25(木) 13:11:32.89
お前ら、文脈わかりにくいから安価つけてほしい
2021/11/25(木) 13:55:03.36
「ARC解けない」と「ABC解けない」は質が違ってて、 橙レベルからしたらABC-Hでさえ知識があればほぼ難問はない
赤コーダーが本番中に解けないのは時間が短い中unratedというモチベが低い状態でマニアッククイズをやらされるから
一回ABCの赤diff解いてみればいいけど、知ってさえいれば青でもすぐ解けそうな虚無問もそこそこある
知識と時間制限のせいでdiffが釣り上がってる問題と難問は区別しような
2021/11/25(木) 14:02:38.08
そこの区別ができない人思ったより多いんだよな
diffの大小しか理解できず問題の質が見えてない
2021/11/25(木) 14:02:58.15
ABC-Aも時間制限30秒とかなら赤diffになったりするの？
2021/11/25(木) 14:09:31.00
Gまでは虚無だし、実質Hの知識パート勉強するだけじゃないか
2021/11/25(木) 14:10:05.49
>>582
理論上はなるんじゃね
2021/11/25(木) 14:21:46.37
ABC-Hの考察パートは簡単な方だと水〜青diffぐらいありそうで、それを虚無というべきかどうか
確かに暖色上位からすれば無に等しいしただの知識ゲーだが、茶とか緑層から見れば難問と区別がつかないだろうな
そもそも考察パートと知識パートに分離できるという話があまり理解できなさそう
2021/11/25(木) 14:29:02.39
虚無
2021/11/25(木) 14:37:13.03
競技プログラミングは役に立たない
http://rio2016.5ch.net/test/read.cgi/informatics/1541745742/
2021/11/25(木) 14:37:47.04
茶緑向けじゃないのは確かなんだけど水青レベルなら十分取り組める内容だと思うから(コンテスト後に勉強するという取り組み方を含めて)、橙diff赤diffをことさらに取り上げてrated層無視だと言わないでほしい
not for youかもしれないけどnot for ratedの問題とは限らないよね
2021/11/25(木) 14:49:02.89
そうなんだ
2021/11/25(木) 14:54:53.40
Hがfor ratedか否かって本当はどうでもよくて、for brown、for green、for cyanの問題が安定的に配置されてないから文句言うやつが発生すると思われる
なかなか難しいんだけどな、出涸らしの問題だとすぐに灰diffになるしちょっと捻るだけで青diff出たりする
2021/11/25(木) 15:01:14.90
そうそう
青以上の人が勉強することで成長につながる問題ってコンセプトは理解できるんだけど、崖を作るぐらいならその枠潰して易問を増やした方がコンテストとして安定感増すんじゃない？って思うんだよな
コンテストである以上コンテスト中の競争をもうちょっと重視してほしい
2021/11/25(木) 15:03:17.96
安定感については、すでにほぼ問題ない、って運営は思ってるからね
2021/11/25(木) 15:05:22.94
コンテスト以外の出題の場所があればいいんだろうけど金が動かなそうだしなぁ。
2021/11/25(木) 15:07:51.45
chokudaiはwriterやadminをdisらずヘイトアピールしてタンクになるのが基本方針だから「問題ないと思う」を連呼するけど、内部的にはそこそこ気にしてるはず
diff投票みたいな仕組みを作ったのはその現れだし
2021/11/25(木) 15:13:11.52
Writerはそこそこ注目されるし、かなりプレッシャーありそうだよな
2021/11/25(木) 15:16:33.15
茶diffとか緑diffみたいな微妙な問題を強い人が作問するの難しいんだよな
茶緑の人に全力で頭ひねって作問してもらえば安定供給できそう
2021/11/25(木) 15:25:41.22
副社長とか丁度いい感じの原案出せるのでは
2021/11/25(木) 15:45:38.42
Codechefに今年から、CodeChef Startersっていうビギナー向けコンテストが追加されたんだけど、こういうのやればいいんじゃね？
599仕様書無しさん
垢版 |
2021/11/25(木) 15:46:08.87
>539名無しさん＠お腹いっぱい。2020/06/14(日) 23:30:27.31ID:uM3QA2DX0
>解説に便乗して半端なレートの奴がC解けないのを煽ってるの笑える
>この民度がAtCoderって感じ

一年前も今も民度同じなの面白いｗ
2021/11/25(木) 15:50:47.25
CodeChef より Codeforces Div.3 のがオススメしたい
Cook-Off と Lunchtime 以外のイメージが未だ悪い
2021/11/25(木) 15:52:53.10
>>590
そこが気になるならまだatcoderじゃなくてもいいんじゃないかな。他にも教育的なサイトあるから、まだatcoderは早いんじゃないかなって思う。エンジョイ勢なら参加どうぞって感じだけど
2021/11/25(木) 15:54:15.16
そうだね
ABCは初心者向けじゃないということだ
2021/11/25(木) 15:58:03.78
実際茶緑水くらいの人はDiv3を楽しめるの？
2021/11/25(木) 16:00:33.25
茶緑水程度じゃ競プロの面白い部分触れなくないか
2021/11/25(木) 16:00:44.48
茶の感覚は知らんが緑水あるなら十分楽しめるはず
2021/11/25(木) 16:00:53.09
副社長のレート帯なら適切なdiff原案出せると思うんだけど対岸の火事みたいだよな。こんなに物議醸し出してるのに我関せずだし。副社長座ってるだけなの？笑
2021/11/25(木) 16:03:41.54
副社長の仕事はコンテスト以外だろ
コンテストに関わって良くなる未来が見えん
2021/11/25(木) 16:07:02.82
>>595
前回のA問題はてんぷらさんだったしQCFIUMさんの名前もたまに見るしABCwriter陣って古参も新人も含めて少なくとも20人以上いそう
2021/11/25(木) 16:08:54.52
Writerっていっぱいいるんだね
2021/11/25(木) 16:09:22.65
>>607
えーだって他に低レートの運営いないんだもんｗ
2021/11/25(木) 16:10:29.26
副社長って何色？ 人権あるの？
2021/11/25(木) 16:22:04.62
色は知らんが人権はあるだろ
613仕様書無しさん
垢版 |
2021/11/25(木) 16:29:05.66
https://atcoder.jp/contests/arc128/tasks/arc128_bみたいな問題は典型か典型じゃないか人によって意見が分かれそう
2021/11/25(木) 17:45:46.48
Ruteくんの配信を見た感じ緑までは競プロ以前の問題だわ
2021/11/25(木) 17:53:07.85
せやな
姿勢をガラッと変えないとレート上げられなそう

おれみたいな青色底辺も、上位から見たら似たような無駄な努力マンに見えるのかなあ・・・
2021/11/25(木) 17:58:55.40
青色に届いたんだから無駄な努力ではないと思う
2021/11/25(木) 18:00:48.30
競プロをどれくらいやりこんでるかによりそう
618仕様書無しさん
垢版 |
2021/11/25(木) 18:01:47.16
茶だけど
ARCはおもろい
ABCはつまらん
上のレートからみたら意外かもしれんが問題の性質を考えると分かってもらえると思う
2021/11/25(木) 18:02:15.51
うにだよ!?
2021/11/25(木) 18:02:46.12
スレ長未満ってことは多分人間のレベルには達してないから、同じように珍奇な存在であることは間違いないと思う
2021/11/25(木) 18:03:30.86
ゴリ！？
2021/11/25(木) 18:04:18.36
数強だったらそうなる人多いから意外でもなんでもない
ARCだけでも十分レートは上がるから、無理してABC出る必要ない
2021/11/25(木) 18:04:21.56
ABCの方が勉強色強いから、勤勉じゃない人的にはARCの方が本来面白いと思う
2021/11/25(木) 18:05:38.20
>>613
問題理解した瞬間にあーはいこれねとはならないが解けたあと振り返ってみると考察の進め方はよくあると感じる
つまりメタ典型
2021/11/25(木) 18:08:29.29
青底辺か
まあ始めてニ、三ヶ月とかなら大体そんなレベルだろ、気にすんな
2021/11/25(木) 18:09:58.35
ARCおもろいならある程度典型身につけたらすぐ伸びそう
2021/11/25(木) 18:12:20.60
ARCおもしろいけどこの前のA問題みたいなやつはおもんない
ABCで出しとけや
2021/11/25(木) 18:23:25.44
この前のAは脳死で桁DPやろうとすると出遅れるタイプの問題
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況