新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

参加記録:AtCoder

[参加記録] AtCoder Beginner Contest #13

結果

  • 解説スライド:AtCoder Beginner Contest 013 解説
  • A, B問題は解答できたが、C問題の部分点(10点)貰ったところで終了でした。
    • A問題:テンパってswitch文で全分岐作った
      • 解説にもある通り、配列入れて回すとか文字コード使うとかあったはず…
    • B問題:数を増やしていく方向と減らしていく方向の両方計算して小さい方が答え
    • C問題:基本食事抜きで満腹度不足の場合質素と普通の食事の良い方を選択にするもWA>全探索でもやってみるも間に合わず
      • 「質素と普通の食事の良い方」の良い方を見分ける条件分岐が見つからず
      • 慌てて再帰使って全探索してみるもTLE
      • 動的計画法というのがあるらしい
public class MemoSaikiExample {
	// メモ用連想配列
	Map<Long, Long> MEMO;
	
	// a[n] を求める
	// (i <= 0) のとき、a[i] = 1
	// それ以外のとき、a[i] = a[n/p-x] + a[n/q-y]
	public long calc(long n, int p, int q, int x, int y) {
		MEMO = new HashMap<Long, Long>();
		return saiki(n, p, q, x, y);
	}
	
	public long saiki(long n, int p, int q, int x, int y) {
		if (n <= 0) {
			return 1;
		}
		
		// メモに記録されていればそのまま返す
		if (MEMO.containsKey(n)) {
			return MEMO.get(n);
		}

		// メモに無ければメモに入れる
		MEMO.put(n, saiki(n/p-x, p, q, x, y) + saiki(n/q-y, p, q, x, y));
		return MEMO.get(n);
	}
}
    • 諸注意
      • メモを配列でやると、配列の大きさによってはメモリ不足になる上、使われない無駄な領域が存在する可能性
      • 場合によっては連想配列でもメモリ不足になるかも>メモする値の領域を限定するなどの工夫が必要
      • 全探索を考える>手間を減らす方法を考える、という流れでやると良いっぽい