AtCoder Beginner Contest 098
※今回のコンテストには出場できず、全ての問題は終わった後に解きました。
A - Add Sub Mul
out.println( max(a+b,a-b,a*b) );
B - Cut and Count
import static java.lang.System.*; import java.util.*; public class Main { //初期フィールド・メソッド--------------------------------------------- static Scanner sc = new Scanner(System.in); static int min(int... ar) {Arrays.sort(ar); return ar[0];} static int max(int... ar) {Arrays.sort(ar); return ar[ar.length-1];} //------------------------------------------------------------ //フィールド追加場所----------------------------------------------- static String s; //------------------------------------------------------------ //mainメソッド--------------------------------------------------- public static void main(String[] args) { int n = sc.nextInt(); s = sc.next(); int max = Integer.MIN_VALUE; for (int i=1; i<n; i++) max = Math.max(max,cut(i)); out.println(max); } //------------------------------------------------------------ //メソッド追加場所------------------------------------------------ static int cut(int n) { boolean[] x = new boolean[26]; boolean[] y = new boolean[26]; String a = s.substring(0,n); String b = s.substring(n,s.length()); for (int i=0; i<a.length(); i++) x[a.charAt(i)-97] = true; for (int i=0; i<b.length(); i++) y[b.charAt(i)-97] = true; int num = 0; for (int i=0; i<26; i++) { if (x[i] && y[i]) num++; } return num; } //------------------------------------------------------------ }
B問題にしてはちょっと難しいかも。
文字列長は最大でも100なので、全探索可能です。
切断した後の左右の文字列のうち、左側にある文字種を格納する配列xと、右側にある文字種を格納する配列yを用意し、あとは実際に全ての箇所を切断しながら、両配列に共通する文字種を数えていけばよいです。
問題を解くにあたり、
①substringを使った文字列の部分抽出のやりかた
②英小文字のchar値から97を引くことで、0~25までの数字に変換する
これらのテクニックを使えるようにしておくと便利です。
C - Attention
import static java.lang.System.*; import java.util.*; public class Main { //初期フィールド・メソッド--------------------------------------------- static Scanner sc = new Scanner(System.in); static int min(int... ar) {Arrays.sort(ar); return ar[0];} static int max(int... ar) {Arrays.sort(ar); return ar[ar.length-1];} //------------------------------------------------------------ //フィールド追加場所----------------------------------------------- //------------------------------------------------------------ //mainメソッド--------------------------------------------------- public static void main(String[] args) { int n = sc.nextInt(); String s = sc.next(); int[] eNum = new int[n]; int[] wNum = new int[n]; for (int i=1; i<n; i++) { if (s.charAt(i-1)=='W') wNum[i]++; wNum[i] += wNum[i-1]; } for (int i=n-2; i>=0; i--) { if (s.charAt(i+1)=='E') eNum[i]++; eNum[i] += eNum[i+1]; } int min = Integer.MAX_VALUE; for (int i=0; i<n; i++) { min = Math.min(min,wNum[i]+eNum[i]); } out.println(min); } //------------------------------------------------------------ //メソッド追加場所------------------------------------------------ //------------------------------------------------------------ }
累積和の問題です。
配列wNum：i番目の人を選んだとき、その人より左側にいるWの数の累積和
配列eNum：i番目の人を選んだとき、その人より右側にいるEの数の累積和
というふうに累積和をとって、二つの配列を順に探索し、wNum[i]+eNum[i]の最小値を出力すればよいです。
追記：もしかするとB問題も、累積和使えば全探索しなくても解けるのかな？
D - Xor Sum 2
またこんど
まとめ
今回のコンテストは深刻な寝不足により参加できませんでした。
解説を見ることなく、またWAを出すことなくA,B,C問題を完答できたのでよかったです。次回までに生活リズムを整えておきたい……。
yukicoder No.688 E869120 and Constructing Array 2
方針
・0と1の順番は関係ないので、リストに1を適当個詰めたあと、0を適当個詰めて、出力する
・ここでは便宜上、1を「2を作るための数」と定義し、0を「組み合わせを増やすための数」と定義する。
・合計が2になるには、1が少なくとも2個は必要。
→k=0のときは、0か1をひとつだけ出力すればよい。
1のみで数列を構成した場合
合計が2となる選びかたは……
・11 → 選び方は1通り
・111 → 3通り
・1111 → 6通り
・11111 → 10通り
1のみで配列を構成した場合、合計が2となるような選びかたは、「(1の数)C2」のコンビネーションで求まる。
0のみで数列を構成した場合
数列の部分集合（すべての選びかたの合計）は……
・0 → 選び方は2通り
・00 → 4通り
・000 → 8通り
・0000 → 16通り
0のみで配列を構成した場合、その部分集合の数は「2^(0の数)」で求まる。
1と0から数列を構成する
・1の個数とその選び方 2(1), 3(3), 4(6), 5(10), 6(15)......
・0の個数とその選び方 0(1), 1(2), 2(4), 3(8), 4(16), 5(32)......
たとえば、K=96のとき、1が4個（6通り）、0が4個（16通り）からなる数列を作ることで、題意を満たす数列となります。
K=10のときは1を5個並べればよいですし、K=2のときは1を2個と0を1個並べればよいです。
実装する
まず、k=0の場合は1もしくは0を出力して終わらせます。
次に、数列を1のみから構成した場合の選び方（Key）とその個数（Value）をmapに入れます。
・11 map.put(1,2)
・111 map.put(3,3)
・1111 map.put(6,4)
・11111 map.put(10,5)
・1*30 map.put(435,30) 最大値
もし指定されたkがこのmapのKeyに含まれているなら、そのValueぶんだけ1をリストに追加し、それを出力します。
さて問題は、指定されたkがmapのKeyに含まれていない場合です（2560など）
この場合は、kが(mapのKeyに含まれている数)*(2^n)の形になればよいわけですから、kを手当たり次第にmapのKeyで割っていきます（k/key = dとします）。このdが2^nの形になっているかどうかを確かめ、もしなっているなら、1をvalue回、0をn回リストに追加し、それを出力します。
追記：この方法だと配列の長さが30を超えてしまいそうなので、公式解説にある通り、0と1の個数を全探索するのがよいと思います。
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { Map<Integer,Integer> map = new HashMap<>(); for (int i=2; i<=30; i++) { map.put(i*(i-1)/2, i); } Set<Long> set = new HashSet<>(); for (int i=1; i<=28; i++) { set.add((long)Math.pow(2,i)); } List<Integer> ans = new ArrayList<>(); long n = sc.nextLong(); if (n == 0) out.println(1); if (map.containsKey((int)n)) { for (int i=0; i<map.get((int)n); i++) { ans.add(1); } printList(ans); } else { for (Map.Entry<Integer,Integer> e: map.entrySet()) { int k = e.getKey(); long d = n/k; if (set.contains(d)) { for (int i=0; i<map.get(k); i++) { ans.add(1); } while (d%2 == 0) { d /= 2; ans.add(0); } printList(ans); break; } } } } static void printList(List<Integer> list) { for (int i=0; i<list.size(); i++) { out.print((i==0?"":" ")+list.get(i)); } } }
AtCoder Beginner Contest 097
A - Colorful Transceivers
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int a=sc.nextInt(), b=sc.nextInt(), c=sc.nextInt(), d=sc.nextInt(); int difAB = (int)Math.abs(a-b); int difBC = (int)Math.abs(b-c); int difAC = (int)Math.abs(a-c); if (difAB<=d && difBC<=d) { out.println("Yes"); } else if (difAC <= d) out.println("Yes"); else out.println("No"); } }
むっ、A問題にしては少し難しくないですか。僕だけですか。
AさんとCさんが通話する方法には2パターンある。
・Bさんを間に挟んでいる場合（Math.abs(a-b)とMath.abs(b-c)、両方がd以下ならば通話可能）
・AさんとCさんが隣り合っている場合（Math.abs(a-c)がd以下であれば通話可能）
よって、この2パターンを試してみて、どちらかで通話可能ならYes、どちらの方法でも通話できないならNoを出力する。
B - Exponential
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int x = sc.nextInt(); TreeSet<Integer> set = new TreeSet<>(); set.add(1); for (int i=2; i<=33; i++) { for (int j=2; j<=100; j++) { if (Math.pow(i,j) > x) break; set.add((int)Math.pow(i,j)); } } int ans = 1; for (Integer n: set) { if (n > x) break; ans = n; } out.println(ans); } }
僕はこの問題で致命傷（3WA）を負いました。原因は、問題文を読み違えていたから。
対象となる数列を、
・1,4,9,16,25,36......
のような、（i*i）の形で表せるもの限定だと思い込んでいた。
問題文とサンプルをよく読めば、
・1,4,8,9,16,25,27,32,36......
であることが分かる。2^3や、2^5といった数字も入ってくる。
ACできたプログラムでは、「2^2,2^3,2^4......2^n」「3^2,3^3,3^4......3^n」「33^2（最大の値）」というような、x以下のべき乗数を片っ端からsetに詰め込んでいる。
C - K-th Substring
部分点解答→満点解答という順に提出したので、まずは部分点解答を。
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { String s = sc.next(); int k = sc.nextInt(); int n = s.length(); TreeSet<String> set = new TreeSet<>(); for (int i=1; i<=n; i++) { for (int j=0; j<n-i+1; j++) { set.add(s.substring(j,j+i)); } } int i = 1; for (String str: set) { if (i == k) { out.println(str); break; } i++; } } }
部分点解答は、「長さnまでの、考えられうるすべてのsubstringを列挙し、TreeSetに詰め込み、先頭からk番目を出力する」というものになっている。
TLEして当然の全探索解答だが、意識的に部分点解答を作れたという点で成長が見られると思う。
では次に、満点解答を。
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { String s = sc.next(); int k = sc.nextInt(); int n = s.length(); TreeSet<Character> set = new TreeSet<>(); for (int i=0; i<n; i++) { set.add(s.charAt(i)); } List<Character> list = new ArrayList<>(); int x=0; for (Character c: set) { if (x >= Math.min(set.size(),k)) break; list.add(c); x++; } TreeSet<String> ans = new TreeSet<>(); for (int i=0; i<list.size(); i++) { char c = list.get(i); for (int j=0; j<n; j++) { if (s.charAt(j)==c) { for (int l=0; l<Math.min(k,n-j); l++) { ans.add(s.substring(j,j+l+1)); } } } } int i = 1; for (String str: ans) { if (i == k) { out.println(str); break; } i++; } } }
流れとしては、
・sを1文字ずつ探索し、TreeSet1に入れる
・TreeSet1の先頭から Math.min(5,s.length()) 個取り出し、リストに入れる
・リストに入っている文字一つ一つにつき、sを再び1文字ずつ探索する。
・リストの文字に行き当たったら、そこから Math.min(5,伸ばせるだけ) 伸ばしつつ、TreeSet2に格納していく。
・仮にsがabcdefgだとすると、リストの文字が bのときは、[b,bc,bcd,bcde,bcdef] がTreeSet2に入ることになる。
・TreeSet2の、先頭からk番目を出力して終了。
というもの。ようは、辞書順の小さいものを優先して探索して、計算量を減らそうと試みている。
追記：2つめのfor文のあとに「if(ans.size() >= k) break;」を入れれば、さらに計算量を減らせそう。
理由：辞書順で一番小さい文字（aとします）についてすべて探索し終えた段階で、substringがk個以上あったなら、その中からk番目に小さいsubstringを出力すればよく、もはやそれよりも辞書順で大きい文字（b,c,d......）を探索する必要はないからです。
しかし、解答となるsubstringが5文字以下であることを考えると、sの各文字について後方に5文字ぶんだけ探索し、setに入れることを繰り返せば、計算量25000で済み、TLEしないのでは……？
ということで、以下に、その方針に従って改良したプログラムをのせます。
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { String s = sc.next(); int k = sc.nextInt(); int n = s.length(); TreeSet<String> ans = new TreeSet<>(); for (int i=0; i<n; i++) { for (int j=0; j<Math.min(k,n-i); j++) { ans.add(s.substring(i,i+j+1)); } } int i = 1; for (String str: ans) { if (i == k) { out.println(str); break; } i++; } } }
うーん、これだけで済んでしまうのか。計算量だけでいえば一つ前の解答のほうが優れているんだろうけど、競プロならこっちを書くべきだろう。計算量の計算をとっさにできるようにしたい。
追記：あっ……部分点解答のnを5にするだけで満点解答になるじゃないか……
D - Equals
またこんど
まとめ
問題文をよく読むこと。それだけで今回の順位も50位は縮められた。C問題については、自力で部分点解答から満点解答まで持っていくことができ、素直に嬉しかった。昨日の記事では悲惨な結果に終わりそうなどと書いたが、終わってみると可もなく不可もなくという内容だった（202位）。今後はアルゴリズムの復習をしつつ、以前買った競プロ本も進めていければなと思っている。
n以下のすべての素数をリストで返すメソッド
エラトステネスのふるいを用いて、n以下のすべての素数をリストアップするメソッド。
ふるい終わったあとの配列が穴だらけになって不便なので、単にそれをリストに詰め込んだだけです。
static List<Integer> primeList(int n) { List<Integer> list = new ArrayList<>(); boolean[] prime = new boolean[n+1]; Arrays.fill(prime,true); prime[0]=false; prime[1]=false; for (int i=2; i<Math.sqrt(n); i++) { if (!prime[i]) continue; for (int j=2; i*j<=n; j++) { prime[i*j] = false; } } for (int i=0; i<prime.length; i++) { if (prime[i]) list.add(i); } return list; }
＜参考にしたページ＞
Javaで素数を求めるプログラムを実装 - にわとりプログラマーの備忘録
AtCoder Beginner Contest 096
※今回は不参加で、問題はすべてコンテスト終了後に解きました。
A - Day of Takahashi
out.println(a<=b?a:a-1);
B - Maximum Sum
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int a=sc.nextInt(), b=sc.nextInt(), c=sc.nextInt(), k=sc.nextInt(); int total = a+b+c; int max = max(a,b,c); int pow = (int)Math.pow(2,k); out.println((total-max)+max*pow); } static int max(int... ar) { Arrays.sort(ar); return ar[ar.length-1]; } }
一番大きい数字を2倍していけばいいのではと考え、素直に実装した。
C - Grid Repainting 2
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); static int[] dx = {0,1,0,-1}; static int[] dy = {-1,0,1,0}; public static void main(String[] args) { int h=sc.nextInt(), w=sc.nextInt(); char[][] map = new char[h+2][w+2]; for (int i=1; i<h+1; i++) { String s = sc.next(); for (int j=0; j<w; j++) { map[i][j+1] = s.charAt(j); } } boolean isAchievable = true; loop: for (int i=1; i<h+1; i++) { for (int j=1; j<w+1; j++) { if (map[i][j]=='#') { boolean isBlack = false; for (int k=0; k<4; k++) { if (map[i+dy[k]][j+dx[k]]=='#') isBlack = true; } if (!isBlack) { isAchievable = false; break loop; } } } } out.println(isAchievable?"Yes":"No"); } }
正直に告白すると、今回の問題は4問ともすべて解説を見てから解いている。
それでこの問題だが、すべての黒マスについて「上下左右のマスのうち、少なくとも一つが黒マス」という形になっていれば、達成できる。逆に、「上下左右すべてが白マス」という黒マスがあれば、達成できないということになる。
よって、すべての黒マスについて、上下左右のマスを調べればよい。
D - Five, Five Everywhere
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); List<Integer> list = primeList(55555); for (int i=0; i<n; i++) { out.print((i==0?"":" ")+list.get(i)); } } static List<Integer> primeList(int n) { List<Integer> list = new ArrayList<>(); boolean[] prime = new boolean[n+1]; Arrays.fill(prime,true); prime[0]=false; prime[1]=false; for (int i=2; i<Math.sqrt(n); i++) { if (!prime[i]) continue; for (int j=2; i*j<=n; j++) { prime[i*j] = false; } } for (int i=0; i<prime.length; i++) { if (prime[i] && i%5==1) list.add(i); } return list; } }
メソッド「primeList」では、「n以下かつ、5で割って1余る素数」のリストを返すようにしている。
まずメインメソッドでprimeListを引数55555で動作させ、戻り値をlistに格納する。そしてその中から、小さい順にn個を出力して解答の数列としている。
このメソッドの作成にあたって、以下のページを参考にしました。
Javaで素数を求めるプログラムを実装 - にわとりプログラマーの備忘録
まとめ
とりあえず、競プロを休止していた期間に行われたコンテストについては、これですべて解き終わった。今日開催されるABC097は１か月ぶりのコンテストということになるけれど、悲惨な結果に終わるような気がしてならない。
それと、今回使った「n以下の素数をリストとして返すメソッド」というのは便利そうなので、作って記事にしようと思った。
AtCoder Beginner Contest 095
※今回は不参加で、問題はすべてコンテスト終了後に解きました。
A - Something on It
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { String s = sc.next(); int price = 700; for (int i=0; i<3; i++) { if (s.charAt(i)=='o') price += 100; } out.println(price); } }
B - Bitter Alchemy
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n=sc.nextInt(), x=sc.nextInt(); int min = Integer.MAX_VALUE; for (int i=0; i<n; i++) { int temp = sc.nextInt(); min = Math.min(min,temp); x -= temp; } out.println(n+(x/min)); } }
入力で与えられたn種類のドーナツについては、すべて作れることが保障されているので、まずはそれを作る。残った粉で、一番粉消費が少ないドーナツを作れるだけ作る。
C - Half and Half
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int a=sc.nextInt(), b=sc.nextInt(), c=sc.nextInt(), x=sc.nextInt(), y=sc.nextInt(); int total = 0; if (a+b > 2*c) { //ABピザを買う必要あり total += 2*c*(Math.min(x,y)); if (x > y) { total += (x-y)*a; } else if (x < y) { total += (y-x)*b; } int total2 = 2*c*(Math.max(x,y)); out.println(Math.min(total,total2)); } else { total = a*x + b*y; out.println(total); } } }
まず、（a+b > 2*c）の条件式によって、ABピザを作る必要があるかどうか判断する。作らない場合は簡単。
ABピザを作る場合だが、「最低限の数だけABピザを作り、残りをAピザもしくはBピザで補う場合」と、「余ることが前提でABピザを作り、AピザとBピザは1枚も作らない場合」に分けられる。前者はmin(x,y)個、後者はmax(x,y)個ということだ。
それぞれ実際に作ってみて、金額が少ないほうを出力する。
D - Static Sushi
部分点の解のほうは理解できそうだったけれど、とりあえず先送り
まとめ
とくになし
可変長引数を用いた、最大値・最小値を求めるメソッド
可変長引数なるものがあることを（たった今）知りました。面白い書き方だったので、すぐにメモすることに。
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { out.println(max(1,8,5,10,9)); out.println(min(9,5,7,1)); } public static int max(int... ar) { Arrays.sort(ar); return ar[ar.length-1]; } public static int min(int... ar) { Arrays.sort(ar); return ar[0]; } }
とこのように書けば、一つの型につき何個でも引数をとれるようなメソッドを作れる。
可変長引数には以下のような制約がある。
・一つのメソッドに一つだけ
・最後の引数でのみ使用できる
とここまで書いて、便利な機能だと感心したものの、競プロではあまり使い道はないかもしれない。3、4個の数字から最大値を求めるためにわざわざメソッドなど作っていては解答が遅くなるし、10個の数字から最大値を……となれば、配列を使えばよいからだ。
