競技プログラミングで青になるまでにやったこと - hogecoder
リクエストを受けたので、最近流行りの「○○色になるまでにやったこと」記事を書きたいと思います。 自分の現在の位置について少し話すと、AtCoder 青上位・ Codeforces 青中位・CSAcademy 青中位・ TopCoder 青下位くらいです。全身青いです。近いうちに青卒業できるように頑張っているところです。なので「青色になったので書いている」わけではないのですが、青を目指している人々にとって参考になる記事になっていれば幸いです。 水色 → 青 これは Twitter などでもよく言われていることなのですが、 AtCoder の ABC / ARC の D がコンスタントに通せる ようになると青が見えてくると感じています。問題セットにもよるので一概には言えませんが、 C 問題は呼吸、 D 問題は最低でも 20 分以内には片付けたいところです。なので、コンスタントに通すにはどのよう
遅延評価セグメント木をソラで書きたいあなたに - hogecoder
最下段が N-1 から始まるのと、親と子の取得方法がわかってればセグ木は書けます (ホンマか？)— 009_tsutaj@CODE FESTIVAL (@_TTJR_) 2017年3月29日 この記事は前記事: 「セグメント木をソラで書きたいあなたに」の続編です。セグ木をソラで実装するのはまだ厳しい・・・という方はまずはこちらの記事を読んでみてください。 tsutaj.hatenablog.com この記事は「セグメント木はソラで書けるけど、遅延評価セグ木は書けない・・・」という人を対象にしています。 遅延評価って何？ まず遅延評価について軽く説明しておきます。 遅延評価というのは、値の伝播*1を遅らせるテクニックです。これは区間に対して更新を行うときに必要になる時が多いです。例えば、値の更新を普通のセグメント木でやろうとしたとき、範囲の長さを とするとこの範囲の長さだけクエリを呼ばなけれ
動的計画法における空間計算量削減テク - hogecoder
この記事は 「競プロ!!」競技プログラミング Advent Calendar 2017 の 日目の記事として書かれました。 競技プログラミングをそれなりにやってきた方となれば、動的計画法に触れたことも多いでしょう。今回は、その動的計画法における空間計算量削減テクを色々紹介したいと思います。 普通のナップザック問題 題材として、ごく普通のナップザック問題を考えてみましょう。 容量 のナップザックに、品物をいくつか入れたいと考えています。品物は全部で 個あり、 番目の品物は価値 、容量 です。品物の在庫はそれぞれ 個ずつなので、同じ商品を複数個入れることはできません。ナップザックの容量を超えることなく商品を入れる時、入れた商品の価値の総和の最大値を求めてください。 制約は 時間制限 sec メモリ制限 MB とします。せっかく空間計算量削減の話をするんですから、これくらい厳しくしないとですよね
セグメント木をソラで書きたいあなたに - hogecoder
セグ木がソラで書けなかったらセグ木に何か生やす問題とか解けない— つたじろう@帰省 (@_TTJR_) March 29, 2017 セグ木にいろいろ生やす問題がてんで解けない私なので、セグ木に慣れようと思い立ちました。そのためにはまずセグ木をもっと知らねばならないと思ったので、ソラで書けないか色々やっていました。 やってくうちにコツを掴んでソラで書けるようになってきたので、忘れないためにも記事を書くことにしました。ということで、何も見ずにセグ木を書くために押さえておきたいポイントを紹介していきます。 注意 この記事は、「セグ木がどんな形をしているかはわかるけど、実装はできない・・・」という方向けで、遅延評価が不要な、区間最小の基本的なセグメント木のみ扱っています。 そもそもセグ木って何という人は他記事を参考にしてください。 おすすめは iwiwi さんのスライド → プログラミングコンテ
競プロをやりはじめてから一年が経ちました - hogecoder
競プロをやりはじめて、今日でちょうど一年です。半年記事 に引き続き、ポエム的なものを書いていきます。 始めたきっかけ 自分が競プロをはじめたきっかけは、当時受けていたアルゴリズムの演習です。この演習の TA に競プロサークルの先輩がおり演習時にプロコンの話をいくつかしていたので、なんか面白そうだなあと思って先輩にプロコンについて聞いてみたところ、その日の夕方にサークルの活動があるからぜひ来てみないかという話になりました。(この演習がなかったらたぶん競プロやっていなかったと思います・・・) 放課後のプロコン勉強会参加できるかも！— TOEIC あと2日 (@_TTJR_) 2016年5月19日 それで始めてサークルの練習会にいきました。練習会ではいつも AtCoder Virtual Contest を使用しているのですが、この日に AtCoder の問題を始めて解きました。この時は C++
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
