こういうことをしたくなります。 ans = 0 for i = 1, ..., m: for j = i, ..., m: if [i, j] がSAT: ans = max(ans, j - i + 1) else: break SATの判定が O(N+M) なので、全体で O(M2(N+M)) になります。 j は解を更新する可能性がある範囲しか調べなくてい…

初めてSRMに出たのが 2010/10/21 なので今日で競プロ10周年になりました。 自分としては蟻本が出版された後に競プロ始めた人は新入りという感覚なんですが、いつの間にか 老害 古参と言われても文句が言えない年数になってました。 今後ものんびりやっていこ…

「空文字列でない」を入れることにしたみたいです（今日のABC-Fもそうでした）。PAST中めちゃくちゃ考えましたが、確かにこれで一意になりそうです。https://t.co/Aykgtguv14— きり (@kiri8128) May 10, 2020 なるほどなぁと思ったし周知しておくべきだと思…

こういうことをしたくなります 微妙に合わないのでてきとうに直します おわり

北大・日立新概念コンピューティングコンテスト2018の参考文献を読んだのでコンテストに関係ありそうなところを雑にまとめました。 Reduction by substitution を に置換することで次元を下げることを考えます。 この時、元の数式をに依存する部分と依存しな…

これはCompetitive Programming (1) Advent Calendar 2018の2日目の記事です。 JAGでは作問を楽に行うために、様々な試行錯誤を行なっています。今回はデータセット・問題文の準備にどのような工夫をしているかを紹介します。作問の全体的な流れは既に記事が…

これはAtCoder関連サービス Advent Calendar 2018の2日目の記事です。 以下のAtCoder Virtual Contestの挙動は既知のバグです。 他にもあったら教えてください。 そのうち直します。 直す……！ 直すが…… 今回まだその時と場所の指定まではしていない そのこと…

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

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

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

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