演算子の優先順位がわからないときに、何通り答えがあるかを求める問題。 頑張ってDPを使って解いてみた。 CYK法(Cocke-Younger-Kasami法:文脈自由文法が与えられたときに構文木を導出するアルゴリズム)みたいな手法。 授業で扱ったような気がするけど、実際…

nステップ六角形のマスを移動できるとき、移動可能なマスはいくつあるか数える問題。 障害物があるのでただ数えるだけではダメ。 深さ優先でもいけるよね・・・と思ってやったら、複雑なことになってしまった。マスが正方形ならそれでいいんだけど、この問題…

配列にどっちの手でタイプすればいいか保存しておけば簡単簡単。 と、思ったら、その配列を自分で作らなくちゃいけなくて面倒だった。 右手で打つ文字リストを作って、その中にあるかないかを見た方が、実装するのは簡単だったかな。 #include <iostream> #include <string> us</string></iostream>…

解説を参考にして書いてみた。 台形の面積を求めるだけ！って所だけみて書いたら、「あれ？いちごがy軸上にあるとき、上底と下底求められないじゃん」ってなった。 中点の長さを求めればいいんだね。小学校レベルの式がでてこない自分orz あとy2の範囲がケー…

2つのスプリンクラーで円形のPlantに水をやる問題。 Large問題は検討もつかないけど、Smallなら簡単。n=1のときは、そのPlantの半径がそのまま答え。 n=2のｔきは、2つのPlantを比べて大きいほうが答え。 n=3のときは、1つと2つのグループに分けて、それぞれ…

行列を隣り合った行の入れ替えによって下三角行列に変形する問題。以前他のところで見た気がする。何かの解説記事かな？ 上から順番に見て、条件を満たしていない行があれば、条件を満たす一番近い行と置き換える。 これを全部の行に行えばおｋ #include <iostream> #i</iostream>…

セル・オートマトンみたいな問題。Small程度のデータセットなら実行例のようにシミュレーション可能。 バクテリアの初期位置は100マス×100マスの範囲内。この範囲の外では、北と西に同時にバクテリアが存在することは無いから、この中だけでシュミレーション…

ダイヤモンドを拡張して上下左右対称にする問題。 拡張する時、追加する文字によってコストが違う物だと思い込んでいた。大きさしか関係ないんだね。 一位とった人のソースコードを読んで気がついた。自分なりに書きなおしたのが以下のコード。 １行読み取り…

この前のGCJ2010 Problem BをLarege問題用に書きなおし。 と、言っても、ほとんどContest Analysisの書き写しですが。前書いたプログラムは、実際の試合順にDPをやってけど、今回は後ろからメモ化再帰。 状態は試合番号とその後観る予定の試合数。計算量はO(…

Google Code Jam Round 1 は最高1008位でした。あーあRound2へは進めないな・・・と思ったら、おめでとうメールが。 確認するとちょうど1000位になってるよ！よくわからないけど、Round2に進めることになってしまったので、練習練習。 http://code.google.co…

よく考えたらGCJってなんの言語使ってもいいんだよね。 これ、木構造扱わないといけないし、文字列処理が入ってくるので、Perlを使って書いてみた。 #!/usr/bin/perl $T = <>; for $no(1..$T) { $tree = {}; $line = <>; chomp $line; ($N, $M) = split / /,…