問題概要 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0263 日本語なので省略。 解法 bitDPで解けました。 具体的には、 dp[何回目のビート音まで鳴ったか][ボタンの光り方] = 最大のスコア dp[31][1 で解けました。 計算量としては、上記の…
ブログ更新するの久しぶりです。 最近ではあまりコンテストにも参加しておらず、すっかり引退ガチ勢となりましたが、会津合宿の1日目にコンテストを開催します。問題は割と易しめになったと思います。プロコン慣れしてる人は合宿のウォーミングアップのつも…
問題概要 点集合C, R, Oが与えられる。 それぞれの集合には、点が最大200個含まれている。 Oの中の各点について、以下の3つのパターンの内どれになるか答えよ この点が、Cの任意の3点により作られる三角形に包含される : safeと呼ぶ この点が、Rの任意の3点…
問題概要 M本(4以上20以下)の長さが様々な棒が与えられる。 これらM本の棒を使って正方形の4つの辺を作ることができるか答えよ。 棒は折ったり曲げたりしてはいけません。 解法 まず、正方形を絶対作れない場合を考えましょう。 棒の長さを全部足し合わせて…
問題概要 int型の範囲に収まる正の数、t, a, bが入力される。 (t^a - 1)/(t^b -1)という式に関して、以下のどれに当てはまるか答えよ。 答えが、100桁より短い整数になる それ以外の答えになる（100桁以上であったり、小数であったりする場合） 解法 一つ一…
Problem A : Beautiful strings 出現回数が多いアルファベットに対して、大きい数字を割り当てればいいだけです。 int main(){ int T; cin >> T; string s; getline(cin, s); for(int CASE = 1; CASE <= T; CASE++){ cout << "Case #" << CASE << ": "; getl…
問題概要 省略 解法 枝刈全探索で解けます。枝刈手法 まず、再帰探索を開始する前に、式が合ってるか判定できるところは、全てしてしまいましょう。 空白が埋まらないと式判定できない場所は、式判定に必要な空白が全て埋まった時点ですぐ式判定してしまいま…
問題概要 ある数字aに、一ケタの数字を末尾に自由に付け足していく処理をn回行う。 ただし、毎回bで割り切れるようにケタを追加していかなければならない。 n回ケタを追加した後の値を出力せよ。 もし、このような数が作れない場合は、-1を出力せよ。 解法 1…
問題概要 N個の要素をもつ数列が与えられる。 この数列において、K個の要素をもつ区間それぞれについて、最小値・最大値を求めよ。 解法 セグメントツリーを使って、区間の最小値・最大値をO(log n)で求めてしまいましょう。 セグメントツリーは、プログラミ…
問題概要 文字列が入力される。 この文字列の順列全てを辞書順で出力せよ。 解法 next_permutationやるだけで解けました。 プログラム #include <iostream> #include <algorithm> #include <cstdio> using namespace std; int n; char s[1002]; int main(){ while(scanf("%s", s) != EOF){</cstdio></algorithm></iostream>…
問題概要 n, kが入力される。 n個の要素がある数列をバブルソートでソートされることを考える。 このとき、数列が並び終わるまでに、バブルソートの一重ループ目を実行した回数がkであるとする。 このようになる数列の初期配置は、何パターンあるか求めよ。 …
問題概要 nが入力される。 1, 2, ..., nの昇順数列をn, n-1, ..., 1の降順数列にするための最小の操作数と、操作方法を出力せよ。 数列に対する１回の操作では、次のことをできる。 (pos1, length, pos2) まず、数列のpos1番目からlength個を取り出す。 次に…
Problem C - Color Length 問題概要 N台の車の列とM台の車の列が与えられます。 これらの車は、'A'〜'Z'の色のどれかで塗られています。 N台の車の列とM台の車の列を順番を変えずに、マージした列Sを作ります。 文字列Sにおいて、以下の方法によって求めたコ…
会津合宿の1日目に、AOJでコンテストを開きます。 レベルはそんなに高くないと思うので、気軽にご参加ください。 みなさんの参加お待ちしてます！ 日時2012年9月3日(月) 14:00-17:00 コンテスト時間3時間 問題数7問程度 難易度ACM/ICPC国内予選A〜Eレベルを…
問題概要 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0243 問題文が日本語なので, 概要は省略です.
「な〜でこ〜だYO〜！」 ブログの更新がすごく久しぶりです〜. 昨日は, ACM/ICPCの国内予選に参加していました. 今年は, 競技プログラミングがすごく活発化していて, 昨年よりも他のチームのレベルがすごく高くなってくるだろうと予測していたので, 正直国内…
半年ぶりぐらいの更新な気がします. 今年の目標は, 国内予選を突破して, アジア地区の表彰式で名前を呼んでもらうことです(去年, おしくも名前を呼んでもらえなかったので). 余裕があれば, 海外のアジア地区大会に参加できるといいと思ってます.
問題概要 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2365 立命合宿のDay3で出題しました. 問題文長くてごめんなさい.
問題概要 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1259 各面に色が塗られた6面ダイスがn個(1 このとき, n個のダイスを全て等しくするためには, 最小でいくつの面を塗り替えなければならないかを求めよ. 等しいダイスとは, 問題文のFigure…
先日, 愛媛大学にて『EPOCH@まつやま』というプログラミングコンテストが開かれました. ぼくの友人のチーム『卒論からの逃避』がめでたくオンサイト出場を決めたので, ぼくもそれに便乗し逃避しに愛媛へ行ってきました. ということで, 今回は観戦者サイドで…
問題概要 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1213 (0,0)〜(10000,10000)の土地のどこかに宝石が落ちてきます. この土地には, ICさんとPCさんとACMさんの3人の人が住んでいます(それぞれの人の家の座標は与えられる). 宝石を取ること…
問題概要 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1212 問題文の図のような部屋があり, (0.75,0.25)の位置で, (1.0,0.5)の方向を向いて人が立っている. また, この部屋には, 鏡がいくつか置いてある. このとき, 立っている人は, 周りの壁…
問題概要 http://poj.org/problem?id=3720 1/2 = .5, 1/3 = .(3), 1/6 = .1(6)... であるとき, 1/2〜1/nの小数点以下に数字kが何回出現するか求めよ.
問題概要 http://poj.org/problem?id=3456「a⋅w + b⋅x + c⋅y + d⋅z」という式のa〜dが入力として与えられる.(a〜dは0以上の整数) w,x,y,zに, 0以上の整数を代入できるとき, この式を使って作ることができない100万以下の整数の数を答えよ. また, 作ることが…
問題概要 http://poj.org/problem?id=3407 球のA地点とB地点が, 緯度と経度で与えられます. このとき, AからBまでの球上での最短距離を求めてください.
問題概要 http://poj.org/problem?id=3414 容量A,Bまで入る2つのポットがあります. 最初の水の量は, 最初2つとも0です. このとき, 次の操作を行いながら, どちらかのポットの容量をCにしてください. FILL(i) : iのポットを満タンにする DROP(i) : iのポット…
問題概要 http://poj.org/problem?id=3421Xが入力として与えられ, 次のようなm+1個の数を含む数列を考えます. 1 = X0, X1, X2, …, Xm = X Xi番目の項は, X_(i-1)番目の項で割り切ることができ, Xi > X_(i-1)が成り立っています.このとき, この数列の最大長と,…
問題概要 http://poj.org/problem?id=3411片方向グラフが与えられます. あるエッジ i を通るときのコストは, ciをすでに訪れたことがある場合 Piかかり, 訪れたことがない場合 Ri かかります. このとき, ノード１からNまでの最短コストを求めてください.
しめじたんのおっかけ
問題概要 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1249 三目並べを立体にしたようなゲームで遊びます. 2人のプレーヤーが交互に, N*Nの棒のどれかにボールを差し込みます. 先に, M個のボールを直線状に並べた人が勝ちです. 全てのボール…
