ヘクトのメモ

なんとなくいろいろ書いていくと思います．

渋谷で迷子になった話

この記事はIQ1 Advent Calendar 2019 18日目の記事です.


IQ1 Advent Calendarなので、渋谷で迷子になった話をします??? *1

*1:アドベントカレンダー(物理)の感想でも書こうと思ったけど，ネタの回収に失敗したので今年はお蔵入りです.

続きを読む

NEERC 2006 Problem H. Hard Life

この記事は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
N 頂点， M 辺のグラフが与えられる.
ここで，誘導部分グラフの頂点集合と辺集合をそれぞれ V，E とする.
与えられたグラフの全ての誘導部分グラフのうち， \frac{|E|}{|V|} が最大となる頂点集合 V を1つ求めよ.

*1:hosさんのスライドで初めてこの問題を知りました.http://hos.ac/slides/20150319_flow.pdf

続きを読む

競プロ初心者だった頃の注意すべき点を列挙する 1

背景

ここ最近になって競プロを始めて、毎週プログラミングコンテストに参加する人が増えていると感じます。*1
特に日本語で提供される初心者向けコンテスト AtCoder Beginner Contest (ABC) に参加する人が多いです。各ABCに対して解説pdfと配信動画が公式に用意されていますが、実装で苦戦している人が多いように思えます。
今回の一連の記事では、無意識にやっているようなレベルの実装上のテクニックをあぶりだす為に、自分が競プロを始めた頃の提出コード*2をもとに難所を列挙していきます。ここでの対象読者層は、1問でも解いた人からAtCoder上での緑色くらいまでを想定しています。

以下の記事よりもかなり細かいレベルで書いていきます。
初心者向けのABCの問題傾向とその対策 - ヘクトのメモ

この記事の要約

競プロ初心者かつコンテストパフォーマンスを上げたい人への典型tips集

*1:例えば、5年前は大学のコンピュータサークルに所属している5人くらいだったけど、今では大学の学科で10 -- 20人くらい

*2:AOJ, ARC

続きを読む