2012-07-01から1ヶ月間の記事一覧

AOJ 0247 Ice Maze

問題文 Ice Maze 感想 本番じゃ手出したくない部類の問題だなあ。 枝刈り探索。semiexpが自明な枝刈りするだけで通ったと言っていたのを思い出して解いた。 ただ1.0sとか厳しくて、1.5sくらいでTLEしててハマってた。もっと自明な枝刈りしたら普通に通ってワ…

AOJ 0246 Bara-Bara Manju

問題文 Bara-Bara Manju 感想 難しいが良問。去年の予選終わったあと、バックトラックとかしてて泥沼にはまってしまって、わかんなかったのでsemiexp先生に解法教えてもらった。 ただAOJのテストケース厳しいナァ。 ほかの人たぶん違う解法をしていて気にな…

AOJ 0245 Time Sale

問題文 Time Sale 感想 なんか探索多いけど、これもその1つ。ただこれは状態の持ち方間違えなければ普通に間に合う。 もし時刻tを持てなかったら割りと実装が大変になるんですが、さすがにPCK優しいので楽。問題文うろ覚えている程度には知ってたので、昨日…

AOJ 0244 Hot Spring Trip

問題文 Hot Spring Trip 感想 明らかに前問より簡単。ダイクストラを用いた最短経路問題に慣れていたらやるだけに感じた。10分で書けた。これ10分ってタイピング速度向上してる感ある。 DPするにしても探索するにしても何にしてもそうだけど、状態に対する感…

AOJ 0243 Filling Game

問題文 Filling Game 感想 この位置にあるしどうせ枝刈り全探索だと思って適当に15分くらいで書いて投げたらなぜか通ってしかも自分以外に1人しか通ってなかったので???ってなった。(まあ本番とはテストケース違うけど) 運良かったのか。こういう怪しいの何…

AOJ 0242 Input Candidates

問題文 Input Candidates 感想 とても悪名高い予選問題の1つ。AOJのテストケースは知らないが本番では改行コードがCR+LFだったので見えない制御文字\rに苦しめられた人々がたくさんいた。 解法 日頃からちゃんと\r消す習慣つけとくと嬉しい。 stringとかmap…

AOJ 0241 Quaternion Multiplication

問題文 Quaternion Multiplication 感想 うまく実装してくださいっての好き。 解法 やるだけだが、上手いやり方を思いつかなきゃいけないあたり好き。普通に手計算したりするのはちょっと恐すぎるし、それで泥沼にはまったら予選落ちメニーチャンシーズなの…

AOJ 0240 Interest Rates

問題文 Interest Rates 感想 複利の場合の誤差が恐い(1.001)^30乗とか2^30とか大きくて恐いがまあ通りそうだと思った。 解法 元のお金は1円として考える。 ソース 実装マジで下手。 #include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <cmath> using namespace std;</cmath></vector></cstdio></algorithm></iostream>…

AOJ 0239 Calorie Counting

問題文 Calorie Counting 感想 絶望的に条件を拾いづらくしており悪質。 解法 読んだらあとは実装すると通る。 ソース 実装下手 #include <iostream> #include <cstdio> using namespace std; int II[1000] , PP[1000] , QQ[1000] , RR[1000]; int main(){ int n; while(cin >></cstdio></iostream>…

AOJ 0238 Time to Study

問題文 Time to Study 感想 読みやすいこともない。 解法 素直に実装する。 ソース ふつう。 #include <iostream> #include <cstdio> using namespace std; int main(){ int t; while(cin >> t && t){ int n; cin >> n; int s = 0; for(int i = 0 ; i < n; i++){ int a,b; cin </cstdio></iostream>…

パソコン甲子園2011 予選・解法

PCK2011予選。僕は去年台風で予選参加できなかったのですが、今回AOJにその問題があがったので解いてみました。 1. 勉強の時間(4点) : AOJ 0238 Time to Study - kyuridenamidaのチラ裏 2. カロリー計算(4点) : AOJ 0239 Calorie Counting - kyuridenamid…