はじめに
今回も4完出来たのでDまで載せようと思います。
では見ていきましょう。
A - Five Integers
問題文はこちら
公式解説のように全部比べていっても良いですが、今回はHashSetを使ってみました。
Setで要素の重複はしないので、単純にsize()を出力すれば良いです。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//重複を弾くためのHashSet
HashSet<Integer> list = new HashSet<Integer>();
//それぞれをadd
for(int i=0;i<5;i++){
list.add(System.in.nextInt());
}
//数字の種類を出力
System.out.println(list.size());
System.out.close();
}
}
簡単ですね。
B - Prefix?
問題文はこちら
SとTをchar型配列として受け取って一文字ずつ比較しました。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//S、Tそれぞれをchar型配列として受け取り
char[] S = System.in.nextCharArray();
char[] T = System.in.nextCharArray();
//SがTより長いなら弾く
if(S.length>T.length){
System.out.println("No");
}else{
//先頭から順に見ていく
for(int i=0;i<S.length;i++){
if(S[i]!=T[i]){
System.out.println("No");
System.exit(0);
}
}
//forを抜けた=一致したのでYesを出力
System.out.println("Yes");
}
System.out.close();
}
}
ただ、接頭辞かだけの判定ならStringクラスのメソッドstartsWith(String prefix)を使うだけで良かったですね。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//S、Tの受け取り
String S = System.in.next();
String T = System.in.next();
//接頭辞ならYes、違うならNo
System.out.println(T.startsWith(S)?"Yes":"No");
System.out.close();
}
}
どちらでも実行時間に差はほとんどありませんでした。
C - Chinese Restaurant
問題文はこちら
pが0 1 2 3･･･って並んでいる時を考えてみると、pi-iは常に一定になることがわかります。では0と1を末尾に持って行った2 3･･･0 1の場合はどうでしょう。pi-iは末尾の0と1だけ異なってしまいます。しかし、modNではどうでしょう。
2-0=2、3-1=2、･･･、0-(N-2)=2-N≡2 mod N、1-(N-1)=2-N≡2 modN
一致していますね。
ということで、どれかの数字Mを基準にしたときにM M+1 M+2･･･ (modN)と一致している個数を数えれば人Mと料理Mを一致させたときに喜ぶ人数が求められます(実際には±1の範囲も加算する)。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、pの受け取り
int N = System.in.nextInt();
int[] p = System.in.nextInt(N);
//pi-i modNの重複を数える配列
int[] count = new int[N];
//条件を元に加算
for(int i=0;i<N;i++){
count[(p[i]-i+N+1)%N]++;
count[(p[i]-i+N)%N]++;
count[(p[i]-i+N-1)%N]++;
}
//最大を探す
int max = 0;
for(int tmp:count){
max = Math.max(max,tmp);
}
//出力
System.out.println(max);
System.out.close();
}
}
早めに解法に気付いて良かったです。
D - Unique Username
問題文はこちら
DFSで実装しました。
選んだ文字数と作りかけのユーザー名を引数に持つようにして全通り試しました。
間に合うのか？と思うかもしれませんが、かなり組合せの数が少ないので十分終わります。
各Nでの通り数
全部の文字の長さが1で、かつ重複が無い時が一番通り数が増えるのでその条件下での通り数を求めます。
・N=1の時
1個しかないので1通りです。
・N=2の時
並べ替えは2!=2通り、間に_を16-2=14個まで入れられるので、2×14=28通りです。
・N=3の時
並べ替えは3!=6通り、_を合計16-3=13個入れられ、必ずそれぞれの間に1個以上入れる必要があるので、
$6 \times \sum_{i=1}^{13}\sum_{j=1}^{13-i}1=396$通りです。
以下同様に、
・N=4の時
$4! \times \sum_{i=1}^{12}\sum_{j=1}^{12-i}\sum_{k=1}^{12-i-j}1=5280$通り
・N=5の時
$5! \times \sum_{i=1}^{11}\sum_{j=1}^{11-i}\sum_{k=1}^{11-i-j}\sum_{l=1}^{11-i-j-k}1=15120$通り
・N=6の時
$6! \times \sum_{i=1}^{10}\sum_{j=1}^{10-i}\sum_{k=1}^{10-i-j}\sum_{l=1}^{10-i-j-k}\sum_{m=1}^{10-i-j-k-l}1=90720$通り
・N=7の時
$7! \times \sum_{i=1}^{9}\sum_{j=1}^{9-i}\sum_{k=1}^{9-i-j}\sum_{l=1}^{9-i-j-k}\sum_{m=1}^{9-i-j-k-l}\sum_{n=1}^{9-i-j-k-l-m}1=141120$通り
・N=8の時
並べ替えは8!=40320通り、間に_を16-8=8個まで入れられますが、8文字の間は7カ所あってそれぞれに1個以上入れる必要があるので、全て_か追加で_をどこかに入れると考えれば_の入れ方は8通りです。よって、40320×8=322560通りです。
ということで、最大でも322560通り調べれば良いので十分終わります。
N=1の時は先に弾いてしまいました。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
//dfsに渡すためにstaticで
static HashSet<String> blackList = new HashSet<String>();
static String[] S;
static boolean[] isUsed;
public static void main(String[] args)throws IOException{
//N、M、Sの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
S = System.in.next(N);
//TをブラックリストとしてHashSetに
while(M-->0){
blackList.add(System.in.next());
}
//N=1のときは別に処理
if(N==1){
int now = blackList.size();
blackList.add(S[0]);
System.out.println((S[0].length()>2&&now<blackList.size())?S[0]:"-1");
System.exit(0);
}
//すでに使ってる文字か管理するboolean型配列
isUsed = new boolean[N];
//答え用変数
String answer = "";
for(int i=0;i<N;i++){
//使用済みに
isUsed[i] = true;
//dfs
answer = search(S[i],N-1);
//答えが見つかったなら終了
if(!answer.equals("-1"))
break;
//使用済みを解除
isUsed[i] = false;
}
//答えの出力
System.out.println(answer);
System.out.close();
}
//dfs
public static String search(String name,int n){
//使ってない文字列を探す
for(int i=0;i<S.length;i++){
if(isUsed[i])
continue;
//使用済みにセット
isUsed[i] = true;
//`_`を入れられるだけ入れてみる
for(int j=1;j<=16-name.length()-S[i].length();j++){
//StringBuilderで整形
StringBuilder sb = new StringBuilder(name);
for(int k=0;k<j;k++){
sb.append('_');
}
sb.append(S[i]);
//ちょうど最後の文字？
if(n==1){
//HashSetに突っ込んでみてサイズが変わればそれを返す
int now = blackList.size();
blackList.add(sb.toString());
if(now<blackList.size())
return sb.toString();
}else{
//dfs(-1以外が返ってきたらそれを返す)
String ret = search(sb.toString(),n-1);
if(!ret.equals("-1"))
return ret;
}
}
//使用済みを解除
isUsed[i] = false;
}
//見つからなかったら-1を返す
return "-1";
}
}
N=1の時に|S|<3をNoとするのを忘れてたのでとんでもないペナルティをいただいてしまいました･･･。
感想
A、B:易しい
C:比較的容易に気付いた。
D:バグり散らかしたが、発想だけは速攻で出来たのでヨシ！
って感じでした。
Cまでを比較的早めに解けたのでパフォーマンスが高かったですが、Dはもうちょっと早く解きたかったなぁという気持ちが･･･。