SRM452 DIV2

250 - EggCartons

6個, 8個と入っている、2種類の卵の箱がある。
n個の卵を買いたいとき、最も少ない箱の数で買えよ！って問題。
ぴったりn個買えないときは-1。

スマートな解き方が分からない。
最大で100*100だし全部確かめればいいよね！

import java.util.*;
public class EggCartons {
    public int minCartons(int n) {
	 int res = 0;
	 if(n<6) return -1;
	 for(int i=0; i<n;i++){
	     for(int j=0; j<n;j++){
	 	if(6*i+8*j==n) return i+j;
	     }
	 }
        return -1;
    }
}

submitしてから気付いたけれど、nまで見る必要なかった。i<=n/6, j<=n/8でおｋ。
でももっかいsubmitすると点数下がったような気がしたのでほっときました。
208.1pt獲得。

500 - NotTwo

width x heightマスの盤がある。
全ての石について、2つの石間のユークリッド距離が2にならないように盤に置ける石の最大数を求める問題。

……ユークリッド距離をググるところからはじまりました。
ユークリッド距離がちょうど2になるのは縦横±2の場所だけなので、
左上から石を置きつつ、縦横±2の場所に置けませんよチェックを入れていけばおｋ？
ということでこんなかんじ。

import java.util.*;
public class NotTwo {
    public int maxStones(int width, int height) {
        int[][] ar = new int[height][width];
	int res = 0;
	for(int i=0; i<height; i++){
	    for(int j=0; j<width; j++){
		if(ar[i][j]!=-1) {
		    ar = setStones(j, i, ar);
		    res++;
		}
	    }
	}
        return res;
    }
    public int[][] setStones(int x, int y, int[][] aar){
	aar[y][x] = 1;
	if(x+2<aar[y].length) aar[y][x+2] = -1;
	if(x-2>-1) aar[y][x-2] = -1;
	if(y+2<aar.length) aar[y+2][x] = -1;
	if(y-2>-1) aar[y-2][x] = -1;
	return aar;
    }
}

気をつけながら書いたけどやっぱり何度かxとyを間違える。
最大で1000*1000ってあぶないかな？と思ったけど、ええいどうせスマートなコードなんて書けねー！とsubmit。
2つの試練を無事潜り抜けて321.94ptげっと。

1000 - HamiltonPath

最初、"Y"の都市間にだけ道路があると勘違いしていて、
exampleを見て「なんで道ないのに1から2に行ってんの！？」と混乱してました。ひどい。

問題文を正しく理解した頃には残り16分。
ひとつの行に2つ以上Yがあったら0->1, 0->2は同時に満たせないので通れないんじゃないか？と思ったけど
道路は双方向なことを忘れていた。この場合普通に1->0->2でいける。
でも3つ以上の時は通れないね！と分かったところで時間切れ。

どう解けばいいのか分からないのでエロい人のコードを見つつあとで復習する。きっと。

結果

530.04pt獲得してrateは951から1033に。やった4桁だ！
次は再来週にあるようなので、それまでにいくつか過去問といておきたい。