e869120 / kyopro_educational_90 Goto Github PK

View Code? Open in Web Editor NEW

794.0 20.0 87.0 52.92 MB

2021/3/30 ～ 2021/7/12 に行われる企画「競プロ典型 90 問」の問題・解説・ソースコードなどの資料をアップロードしています。

C++ 99.43% Python 0.57%

kyopro_educational_90's Introduction

競プロ典型 90 問

日曜を除く毎朝 7:40 に競プロやアルゴリズムの教育的な問題を Twitter（@e869120）に投稿する企画です。

本企画は、2021 年 3 月 30 日から 7 月 11 日まで行われる予定です。

企画の目的

「競プロ典型 90 問」は、競プロ初級者から中上級者（レーティングが 300 から 1999 程度の参加者）を主なターゲットとし、アルゴリズム構築能力を向上させたいという目的で立案されました。

考察ステップだけでなく実装の仕方なども重視するため、サンプルコードはすべての問題でアップロードされる予定です。

出題される問題は教育的な問題や典型問題が多いです。既出があるかもしれませんが、企画の性質上ご容赦くださいませ。この場合は解説に出典を載せておく場合があります。なお、有志コンテストなどの作問者に影響を及ぼさないようにするため、問題は被せないように努力します。もし被ってしまった場合、この問題は典型です。

アルゴリズム本・競プロ本の演習問題のような立ち位置を目指しています。

この github ディレクトリについて

主に以下の 4 点をアップロードします。

出題された問題の画像（/problem）
出題された問題の txt ファイル（/problem-txt、文章の方が見やすい人向け）
問題解説（/editorial）
各問題の入力形式・入力例・出力例（/sample、2021/3/30 追記）
問題の想定ソースコード [C++]（/sol）

なお、各問題には 001 ～ 090 までの番号が付けられており、問題・解説・ソースコードが番号で一対一対応されています。

問題の難易度について

基本的に以下の 7 つの段階にレベル分けされています。

レベル	AtCoder Problems Diff.	備考
★	149 以下	ABC の A, B 問題に相当する難易度です
★★	150 ～ 399	ABC の標準的な C 問題に相当する難易度です
★★★	400 ～ 799
★★★★	800 ～ 1199	ABC の標準的な D 問題に相当する難易度です
★★★★★	1200 ～ 1599	ABC の標準的な E 問題に相当する難易度です
★★★★★★	1600 ～ 1999	これが安定して解ければ上級者です
★★★★★★★	2000 以上	チャレンジ問題ですが、90 問の中でも出題されることがあります

難易度投票について（2021.4.2 追記）

管理者の難易度判定は完璧なものではなく、現状 ± 1 段階程度ずれることがあります。
そこで、皆さんにより正確な難易度を知っていただければと思い、難易度投票スプレッドシートを追加しました。
皆さん投票よろしくお願いします。

「競プロ典型90問」非公式難易度表・ソースコード共有

他言語などのソースコード共有について（2021.5.31 追記）

現在、C++ 以外の言語のソースコードが見られないこと、そして色々な解法や実装を見比べられないことが、重要な課題となっています。
皆さん、AC が出て解説が公開されたら、ソースコードを共有していきましょう。
共有方法については、「ホーム」の下部に書かれていますので、それをご覧ください。

「競プロ典型90問」非公式難易度表・ソースコード共有

テストケースについて（2021.5.31 追記）

解説公開後、テストケースが順次公開されていきます。リンクはこちらです。

「競プロ典型90問」テストケース

問題文やファイルのミスを発見した場合（2021.4.6 追記）

基本的に Pull Request でお願いします。

Merge は管理者の E869120 が行いますが、原則 24 時間以内に対応できます。

その他

この企画について、ご質問やご意見などがございましたら、@e869120 までお問い合わせください。

どうぞよろしくお願い致します。

kyopro_educational_90's People

Contributors

Stargazers

Watchers

Forkers

taketakeyyy ftnext shinkashi cznyx matsutaku wakabame applifun tajima738 soushianzai emthrm caovanbi235 kei-u29 soraiemame matsutakk takutojibiki wtetsu nagoyan55 kemkemg0 mtchaos 2xtvvrscpp harurunrunrun kentaro-kamaishi miyajiro takumi1923 siro53 nekotheshadow mdstoy kato-hiro koichi4970 kenryu42 masutech16 zobio gontititi raise-nccr kota-isayama coolduck777 0kina programmer412 quantumshiro sterben9014 y-tomimoto 7iva kyohei8937 roy030311 xizhe-zhang ikoan08 keru0511 naototazumi syamashi isa-rentacs j-d-0630 sakana32 myzk-a byam hiro-mori999 knknkn1162 superrino130 koboritakumi gcqmkm02 naoyafurudono wds33817 zoioi terakoshitaisuke hogeno gio15153 zerof-dy r3ishida syncrodazt lekangzou daikichiba9511 hykw yurai-kitadate tata10432 haruponponpopon tomota8686 seigot lmdexpr pokopk155 gg-big-org polly9 kazuki1023 ramu13 xiaomitenshi mimihoullier inozo22 unokun 1m-n00b

kyopro_educational_90's Issues

sol/17-3.cpp で変数・コメントのAnswer1,2がeditorialと逆に見えます

典型17の解説とソースコードでAnswer#の割り振りが異なっているように見えました。

解説のAnswer1が下記実装に対応し

	// Step #3. Get Answer2
	long long Answer2 = 0;
	for (int i = 1; i <= M; i++) V3[L[i]] += 1;
	for (int i = 1; i <= M; i++) V3[R[i]] += 1;
	for (int i = 1; i <= N; i++) Answer2 += V3[i] * (V3[i] - 1LL) / 2LL;

解説のAnswer2が下記実装に対応すると思います。

	// Step #2. Get Answer1
	long long Answer1 = 0;
	for (int i = 1; i <= M; i++) V1[R[i]] += 1;
	for (int i = 1; i <= M; i++) V2[L[i] - 1] += 1;
	for (int i = 1; i <= N; i++) V1[i] += V1[i - 1];
	for (int i = 1; i <= N; i++) Answer1 += V1[i] * V2[i];

17-2.cpp も同様だと思います。

ref

cpp
[url]https://github.com/E869120/kyopro_educational_90/blob/main/sol/017-03.cpp

editorial
[url]https://github.com/E869120/kyopro_educational_90/blob/main/editorial/017-02.jpg

問題17：入力用/数え上げ用の配列の大きさが足りない

https://github.com/E869120/kyopro_educational_90/blob/main/sol/017-03.cpp
について、入力用/数え上げ用の配列の大きさが　1 << 18 とされていますが、この値は300000より小さいため小課題3の入力に対応していません。

問題 06 の解説の類題

素晴らしい企画ありがとうございます。

問題 06 の解説にある、類題の２つめ辞書式順序ふたたびの問題番号が間違ってそうです。正しくは ABC009-C と思われます。

https://github.com/E869120/kyopro_educational_90/blob/main/editorial/006.jpg

とても勉強になる企画ありがとうございました。とても楽しめました
https://twitter.com/e869120/status/1411595642493759488 をはじめとした最終週に出した「まとめプリント」はGitHubにはアップロードしないのでしょうか？非常に便利なまとめだったのでGitHubにあると後から見る際に助かります
良ければ検討していただけると嬉しいです。よろしくお願いします

i want to add english version that will it be merged?

060 - Chimera（★5）の解説画像の最長増加部分列の長さの表に誤記?

はじめまして。
非常に素晴らしい教材を作成していただきどうもありがとうございます。大変勉強になっております。

この度は60日目の解説に誤記と思われる点がございましたので、私の勘違いであれば申し訳無いのですが一応ご報告させていただきます。

060 - Chimera（★5）の、解説画像のステップ2の最長増加部分列の長さの表で、i=2, 4, 7の部分に誤記があると思われます。

正しくは下記の表のようになると思います。

i	1	2	3	4	5	6	7	8
Pi	1	1	2	2	3	4	4	4
Qi	2	2	2	2	2	2	1	1

参考までに、i=1-8における数列A = [3 1 4 1 5 9 2 6] と、それを逆転した数列の最長増加部分列は、それぞれ下記のようになりました。(INFは無視して下さい)
[3, INF, INF, INF, INF, INF, INF, INF]
[1, INF, INF, INF, INF, INF, INF, INF]
[1, 4, INF, INF, INF, INF, INF, INF]
[1, 4, INF, INF, INF, INF, INF, INF]
[1, 4, 5, INF, INF, INF, INF, INF]
[1, 4, 5, 9, INF, INF, INF, INF]
[1, 2, 5, 9, INF, INF, INF, INF]
[1, 2, 5, 6, INF, INF, INF, INF]

[6, INF, INF, INF, INF, INF, INF, INF]
[2, INF, INF, INF, INF, INF, INF, INF]
[2, 9, INF, INF, INF, INF, INF, INF]
[2, 5, INF, INF, INF, INF, INF, INF]
[1, 5, INF, INF, INF, INF, INF, INF]
[1, 4, INF, INF, INF, INF, INF, INF]
[1, 4, INF, INF, INF, INF, INF, INF]
[1, 3, INF, INF, INF, INF, INF, INF]

お忙しい中大変恐縮ですが、もしご確認いただければ幸いです。
何卒宜しくお願い致します。

典型068の解説が一部間違っている

https://twitter.com/peroon_cp/status/1409527756132544520

こちらでも指摘したのですが、本にもなるということでもう1度連絡してみます。

典型068にて、問題文では
Ti=0 or 1なのですが、
解説では
Ti=1 or 2となっていて、制約が一致していません。

041 - Piles in AtCoder Farm（★7）凸包の解説に誤り？

凸包の作成の解説において、
(1)「x座標の昇順にソートした上で」
と書かれていますが、正しくは
(2)「(x座標、y座標)の組で昇順にソートした上で」
と思われます。

・サンプルソースは、上記(2)でソートされていることを確認
・サンプルソースではACするが、上記(1)に修正したらWAが出ることを確認
・x軸のみソートするのでは不正解になるテストケースを考案
4
0 0
0 1
0 -1
1 0

解説をもとにPythonで解答を考えている上で、どうしてもWAが消えきらず、考察していて上記が判明しました。

42 の解説

https://github.com/E869120/kyopro_educational_90/blob/main/editorial/042.jpg

解説右側の記述ですが、
誤: 9 の倍数: 各桁の数字の和が 3 の倍数
正: 9 の倍数: 各桁の数字の和が 9 の倍数
だと思います。