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

Related tags

Artificial Intelligence kyopro_educational_90
Overview

競プロ典型 90 問

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

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


企画の目的

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

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

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

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


この 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 問の中でも出題されることがあります

その他

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

Comments
  • 問題 06 の解説の類題

    問題 06 の解説の類題

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

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

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

    opened by fumuumuf 2
  • 典型068の解説が一部間違っている

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

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

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

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

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

    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

    opened by MoSooN1110 1
  • 037.cppの日本語の文字化けを修正

    037.cppの日本語の文字化けを修正

    いつもお世話になっております。

    037.cppの文字コードがおかしくなっていたようで、GitHub上で見ると文字化けしている問題をShift_JISに変更することで修正しました。ご確認ください。

    (以下の文章はPRには一切関係ないです) 実際に解くのはだいぶ遅れているんですが、問題自体は毎日Twitterで拝見していて楽しみにしています。残りの期間も走り切れるよう応援しています！

    opened by masutech16 0
  • 041 - Piles in AtCoder Farm（★7）凸包の解説に誤り？

    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が消えきらず、考察していて上記が判明しました。

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

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

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

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

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

    正しくは下記の表のようになると思います。
    | 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]

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

    opened by AkihiroSasabe 0
  • まとめプリントはGitHubには貼らないのでしょうか？

    まとめプリントはGitHubには貼らないのでしょうか？

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

    opened by rchaser53 0
Owner
Masataka Yoneda
Competitive Programmer. AtCoder Red (max. 2935) / CodeForces Red (max. 2909) / IOI '18, '19, '20 Gold Medalist / APIO '19, '20 Gold Medalist / AtCoder Writer
Masataka Yoneda
GitHub
CVE-2021-3156非交互式执行命令

CVE-2021-3156 This is a warehouse modification based on @CptGibbon and supports arbitrary command execution. 相关阅读：CVE-2021-3156 - Exploit修改 Root shell

倾旋 188 Nov 15, 2022
PoC for CVE-2021-3156 (sudo heap overflow)

CVE-2021-3156 PoC for CVE-2021-3156 (sudo heap overflow). Exploit by @gf_256 aka cts. Thanks to r4j from super guesser for help. Credit to Braon Samed

Stephen Tong 433 Jan 4, 2023
ICRA 2021 - Robust Place Recognition using an Imaging Lidar

Robust Place Recognition using an Imaging Lidar A place recognition package using high-resolution imaging lidar. For best performance, a lidar equippe

Tixiao Shan 296 Jan 1, 2023
Material for the UIBK Operating Systems Lab (2021)

UIBK Operating Systems Lab 2021 This repository contains material required to complete exercises for the OS lab in the 2021 summer semester, including

null 13 Nov 3, 2022
Investigating the bug behind CVE-2021-26708

vsock_poc Investigating the bug behind CVE-2021-26708 This repo contains a small writeup about CVE-2021-26708, and how this bug can be turned into a U

Jordan 25 Sep 19, 2022
Aulas de Sistemas Operativos da turma LI42D no semestre de verão de 2020/2021

ISEL - Sistemas Operativos LI42D - Verão de 2021 Aulas de Sistemas Operativos da turma LI42D no semestre de verão de 2020/2021 Aulas Remotas em Direct

null 12 May 6, 2022
Official PyTorch Code of GrooMeD-NMS: Grouped Mathematically Differentiable NMS for Monocular 3D Object Detection (CVPR 2021)

GrooMeD-NMS: Grouped Mathematically Differentiable NMS for Monocular 3D Object Detection GrooMeD-NMS: Grouped Mathematically Differentiable NMS for Mo

Abhinav Kumar 76 Jan 2, 2023
Code and Data for our CVPR 2021 paper "Structured Scene Memory for Vision-Language Navigation"

SSM-VLN Code and Data for our CVPR 2021 paper "Structured Scene Memory for Vision-Language Navigation". Environment Installation Download Room-to-Room

hanqing 35 Dec 3, 2022
The official implementation of our CVPR 2021 paper - Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach

Graph Optimizer This repo contains the official implementation of our CVPR 2021 paper - Hybrid Rotation Averaging: A Fast and Robust Rotation Averagin

Chenyu 109 Dec 23, 2022
C++ Implementation of "An Equivariant Filter for Visual Inertial Odometry", ICRA 2021

EqF VIO (Equivariant Filter for Visual Inertial Odometry) This repository contains an implementation of an Equivariant Filter (EqF) for Visual Inertia

null 60 Nov 15, 2022
Offical repo for "Moynihan, M., Ruano, S., Pagés, R. and Smolic, A., 2021. Autonomous Tracking For Volumetric Video Sequences"

MeshTracker A segmentation-based tracking algorithm for registering volumetric video meshes (ply/obj) in C++. This is the official implementation of t

V-Sense 22 Nov 7, 2022
Python and C++ implementation of "MarkerPose: Robust real-time planar target tracking for accurate stereo pose estimation". Accepted at LXCV Workshop @ CVPR 2021.

MarkerPose: Robust Real-time Planar Target Tracking for Accurate Stereo Pose Estimation This is a PyTorch and LibTorch implementation of MarkerPose: a

Jhacson Meza 47 Nov 18, 2022
Repository to keep track of progress; Started learning C on 2nd September 2021.

Repository to keep track of progress. I started learning C on 2nd September 2021. The future: I plan on turning this repository into a tutorial with c

aether 4 Dec 16, 2021
[CVPR 2021] NormalFusion: Real-Time Acquisition of Surface Normals for High-Resolution RGB-D Scanning

NormalFusion: Real-Time Acquisition of Surface Normals for High-Resolution RGB-D Scanning Project Page | Paper | Supplemental material #1 | Supplement

KAIST VCLAB 50 Jan 2, 2023
The code for C programming 2021, Department of Computer Science, National Taiwan University.

C2021 .c for sousce code, .in for input file, and .out for correct output. The numbers are the problem indices in the judge system. "make number" to m

Pangfeng Liu 6 Jan 10, 2022
Mixed reality VR laser tag using Oculus Quest 2 and OAK-D depth cameras. First prize winner for North America region in OpenCV AI Competition 2021.

Mixed Reality Laser Tag Copyright 2021 Bart Trzynadlowski Overview This is the source code to my Mixed Reality Laser Tag project, which won first priz

null 34 Jun 3, 2022
Real-time Skeletonization for Sketch-based Modeling (SMI:2021)

Real-time Skeletonization for Sketch-based Modeling (SMI:2021) Demo We provide an executable software under directory "demo_exe/". Tested Environment

null 247 Dec 21, 2022
Real-Time Neural 3D Hand Pose Estimation from an Event Stream [ICCV 2021]

EventHands: Real-Time Neural 3D Hand Pose Estimation from an Event Stream Project Page Index TRAIN.md -- how to train the model from scratch EVAL_REAL

null 23 Nov 7, 2022
2018-2021 mimuw by marcin abramowicz

MIM UW by Marcin Abramowicz bierzcie i kopiujcie z tego wszyscy; to sa bowiem kody moje; ktore za was zostaly napisane. [...] bierzcie i edukujcie sie

Marcin Abramowicz 21 Dec 15, 2022