noyのブログ

プログラミングとかゲームとか

競技プログラミング

AOJ 0553 ダンジョンの解説

AOJ 0553 ダンジョン ダンジョン | Aizu Online Judge 考察 問題点 あり本にある優先度キューを用いたガソリン問題と似ています。 ただし、こちらの問題では、ガソリンを入れられる量の上限があります。体力が0以下になる前に、どこかで回復しなければいけな…

構文解析初心者でも解ける問題を集めた+解説

競技プログラミングにおいての構文解析問題を集めました。難易度はAOJ-ICPCで300点程度です。

AOJ 1249 Make a Sequence

Make a Sequence | Aizu Online Judge AOJ-ICPC 200点所用時間:1時間30分 遅すぎる。実装力が足りてない。 問題概要 簡単に言うと3次元五目並。 n * n個のマスがある。黒いボールと白いボールを交互に置いていき、先にm個一直線に並べれば勝ち。 同じマスに…

AOJ - 2170 Marked Ancestor

Marked Ancestor | Aizu Online Judge 問題概要 木が与えられる。 以下の2つのクエリを処理し、出力された番号の合計を求める。 頂点aをマークする 頂点aから最も近いマークされた祖先の番号を出力する 解法 union-findこのスライドにある解法をそのまま実…

典型探索問題を解く

問題の解法が浮かばないなら、とりあえず解法の全探索をすればいいと思った。パラメータそれぞれに注目して解けるか考える。 DPなら、テーブルに何を持つかを全通り考えてみる。 AOJ ALDS1_4-D Search - Allocation 問題概要 数字がn個与えられる。それをk個…

Binary Indexed Tree(BIT)を学ぶ(1)

BITとはなんぞや POJ1990 MooFest 解法 コード 参考 BITとはなんぞや 参考:蟻本159頁列a_1, a_2, ... , a_nがある。 iが与えられたとき、a_1からa_iまでの和を求める。 (iとjが与えられたとき、a_iからa_jまでの和を求める。) iとxが与えられたとき、 a_i +…

やるだけ問題について メモ

やるだけ問題で特に気を付けること 別にやるだけ問題に限ったことではないけれど。 細かく関数化する できるだけ処理を分けて考えること。見やすいし、後になって直しやすい。main関数だけに書かれたコードを直すのは精神的にとてもつらい。 やるだけ問題を…

C++ 素数を求める2種類の方法

素数を求める方法 ひとつ目は愚直な割り算の繰り返し。ふたつ目はエラトステネスのふるい。割り算を繰り返せば、どんな素数でも求められる。しかし、多くの数を素数か判定するのには遅すぎる。 エラトステネスさえ覚えれば、多くの素数問題は攻略できる。し…

ABC021 C 正直者の高橋君

C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder状態AC AC AC WA AC . . . AC_人人人人人人人人人人_ > なぜかACできない <  ̄Y^Y^Y^Y^Y^Y^Y^Y^Y ̄ #include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) rang</bits/stdc++.h>…

ABC026 C 高橋君の給料

C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder 解説に書いてある解法、再帰で解いた。 ただ、なんとなく通してしまったのであまり考えていない。 そこで、ちょっとは頭を使ってみる。 #include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b);</bits/stdc++.h>…