読者です 読者をやめる 読者になる 読者になる

凸包の頂点数の話

まとめ のグリッドに収まる格子点を頂点とする凸多角形の頂点数は。 詳しい話は論文を読んでください。 On the maximal number of edges of convex digital polygons included into an m × m-grid はじめに 凸包を取ると考慮すべき点の数が減って嬉しい、と…

ナップサック問題でマラソンマッチ入門

マラソンマッチって? 競技プログラミングのうち、「より良い解を求める」ことを競うコンテストをマラソン形式と呼びます。 例えば厳密解を求めることができない問題について、近似解のスコアを競ったりします。 マラソンでよく使われるアルゴリズム マラソ…

短縮王「割り算と足し算」解説(C言語部門)

これは Competitive Programming (その2) Advent Calendar 2015 の7日目の記事です。CODE FESTIVAL 2015の短縮王で出題した「割り算と足し算」のC言語部門の解説です。この問題のC言語部門で1位を獲得した ehaさんのコード を元に解説します。 n;f(x,i){n=…

CODE FESTIVAL 2015 参加記

N日目(N<0) 本戦・短縮王・リレーの問題準備をする。 短縮王をテストプレイしたら徹夜だった。 短縮王の順位表を宇宙ツイッタラーさんに依頼する。 0日目 スタッフで前夜祭をする。 1日目 朝 5時起床に失敗して若干TLEする。 リハをする。 徐々に目が覚めて…