はじめに
今回はDまで解けたのでそれを載せようと思います。
では、見ていきましょう。
A - Probably English
問題文はこちら
愚直に比較して答えを求めました。
A.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//Nの受け取り
int N = sc.nextInt();
//一つでも条件に合うものがあったか管理する変数
boolean isEng = false;
while(N-->0){
//Wの受け取り
String W = sc.next();
//結果との論理和を取る
isEng |= W.equals("and");
isEng |= W.equals("not");
isEng |= W.equals("that");
isEng |= W.equals("the");
isEng |= W.equals("you");
}
//含まれてた？
out.println(isEng?"Yes":"No");
out.close();
}
}
見栄え的にもHashSetに入れてretainAllメソッド使った方が良かったですね…。
B - Bombs
問題文はこちら
これも愚直に求めました。
今見ているマスに対して、マンハッタン距離が書いてある数字よりも小さい時に.に書き換えて処理しました。
B.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//R、C、Bの受け取り(mapがB)
int R = sc.nextInt();
int C = sc.nextInt();
char[][] map = sc.nextCharArray(R);
//答え用の配列
char[][] ans = new char[R][C];
//全探索
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
//暫定的に今の状態を格納
ans[i][j] = map[i][j];
for(int k=0;k<R;k++){
for(int l=0;l<C;l++){
//数字が書いてあるマスを見つけたら、そのマスとのマンハッタン距離が数字以下かで答えを更新
if('0'<map[k][l]&&Math.abs(i-k)+Math.abs(j-l)<=map[k][l]-'0')
ans[i][j] = '.';
}
}
}
}
//答えの出力
out.println(ans);
out.close();
}
}
ちょっとどう処理すべきか悩んでしまいましたが、思いついてからはすんなり書けました。
C - Socks
問題文はこちら
HashSetを使って解きました。
各$i$について、$A_i$を追加してみてfalseが返ってきた時はsetから消して変数に加算、という風に処理しました。
C.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//Nの受け取り
int N = sc.nextInt();
int ans = 0;
HashSet<Integer> set = new HashSet<>();
//Setに追加していく(すでに追加済みなら消してansに加算)
while(N-->0){
int A = sc.nextInt();
if(!set.add(A)){
set.remove(A);
ans++;
}
}
//答えの出力
out.println(ans);
out.close();
}
}
これは比較的早く思いつきました。
D - Three Days Ago
問題文はこちら
各数字に対して、先頭から偶数回目の出現なら$+1$、奇数回目の出現なら$-1$を格納した配列を作り、$0$～$9$それぞれの値の変動をimos法のように先頭から加算していき、各状態での配列をHashMapに追加していきました。答えは追加時にすでにMapにある個数の総和です。
D.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//Sの受け取り
String S = sc.next();
//出現回数管理用Set
HashSet<Character> set = new HashSet<>();
//加減を管理する用の配列
int[] array = new int[S.length()];
//各数字について偶奇によって+1、-1を格納
for(int i=0;i<S.length();i++){
if(set.add(S.charAt(i)))
array[i]++;
else{
set.remove(S.charAt(i));
array[i]--;
}
}
//配列が等しいか判定するため用のクラス
class ArraySet{
int[] set;
ArraySet(int[] a){
set = new int[10];
System.arraycopy(a,0,set,0,10);
}
@Override
public boolean equals(Object o){
if(o instanceof ArraySet){
ArraySet a = (ArraySet)o;
boolean isTrue = true;
for(int i=0;i<10;i++){
isTrue &= set[i]==a.set[i];
}
return isTrue;
}
return false;
}
@Override
public int hashCode(){
int hash = 0;
for(int i=0;i<10;i++){
hash += set[i]*(i+1);
}
return hash;
}
}
//答え用の変数
long ans = 0;
//状態をkey、その個数をvalueとして管理
HashMap<ArraySet,Integer> sum = new HashMap<>();
//今の状態を格納
int[] now = new int[10];
sum.put(new ArraySet(now),1);
//先頭から変動を記録しながらansに加算していく
for(int i=0;i<S.length();i++){
now[S.charAt(i)-'0'] += array[i];
ans += sum.merge(new ArraySet(now),1,(s,t)->s+t)-1;
}
//答えの出力
out.println(ans);
out.close();
}
}
コンテスト後に、配列ではなく整数として状態を保持する解法でも解き直しました。
D.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//Sの受け取り
String S = sc.next();
//状態をkey、その出現回数をvalueとして管理
HashMap<Integer,Integer> sum = new HashMap<>();
//答え用変数
long ans = 0;
//初期状態を格納
int now = 0;
sum.put(0,1);
//先頭から変動を記録して答えを数え上げ
for(int i=0;i<S.length();i++){
//xorによる偶奇の管理
now ^= 1<<S.charAt(i)-'0';
ans += sum.merge(now,1,(s,t)->s+t)-1;
}
//答えの出力
out.println(ans);
out.close();
}
}
こっちの法が簡潔ですしわかりやすいですね。
感想
A:ちょっとめんどくさい
B:かなり悩んでしまった…
C:想像以上にサクッと解けた
D:時間をかけすぎてしまった…
って感じでした。
Dに対して2回ペナルティ取ってしまったので、それがかなりパフォーマンスにも響きました…。