サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
iPhone 16
d.hatena.ne.jp/kyuridenamida
セグメントツリーは、"できるだけ大きい区間で取って誤魔化す"のも大切ですが、それに加えて"遅延評価"をかなり意識すればいろんな木が簡単に特に思考なしでかけるイメージがあります。ちなみにここから説明するセグメントツリーは少し弄るだけで色んな変形が出来るのですきですが、冗長なので定数倍遅いです。ごめんなさい。 #include using namespace std; #define N (117) // update(l,r,v) := [l,r]の区間に対してvを一様に足す. k,a,bは飾り struct NODE{ int sum;//更新された値. この値を参照する時は評価が完全に完了しているようにする. int lazy; //遅延されている値を保存している NODE(){ sum = lazy = 0; } }; NODE seg[2*N]; // inlineつけないと大変
いろいろなDPがありますが、これもまとめとくと良いと思ったので。僕はDPは得意ではないですが、それでもスキルアップに繋がったなあと感じた問題をピックアップしておきます。 DPかメモ化再帰か――ループの中で色々場合分けとかしなきゃいけなかったり、順序付けしにくかったりするDPは出来るならメモ化したほうがバグ減ったり実装楽だったりします。メモ化再帰は初期化ミスとかが無くて済むので。再帰が深くなりそうだったり、特殊なテクニック(ある区間をまとめて足したりする)とかする場合はやはりDPじゃないとだめですが、大体はメモ化再帰で代用が効きます。ではDP問の紹介。 (ネタバレ注意) 簡単な数え上げタイプ・Kannondou[☆]・A First Grader[★] 最長増加部分列タイプ( O(n log n)解法が存在するのでググったり蟻本とかを読むと良い。 )・ビルの飾りつけ(2007年度JOI春合宿
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
僕が知ってると楽だと思うもの。C++(g++)使ってる人向け。いろいろなのごちゃごちゃまぜまぜしてます。大きい配列グローバル配列として宣言しないと謎のセグフォします。ローカル変数で確保すると、[1000][1000]でもうセグフォしちゃったりするので注意。(JOI予選・本選共にそれで苦しんだ人が少なくなかったようです。)配列を多めに確保しよう少し余分に取ることで残念バグとかで死にません。切り上げcmathのクラスのceil()関数を使ってもよいが、A/Bを切り上げたい時、「(A+B-1)/B」で切り上げられる。ビットを数える__builtin_popcount(n)もうわざわざ実装する必要はありません!最大公約数・最小公倍数求める#include ヘッダの__gcd(a,b)を使うと良いです。a,bの最小公倍数はa/__gcd(a,b)*bとかでやると算術オーバーフローしなくてグッドです。
Compile簡単な実装問題なんだけど、39分掛かった。そろそろ大会だということで、問題を解くにしても時間を気にして解いている。とりあえず提出でWA、原因分からない(26分)→5分後くらいにお邪魔ブロック消しのルールの解釈を間違っていたことに気づいて修正。(31分)変なバグ(テスト入力データの書式がバグってた)に悩まされる。AC(39分)本番ではこういうくだらないミスをしてはいけない・・・。 #include #include #include using namespace std; #define rep(i,n) for(int i=0;i string data[12]; /* 方向用変数 */ int dx[] = {1,-1,0,0}; int dy[] = {0,0,-1,1}; /* 判定関数 */ bool iscorrect(int y,int x){ if(y>
このページを最初にブックマークしてみませんか?
『d.hatena.ne.jp』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く