ニートが学ぶプログラミング

ニートの日記。プログラムのことやら、くだらないこと、思ったことをまとめていきます。頑張って毎日更新するぞぉ_(:3」∠)_ 更新が連続して途切れたら察してください。

トップ > AtCoder Beginner Contest > AtCoderの過去問に挑戦 ABC003 AtCoder Beginner Contest 003

AtCoderの過去問に挑戦 ABC003 AtCoder Beginner Contest 003

AtCoder Beginner Contest AtCoder ABC Java プログラミング

こんにちは、鬱太郎です。という事（？）でAtCoder Beginner Contestの3回目の過去問をやったのでそれを記事にしていきたいと思います。

atcoderの画像を使わせていただきました。問題があれば削除します。

はじめに

私はプログラムやプログラミングコンテストに対して何ら知識はありません。私が書くコードは、性能的にも優れているものではありません。私自身が考え、学んでいく過程でできたコードです。無駄がありますが、お許しください。また、改善等の指導があればコメント欄に記入していただけると助かります。

公式URL

abc003.contest.atcoder.jp

使用したもの等

名称 使用したもの
言語 JavaSE8
エディタ pleiades All in one var.4.7.0
プラグイン addons.mozilla.org

A - AtCoder社の給料

問題

問題文

AtCoder社の社員である青木さんの給料は以下のように決められます。
ある月に、青木さんがタスクをこなした数を x とします。
この月の給料は、1 から x までの整数が 1 面ずつに書かれた x 面ダイスを振って出た目 × 1 万円がもらえます。
ただし、このダイスは、どの面が出る確率も等しく 1⁄x です。
青木くんは、暮らしていくのに十分な給料が得られるかどうかが心配で、平均いくら程度給料がもらえるか調べたいです。
毎月、青木くんはちょうど N 個のタスクをこなすこととし、毎月の給料の平均値を求めるプログラムを書いてください。

A問題では、提出した結果、全てのテストに対する判定がWAまたはREになってしまった場合のみ、質問タブにて可能な限りのトラブルシューティングを受け付けます。

提出結果のURLを添えて、お気軽にご質問ください。

また、ページ下部、「よくある質問」も、併せてご活用ください。

入力

入力は以下の形式で標準入力から与えられる。
N
  1. 1 行目には、整数で、青木くんが毎月こなすタスクの数 N (4≦N≦100) が与えられる。

出力

青木くんがもらえる毎月の給料（単位は円）の平均値を 1 行で出力せよ。
絶対誤差、または、相対誤差が 10−6 以下であれば許容される。
また、出力の末尾には改行を入れること。

入力例 1

  1. 6

出力例 1

  1. 35000
  • 1 万円から 6 万円がもらえる確率がそれぞれ 1⁄6 であるので、答えは
    • 10000×(1⁄6)+20000×(1⁄6)+30000×(1⁄6)+40000×(1⁄6)+50000×(1⁄6)+60000×(1⁄6)=35000
  • となります。

入力例 2

  1. 91

出力例 2

  1. 460000

見出しをクリックすると開きます。↓↓

回答

コードを書いたものは「Streamを使いたかった」という供述をしており…

成績

プログラムの実行時間およびメモリ使用量をまとめました。

実行時間 メモリ使用量
214 ms 28116 KB

Streamを使っているので実行時間が長いですね( ;∀;)

B - AtCoderトランプ

問題

問題文

AtCoder社では 1 人で行うトランプを使ったゲームが流行っています。
AtCoder社特製トランプでは、各カードにアルファベット小文字 1 文字（a～z）、または@の文字が書かれています。

ゲームは以下の手順で行います。
  1. カードを同じ枚数ずつ 2 列に並べて文字列を 2 つ作ります。
  2. @のカードは、それぞれa,t,c,o,d,e,rのどれかのカードと置き換えます。
  3. 2 つの列が指し示す文字列が同じであれば勝ち、同じでなければ負けです。
手順 1. で並べられた 2 つの列が指し示す2つの文字列与えられるので、適切に@を置き換えて、このゲームで勝つことができるかどうかを判定するプログラムを書いてください。

入力

入力は以下の形式で標準入力から与えられる。
S
T
  1. 1 行目には、1 列目のトランプが表す文字列 S が与えられる。
  2. 2 行目には、2 列目のトランプが表す文字列 T が与えられる。
    1. S、T ともにアルファベット小文字、および、@のみから構成されることが保証される。
    2. S、T の文字数は等しく、1 文字以上、10文字以下であることが保証される。

出力

このゲームで勝つことが可能であればYou can winと、不可能であればYou will loseと（シングルクォーテーションを除いて）1 行で出力せよ。また、出力の末尾には改行を入れること。

入力例 1

ch@ku@ai
choku@@i

出力例 1

You can win
  • 例えば、@をうまく置き換えることによって、両方ともchokudaiと一致させることが可能です。

入力例 2

aoki
@ok@

出力例 2

You will lose
  • 4 文字目において、@ で i を置き換えることができないので、一致させることができません。

入力例 3

arc
abc

出力例 3

You will lose
  • 2 文字目において、一致させることができません。

見出しをクリックすると開きます。↓↓

回答

文字列の比較の問題ですね。問題を見ると、S・Tともにn番目の文字をそれぞれ比較していけばよさそうですね。

ポイント:文字の比較にはString::indexOf(int ch)を使う

回答のソースコードを見ると、indexOfを使っていますね。

比較文で文字をそれぞれ比較してもいいのですが、コード量が増えてしまうのでできるだけやめた方がいいでしょう。

if(s.charAt(i) == '@'){
  char c = t.charAt(i);
  if(!(c == 'a' || c == 't' || ...)){
   ...
  }
}

上記のように書いてしまうと、ケアレスミスのもととなるため、String::indexOfを使いましょう。

if (s.charAt(i) == '@') {
  if ("atcoder@".indexOf(t.charAt(i)) < 0){
  ...
  }
}

String::indexOf(int ch)は引数の文字がその文字列に含まれている場合はそのインデックスを返し、含まれていない場合は-1を返します1。-1が出る挙動をうまく駆使して、0以上なら含まれていて0未満なら含まれていないという条件文として使うことができます。

成績

プログラムの実行時間およびメモリ使用量をまとめました。

実行時間 メモリ使用量
83 ms 25044 KB

C - AtCoderプログラミング講座

問題

問題文

AtCoder社では、優秀な競技プログラマーの講座動画を N 個配信しています。
初心者競技プログラマーの高橋くんは、AtCoder社が配信している動画を見て修練しようとしています。
高橋くんの実力はレートという実数値で表され、レートが高いほど実力が高いことを表します。

高橋くんのレートが C の時に、レート R の競技プログラマーの講座動画を見ると、高橋くんのレートは (C+R)⁄2 に変化します。
高橋くんは、講座動画を合計で K 個まで好きな順番で見ることができますが、同じ競技プログラマーの講座動画は一度までしか見ることができません。
講座動画を配信している N 人のレートが与えられた時、高橋くんが講座動画を見ることによって達成できるレートの最大値を求めるプログラムを書いてください。
ただし、高橋くんの初期レートは 0 です。

入力

入力は以下の形式で標準入力から与えられる。
N K
R1 R2 ... RN
  1. 1 行目には、講座動画の数を表す整数 N (1≦N≦100) と高橋くんが見ることのできる動画の数を表す整数 K (1≦K≦N) がスペース区切りで与えられる。
  2. 2 行目には、講座動画を配信している競技プログラマーのレートを表す整数 Ri (1≦Ri≦4,000) がスペース区切りで与えられる。

出力

高橋くんが達成できる最大レートを 1 行で出力せよ。
絶対誤差、または、相対誤差が 10−6 以下であれば許容される。
また、出力の末尾には改行を入れること。

入力例 1

  1. 2 2
  2. 1000 1500

出力例 1

  1. 1000.000000
  • 以下の方法が最適です。
    • まず、レート 1000 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 0 から (0+1000)⁄2=500 になります。
    • 次に、レート 1500 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 500 から (500+1500)⁄2=1000 になります。
  • しかし、例えば、以下の方法は最適ではありません。
    • まず、レート 1500 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 0 から (0+1500)⁄2=750 になります。
    • 次に、レート 1000 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 750 から (750+1000)⁄2=875 になります。

入力例 2

  1. 2 1
  2. 1000 1500

出力例 2

  1. 750
  • このケースでは高橋くんは 1 個の講座動画しか見ることができません。
  • レート 1500 の競技プログラマーの講座動画を見るのが最適です。

入力例 3

  1. 10 5
  2. 2604 2281 3204 2264 2200 2650 2229 2461 2439 2211

出力例 3

  1. 2820.031250000

見出しをクリックすると開きます。↓↓

回答

問題を要約すると、レートの降順でk個選んだあと、それを昇順で並べ替えて計算しなさいという事ですね。

Streamの出番だぁ！

  • 18行目Stream.of(br.readLine().split(" "))で入力されたRの文字列配列をStreamにします。
    String[] -> Stream<String>
  • 19行目.map(Integer::parseInt)でStringからIntegerに変換します。
    Stream<String> -> Stream<Integer>
  • 20行目.sorted((s1, s2) -> s2.intValue() - s1.intValue())でStreamを降順に並べ替えます。
  • 21行目.limit(k)でStreamの最初からk件に絞り込みます。
  • 22行目.sorted()で絞り込んだStreamを昇順で並べ替えます。
  • 23行目.collect(Collectors.toList());でStreamをリストにします。（終端処理）
    Stream<Integer> -> List<Integer>

成績

プログラムの実行時間およびメモリ使用量をまとめました。

実行時間 メモリ使用量
183 ms 26964 KB

D - AtCoder社の冬

問題

問題文

AtCoder社の社員室は R×C（R 行 C 列）の区画に区切られており、各区画には、社員のデスク、サーバーラックのどちらかがあるか、何もない空きスペースのどれかです。
AtCoder社のある地域の冬は寒く、暖房代をできるだけ節約するため、社員室の必要なスペースのみを区切って使用することに決めました。
しかし、資材の問題で、区画に平行な長方形の領域で区切らなければいけません。
そこで、
  • デスク、または、サーバーラックのある最も上の行のすぐ上、
  • デスク、または、サーバーラックのある最も下の行のすぐ下、
  • デスク、または、サーバーラックのある最も左の列のすぐ左、
  • デスク、または、サーバーラックのある最も右の列のすぐ右
の 4 辺で囲まれた区画を壁で囲みました。
すると壁で囲まれた領域は X×Y（X 行 Y 列）の区画になりました。
また、AtCoder社の社員室には、D 個のデスクと、L 個のサーバーラックがあります。
もともと、社員室に、どのようにデスクとサーバーラックの配置されていたのか、考えうるパターン数を 1000000007=109+7 で割った余りを求めるプログラムを書いてください。

入力

入力は以下の形式で標準入力から与えられる。
R C
X Y
D L
  1. 1 行目には、AtCoder社の社員室の区画の行数、列数を表す整数 R, C (1≦R,C≦30) がスペース区切りで与えられる。
  2. 2 行目には、社員室の壁に囲まれた部分の区画の行数、列数を表す整数 X, Y (1≦X≦R, 1≦Y≦C) がスペース区切りで与えられる。
  3. 3 行目には、社員室にある社員のデスクの数、サーバーラックの数を表す整数 D, L (D,L≧0, 1≦D+L≦X×Y) がスペース区切りで与えられる。

出力

社員室にどのようにデスクとサーバーラックの配置されていたのか、考えうるパターン数を 1000000007=109+7 で割った余りを 1 行で出力せよ。
また、出力の末尾には改行を入れること。

部分点

D+L=X×Y の場合のテストケースに全て正解した場合、101 点満点中の 100 点が与えられる。
満点解法は非常に難しいので、部分点を確実に取ることから考えましょう。

入力例 1

  1. 3 2
  2. 2 2
  3. 2 2

出力例 1

  1. 12
  • このケースは D+L=X×Y を満たすため、部分点のテストケースに含まれる可能性があります。
  • 以下の 12 通りの配置が考えられます。ここでDはデスク、Lはサーバーラック、.は何もないことを表します。
DD  DL  DL  LD  LD  LL  ..  ..  ..  ..  ..  ..
LL  DL  LD  DL  LD  DD  DD  DL  DL  LD  LD  LL
..  ..  ..  ..  ..  ..  LL  DL  LD  DL  LD  DD

入力例 2

  1. 4 5
  2. 3 1
  3. 3 0

出力例 2

  1. 10
  • このケースは D+L=X×Y を満たすため、部分点のテストケースに含まれる可能性があります。

入力例 3

  1. 23 18
  2. 15 13
  3. 100 95

出力例 3

  1. 364527243
  • このケースは D+L=X×Y を満たすため、部分点のテストケースに含まれる可能性があります。
  • 社員室の配置パターンは 145180660592914517790287604376765671109248284280228061640640 通りで、これを 109+7 で割った余りである 364527243 を出力してください。

入力例 4

  1. 30 30
  2. 24 22
  3. 145 132

出力例 4

  1. 976668549
  • このケースは D+L=X×Y を満たさないため、部分点のテストケースに含まれることはありません。
  • 無理に正解しようとせず、余裕のある人だけ挑戦してみてください。

見出しをクリックすると開きます。↓↓

回答

難しいですね… ABC3回目にして部分点というのを始めてみてとても驚きました。私は120分では解けませんでした。ただ、さらに1時間かけて部分点まで取れたので満足です。

部分点しかもらえない回答です。

部分点のみの場合の大体のアルゴリズムは30分くらいかかりましたが、何とかわかりました。

XYの範囲内におけるdとlの組み合わせ×（縦におけるXYの移動範囲）×（横におけるXYの移動範囲）

{ \huge{\displaystyle{Ans = {}_{d + l} \mathrm{C}_d ×{}_{1 + r - x} \mathrm{C}_1 × {}_{1 + c - y} \mathrm{C}_1}}}

ですが、nC1=nなので、

{ \huge{\displaystyle{Ans = {}_{d + l} \mathrm{C}_d (1 + r - x)(1 + c - y)}}}

ですね。実際はmod1000000007をとるわけですが。

入力例1の場合

f:id:neet-utsu-taro:20171027155948p:plain

R*Cの中にあるXYの箱の配置が2通りあり、XYの箱の中の組み合わせが4C2ですね。

{ \displaystyle{Ans = {}_{2 + 2} \mathrm{C}_2 (1 + 3 - 2)(1 + 2 - 2)}}

{ \displaystyle{Ans = {}_4 \mathrm{C}_2×2×1}}

{ \displaystyle{Ans = 2_4 \mathrm{C}_2}}

{ \displaystyle{Ans = 2×\frac{4\cdot3}{2\cdot1}}}

{ \displaystyle{Ans = 12}}

入力例2の場合

f:id:neet-utsu-taro:20171027161333p:plain

入力例2の場合はXYの組み合わせが1なので、縦×横の計算のみですね。

{ \displaystyle{Ans = {}_{3 + 0} \mathrm{C}_3 (1 + 4 - 3)(1 + 5 - 1)}}

{ \displaystyle{Ans = 1 × 2 × 5}}

{ \displaystyle{Ans = 10}}

入力例3の場合

ちょっと桁数がまずいですねぇ…さすがに図を描いている余裕はないので式だけ書きます。

{ \displaystyle{Ans = {}_{100 + 95} \mathrm{C}_{100} (1 + 23 - 15)(1 + 18 - 13)}}

{ \displaystyle{Ans = {}_{195} \mathrm{C}_{95} × 9 × 6}}

{ \displaystyle{Ans = {54}_{195} \mathrm{C}_{95}}}

お客様の中に195C95の答えが分かる方、いらっしゃいませんか？ｗ

ちなみに、答えは

{ \displaystyle{Ans = 145180660592914517790287604376765671109248284280228061640640}}

ですって奥さん！桁数がやばいｗ

恐らく、プログラムを実装する際にmod1000000007を使うんでしょうね。計算途中でもmodを使わないと桁があふれて答えが合わなくなってしまいます。

{ \displaystyle{XY \mathrm{mod} P = (X \mathrm{mod} P)(Y \mathrm{mod} P)\mathrm{mod} P}}

のような暗号でも使われている（？）分配公式（？）を使うんでしょうけど、いかんせん詳しくなくて分数の場合などにどうすればいいのかわかりませんでした。

BigDecimalを使って実装する

注：邪道です

Javaユーザーの皆さん！朗報です！BigDecimalが使えますよ！

BigDecimalとは

BigDecimalはNumberクラスのサブクラスでmathパッケージに属しているクラスです。

変更が不可能な、任意精度の符号付き10進数です。BigDecimalは、任意精度のスケールなしの整数値と、32ビット整数のスケールで構成されます。0または正の場合、スケールは小数点以下の桁数です。負の場合、スケールなしの数値に、スケールの正負を逆にした値を指数とする10の累乗を乗算します。つまり、BigDecimalで表される数値は(unscaledValue×10^-scale)です2。

とんでもない大きな桁数を正確に計算できますという便利なクラスです。もちろん、intやdoubleといったプリミティブよりははるかに計算速度が遅くなるらしいです。最終手段ですね。

BigDecimalはクラスであって、プリミティブではないです。計算する際はクラスに付属している各メソッドを使う必要があります。下にプリミティブとBigDecimalの計算記述の違いを書いておきます。

プリミティブの場合

int a = 3;
int b = 2;

int v = a+b;
int w = a-b;
int x = a*b; 
int y = a/b;
int z = a%b;

BigDecimalの場合

BigDecimal a = new BigDecimal(3);
BigDecimal b = new BigDecimal(2);

BigDecimal v = a.add(b); 
BigDecimal w = a.subtract(b);
BigDecimal x = a.multiply(b);
//BigDecimal y = a.divideAndRemainder(b)[0]; //a/bの整数値の商を求める
BigDecimal y = a.divide(b);//無限小数になる場合は注意！
BigDecimal z = a.divideAndRemainder(b)[1];

BigDecimalは割り算をする際に無限小数の場合にどうするかなど色々と面倒ですが、今回は組み合わせを求めるので少数の値は出ません。ですので普通にBigDecimal::divideを使っていけますね。

ソースコード

BigDecimalを使って先ほどの式を実装するだけですね。桁あふれの心配をしないとあっけなくて少し邪道な気がします。

成績

プログラムの実行時間およびメモリ使用量をまとめました。

※ACじゃありません。部分点100点です。

実行時間が一番長かったテストケースのデータです。

実行時間 メモリ使用量
101 ms 20052 KB

意外と実行時間が短くて震える(((( ﾟДﾟ))))

BigDecimalの計算に1秒近く取られると思ったら全然でした。少なくとも今回の問題では問題なく使えるのではないでしょうか？

もっと桁数や計算数が増えてきたら厳しいかも？

改善

改善1 組み合わせをパスカルの三角形で求める

私の回答ではBigDecimalを使い半ば強引に求めました。解説を見ると、パスカルの三角形で組み合わせを求めることができるらしいです！

なんか授業でやったようなｗ

https://upload.wikimedia.org/wikipedia/commons/thumb/4/4b/Pascal_triangle.svg/588px-Pascal_triangle.svg.png

パスカルの三角形 - Wikipedia

このままだとプログラムを組む際に混乱するので、下のように直しました。

f:id:neet-utsu-taro:20171027191418p:plain

この表から

int[][] map = new int[11][11];
map[0][0] = 1;
for(int i=1;i<=10;i++)
 for(int j=0;j<=i;j++)
  map[i][j] = map[i-1][j-1] + map[i-1][j];

という式が思い浮かぶのは簡単でしょう。

IndexOutOfBoundsExceptionを考慮すると

int[][] map = new int[11][11];
map[0][0] = 1;
for(int i=1;i<=10;i++)
 for(int j=0;j<=i;j++)
   map[i][j] = ((j-1<0)?0:map[i-1][j-1]) + map[i-1][j];

こうですね。こうしてできたパスカルの三角形の表から組み合わせの数を求めることができます。10C5の場合はmap[10][5]ですね。

必要なのは最後の1行であって途中の計算結果は保存しておく必要がないことに気づいた方もいるのではないでしょうか？

int tmp[] = new int[11];
int value[] = new int[11];
tpm[0] = 1;
for(int i=1;i<=10;i++){
 for(int j=0;j<=i;j++)
   value[j] = ((j-1<0)?0:tmp[j-1]) + tmp[j];
 
 for(int j=0;j<=i;j++)
  tmp[j] = value[j];
}

こうすることで、メモリの消費量を抑えることができます。10C5はvalue[5]が保持しています。

さらに、この問題ではmod1000000007を取らないと桁数があふれる可能性があります。ですのでmodを計算に加えてあげます。

int tmp[] = new int[11];
int value[] = new int[11];
tpm[0] = 1;
for(int i=1;i<=10;i++){
 for(int j=0;j<=i;j++){
   value[j] = ((j-1<0)?0:tmp[j-1]) + tmp[j];
   value[j] %= 1000000007;
 }
 
 for(int j=0;j<=i;j++)
  tmp[j] = value[j];
}

こうすればパスカルの三角形を使って組み合わせを求めることができます。

下はソースコードです。満点は取れません！部分点の100点のみです。

成績

プログラムの実行時間およびメモリ使用量をまとめました。

実行時間 メモリ使用量
77 ms 21204 KB

やっぱり実行時間が早くなりました！

組み合わせはパスカルの三角形で求められるという事はとても大事なことでしょう。もしかしたら、これからやる問題にもこれを使ったものがちょろっと出てくるかもしれません。

満点回答

解説を見たのですが、すぐにはわからなかったので保留です。(´;ω;｀)

まとめ

初の部分点問題という事で少し動揺しました。ですが、これまでの問題の経験から比較的楽に問題を解けたのかなと思います。

着々と成長している感じがするぞ |дﾟ)

終わりに

ここまで読んでくださってありがとうございます！解説を見て完答させるつもりでしたが、ちょっと力不足でした。明日本番のコンテストが始まるまで少し粘ってみますね。それでもできなければいったん棚上げします。

スター、ブックマーク、読者登録ありがとうございます！とても励みになっています！

またね('ω')ノ

  1. https://docs.oracle.com/javase/jp/8/docs/api/java/lang/String.html#indexOf-int-↩

  2. https://docs.oracle.com/javase/jp/8/docs/api/java/math/BigDecimal.html↩