SRM445 DIV2 過去問
300 - TheEncryptionDivTwo
ジョンはセキュリティの鬼です。
友達に手紙書きたいけど誰かに盗み見られたくないから暗号化したいらしいです。
アルファベットを別のアルファベットに置換する方法で暗号化します。文字列の先頭から、アルファベットの早い順に置換していきます。
例:"hello" -> "abccd"
暗号化したい文字列が渡されるので、暗号化済みの文字列を返せ。って問題。
- 文字を置換して、その先に今置換した文字と同じのがあったらそこも同じ文字に置換
- 書いて実行したら結果がおかしい
- 既に置き換えたところをまた置き換えてた
- 初期値じゃなかったら置き換えないようにすればいいか
- charの初期値ってなんだっけ・・・
- わかんないので最初にArrays.fill()で適当に埋めとこう
public class TheEncryptionDivTwo { public String encrypt(String message) { int len = message.length(); char[] c = message.toCharArray(); char[] res = new char[len]; //Arrays.fill(res, '0'); char b = 'a'; for(int i=0; i<len; i++){ //if(res[i]!='0') continue; if(res[i]!=0) continue; res[i] = b; for(int j=i+1; j<len; j++) if(c[j]==c[i]) res[j] = b; b++; } return new String(res); } }
後で調べたらcharの初期値は0(\u0000)だったので変更。
500 - TheNewHouseDivTwo
ジョン、またお前か。
新しい家を建てたいけど、セキュリティの鬼であるジョンは東西南北それぞれの直線方向に1つ以上の古い家がある場所じゃないと安心できないらしいです。
古い家の場所がint x, int yで与えられるので、ジョンが安心して新しい家を建てることのできる場所の数を返せ。って問題。
- 最初、4つの古い家に囲まれた場所でないとダメって読み違えて時間ロス。directlyを直接(隣接してる)って読んじゃったっぽい。正しくは"直線的に"でした。
- 最大で200*200*50だし全部チェック。でも一番端っこは見る必要ないNE!
public class TheNewHouseDivTwo { public int count(int[] x, int[] y) { int res = 0; for(int i=-99; i<=99; i++){ for(int j=-99; j<=99; j++){ boolean N=false, S=false, W=false, E=false; for(int k=0; k<x.length; k++){ if(x[k]==j && y[k]<i) N = true; if(x[k]==j && y[k]>i) S = true; if(y[k]==i && x[k]<j) W = true; if(y[k]==i && x[k]>j) E = true; } if(N&&S&&W&&E) res++; } } return res; } }