はじめに
IPA のデータベーススペシャリスト試験を受験して合格しました。5年ぶりにペーパーテストを受けたら苦労したので、記事に残そうと思います。*1
この記事はIQ1 Advent Calendar 2019 18日目の記事です.
合コンのために渋谷に来たけど、派手に迷子になって辛い......
— ヘクト🐬 (@osrehun) 2019年11月19日
*1:アドベントカレンダー(物理)の感想でも書こうと思ったけど,ネタの回収に失敗したので今年はお蔵入りです.
この記事はCompetitive Programming (2) Advent Calendar 18日目の記事です.
あまり紹介されていない高度典型問題の解説を書きます.*1
(追記: 12/18) https://codeforces.com/gym/100287/attachments/download/2012/20062007-acmicpc-northeastern-european-regional-contest-neerc-06-en.pdf
頂点,
辺のグラフが与えられる.
ここで,誘導部分グラフの頂点集合と辺集合をそれぞれ とする.
与えられたグラフの全ての誘導部分グラフのうち, が最大となる頂点集合
を1つ求めよ.
*1:hosさんのスライドで初めてこの問題を知りました.http://hos.ac/slides/20150319_flow.pdf
ここ最近になって競プロを始めて、毎週プログラミングコンテストに参加する人が増えていると感じます。*1
特に日本語で提供される初心者向けコンテスト AtCoder Beginner Contest (ABC) に参加する人が多いです。各ABCに対して解説pdfと配信動画が公式に用意されていますが、実装で苦戦している人が多いように思えます。
今回の一連の記事では、無意識にやっているようなレベルの実装上のテクニックをあぶりだす為に、自分が競プロを始めた頃の提出コード*2をもとに難所を列挙していきます。ここでの対象読者層は、1問でも解いた人からAtCoder上での緑色くらいまでを想定しています。
以下の記事よりもかなり細かいレベルで書いていきます。
初心者向けのABCの問題傾向とその対策 - ヘクトのメモ
競プロ初心者かつコンテストパフォーマンスを上げたい人への典型tips集