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

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

長すぎるカテゴリー欄をアニメーションですっきりさせてみた

はてなブログ プログラミング その他

こんにちは鬱太郎です。ブログを書いているとついつい色々なカテゴリーが増えてしまいますよね？私もそうなんです。カテゴリー数が増えてしまうと、サイドモジュールのカテゴリーが占める割合が大きくなってしまいます。他のモジュールが見えなくなってしまいます。

そんな悩みを解決してみたので記事にしたいと思います。

右のカテゴリー欄にマウスカーソルを合わせると…？

スマホの方はカテゴリー欄のタイトルをタップすると…？

アニメーションで開いたり閉じたりします！

何もしないとカテゴリー欄のサイズが小さくなります。カーソルを合わせると、カテゴリー欄がすべて表示されます。

使い方

下のコードをデザイン→カスタマイズ→サイドバー→モジュール追加→HTMLのコード欄に追加します。タイトルは不要です。一行目はjQueryの読み込みです。既にヘッダー等に同様の記述がある場合は必要ありません。

<script type="text/javascript" src="https://code.jquery.com/jquery-1.11.3.min.js"></script>
<script>
$(function(){
 var normalHeight = "300px";
 $(".hatena-module-category").height(normalHeight).css("overflow","hidden").hover(function(e){$(this).animate({height:$(this).get(0).scrollHeight},{duration:"slow"})},function(e){$(this).animate({height:normalHeight},{duration:"slow"})});
})
</script>

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

私は既にヘッダーにjQueryの読み込み記述があるため、上の画像では同様の記述がありません。注意してください。

var normalHeight = "300px";の数値はタイトルを含んだカテゴリモジュールを表示させる高さです。好きな値に変更してください。

はい。これだけで完成です！簡単ですね！

終わりに

何かと応用がききそうなのでぜひ試してください！何より楽しいです(*'ω'*)

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

またね('ω')ノ

AtCoderの過去問に挑戦 ABC076 AtCoder Beginner Contest 076

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

こんにちは鬱太郎です。先週の土曜日に開催されたAtCoderのコンテストを復習したため、記事にしたいと思います。

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

はじめに

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

公式URL

abc076.contest.atcoder.jp

結果

ABC076ランキングの結果を表示します

使用したもの等

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

A - Rating Goal

略

B - Addition and Multiplication

問題

配点：200 点

問題文

square1001 は、電光掲示板に整数 1 が表示されているのを見ました。
彼は、電光掲示板に対して、以下の操作 A, 操作 B をすることができます。

  • 操作 A： 電光掲示板に表示する整数を「今の電光掲示板の整数を 2 倍にしたもの」に変える。
  • 操作 B： 電光掲示板に表示する整数を「今の電光掲示板の整数に K を足したもの」に変える。

square1001 は、操作 A, 操作 B 合計で N 回 行わなければなりません。そのとき、N 回の操作後の、電光掲示板に書かれている整数として考えられる最小の値を求めなさい。

制約

  • 1≤N,K≤10
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。 

N
K

出力

square1001 が N 回操作を行った後の、電光掲示板に書かれている整数として考えられる最小値を出力しなさい。

入力例 1

4
3

出力例 1

10

高橋君は、操作 A, A, B, B の順でやると、整数を最小化できます。この時、電光掲示板に書かれている整数は 1 → 2 → 4 → 7 → 10 と変わり、最終的に 10 となります。

入力例 2

10
10

出力例 2

76

高橋君は、操作 A, A, A, A, B, B, B, B, B, B の順にやると、整数を最小化できます。この時、電光掲示板に書かれている整数は 1 → 2 → 4 → 8 → 16 → 26 → 36 → 46 → 56 → 66 → 76 と変わり、最終的に 76 となります。

なお、今日のコンテストは、AtCoder Beginner Contest 076 です。

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

回答

問題文を読んでると難しい感じがしてきますね。ですが問題Bです。という事は難しい問題ではないという事ですね！

問題から

  • 操作Aは2^xの指数関数
  • 操作Bはkxの線形関数

という事が分かりますね。つまり、操作後の最小値を求める場合は操作Aを先にする必要があるという事です。1->2->4..kまで操作Aを、そこから操作Bをすればいいでしょう。

この考えにたどり着ければ、そう難しくないでしょう。

ポイント for文の条件式にはカウンタ以外の比較もできる

分かってる方には冗談もほどほどにしろと言われてしまいますね。

for文は

for(初期操作;boolean（trueならばループ）;更新)

こうですね。(間違ってたらすいません)

通常のfor文では

for(int i=0;i<n;i++)

のようにカウンタの比較をよくします。しかし、2番目のループ条件には他のbooleanの条件も追加しても構いません。

今回の問題で言えばvalue<=kを条件に加えることもできます。13行目ですね。

for(; i<n && value <=k; i++)

break文を減らせて見やすくなります（ただそれだけです…）

成績

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

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

C - Dubious Document 2

問題

配点：300 点

問題文

E869120 は、宝物が入ってそうな箱を見つけました。
しかし、これには鍵がかかっており、鍵を開けるためには英小文字からなる文字列 S が必要です。
彼は文字列 S' を見つけ、これは文字列 S の 0 個以上 |S| 個以内の文字が ? に置き換わった文字列であることも分かりました。
ただし、文字列 A に対して、|A| を「文字列 A の長さ」とします。

そこで、E869120 はヒントとなる紙を見つけました。

  • 条件1：文字列 S の中に連続する部分文字列として英小文字から成る文字列 T が含まれている。
  • 条件2：S は、条件1を満たす文字列の中で辞書順最小の文字列である。

そのとき、鍵となる文字列 S を出力しなさい。
ただし、そのような文字列 S が存在しない場合は代わりに UNRESTORABLE と出力しなさい。

制約

  • 1≤|S'|,|T|≤50
  • S' は英小文字と ? から成る
  • T は英小文字から成る

入力

入力は以下の形式で標準入力から与えられる。

S'
T

出力

鍵となる文字列 S を出力しなさい。
ただし、そのような文字列 S が存在しない場合は、代わりに UNRESTORABLE と出力しなさい。

入力例 1

?tc????
coder

出力例 1

atcoder

条件1 を満たす文字列は atcoder, btcoder, ctcoder,..., ztcoder の 26 個がありますが、その中で最も辞書順で小さいものは atcoder なので、S=atcoder と特定できます。

入力例 2

??p??d??
abc

出力例 2

UNRESTORABLE

条件1を満たすような文字列 S が存在しないので、鍵となる文字列 S は存在しません。

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

回答

これも問題文を見ていると難しい感じがします。実際に私が今まで挑戦してきた過去問001,002,003よりもやっぱり難しくなっている気がしますね。

ですが、やはり問題Cです。さほど難しくないでしょう。

ポイント1 辞書順最小の文字列という記述から問題を読み解く

この辞書順最小の文字列という記述にどんな意味があるでしょうか？私はこの問題を解いているときになるほど！と思い、問題を作る人はすごいなぁと思いました。

この記述から

  • 残った?はすべてaに変えてね
  • 後方一致で調べてね

という事が分かりますね！たった一言でこの問題のアルゴリズムがほぼ決まってしまいます。素晴らしい！

あとはプログラムを実装するだけですね。

ポイント2 ?は正規表現の予約文字

予約文字という表現が正しいのかわかりませんが、正規表現では?は特別な意味を持つ記号です。String::replaceAllで置換してあげるときにエスケープしてあげる必要があります。しかも、エスケープ文字である\もまた、Javaではエスケープしなくてはいけません。

return new String(tmp).replaceAll("\\?", "a");

24行目のように\を2回入力してあげましょう。

成績

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

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

D - AtCoder Express

問題

配点：400 点

問題文

2168年、AtCoder 社は成長し、ついに "AtCoder特急" という鉄道を建設することを決めた。

さて、社長の高橋君は、"AtCoder特急" の列車を以下のように運行することを計画した。

  • 列車の走行時間は、(t1+t2+t3+…+tN) 秒である。
  • 最初の t1 秒間は、列車は速度 v1 m/s 以内で走っていなければならない。また、次の t2 秒間は、列車は速度 v2 m/s 以内で走っていなければならない。 次の t3 秒間、またそれ以降についても同様である。
  • 最後の tN 秒間は、列車は速度 vN m/s 以内で走っていなければならない。

ただし、列車の性能上、加速度は ±1m⁄s2 以内でなければならない。また、走行開始時と走行終了時には列車は止まっていなければならない。

列車が発車してから停車するまでに走れる最大の距離を求めなさい。

制約

  • 1≤N≤100
  • 1≤ti≤200
  • 1≤vi≤100
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。 

N
t1 t2 t3 … tN
v1 v2 v3 … vN

出力

列車が発車してから停車するまでに走ることのできる最大の距離を出力しなさい。ただし、絶対誤差が 10−3 以内であれば、正解となります。

入力例 1

1
100
30

出力例 1

2100.000000000000000

  • 最初の 30 秒は、加速度を 1m⁄s2 にし、加速します。その間に列車は 450m 走ります。
  • 次の 40 秒は、速度 30m⁄s を保ちます。その間に列車は 1200m 走ります。
  • 最後の 30 秒は、加速度を −1m⁄s2 にし、減速します。その間に列車は 450m 走ります。

合計で、450 + 1200 + 450=2100m 走ることができます。

入力例 2

2
60 50
34 38

出力例 2

2632.000000000000000

  • 最初の 34 秒は、加速度を 1m⁄s2 にし、加速します。その間に列車は 578m 走ります。
  • 次の 26 秒は、速度 34m⁄s を保ちます。その間に列車は 884m 走ります。
  • 次の 4 秒は、加速度を 1m⁄s2 にし、加速します。その間に列車は 144m 走ります。
  • 次の 8 秒は、速度 38m⁄s を保ちます。その間は列車は 304m 走ります。
  • 最後の 38 秒は、加速度を −1m⁄s2 にし、減速します。その間に列車は 722m 走ります。

合計で、578 + 884 + 144 + 304 + 722=2632m 走ることができます。

入力例 3

3
12 14 2
6 2 7

出力例 3

76.000000000000000

  • 最初の 6 秒は、加速度を 1m⁄s2 にし、加速します。その間に列車は 18m 走ります。
  • 次の 2 秒は、速度 6m⁄s を保ちます。その間に列車は 12m 走ります。
  • 次の 4 秒は、加速度を −1m⁄s2 にし、減速します。その間に列車は 16m 走ります。
  • 次の 14 秒は、速度 2m⁄s を保ちます。その間は列車は 28m 走ります。
  • 最後の 2 秒は、加速度を −1m⁄s2 にし、減速します。その間に列車は 2m 走ります。

合計で、18 + 12 + 16 + 28 + 2=76m 走ることができます。

入力例 4

1
9
10

出力例 4

20.250000000000000000

  • 最初の 4.5 秒は、加速度を 1m⁄s2 にし、加速します。その間に列車は 10.125m 走ります。
  • 最後の 4.5 秒は、加速度を −1m⁄s2 にし、減速します。その間に列車は 10.125m 走ります。

合計で、10.125 + 10.125=20.25m 走ることができます。

入力例 5

10
64 55 27 35 76 119 7 18 49 100
29 19 31 39 27 48 41 87 55 70

出力例 5

20291.000000000000

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

回答

D問題ですね。私は本番中では解けませんでした。また、自力でやっても解けそうになかったので解説を見ました。

でもよくわかんなかったです(´;ω;｀)

正順に調査して加速・逆順に調査して減速を挟み撃ちするように求めることと、0.5ずつでマッピングすることまではなんとなく理解できたのですが、それ以上はさっぱりでした。

どうしたもんかな？と考えているとふと思いつきました。そうだ、関数で表現すればいいじゃん！せっかくJava8で追加されたんだしいけるいける！

となりました。

大体のアルゴリズム

1.最大速度を関数として追加する

i区間ごとの最大速度viをグラフ関数として追加します。

{ \displaystyle{ f(x) = v_i (0 \leq dx \leq t_i)}}

{ \displaystyle{ dx = x - \sum_{j=0}^{i-1}t_j}}

ですね。ソースコードでは25行目からの部分です。

グラフにすると単なる横棒の関数です。

2.正順に調査し、加速を関数として追加する

i区間で最大速度-現在速度が正ならば、加速させる必要があります。

{ \displaystyle{ f(x) = dx + speed (0 \leq dx \leq t_i)}}

{ \displaystyle{ dx = x - \sum_{j=0}^{i-1}t_j}}

こんな感じですね。

{ \displaystyle{ y = x + b}}

の様な傾き1の簡単な関数ですね。

3.逆順に調査し、加速（減速）を関数として追加する

i区間で最大速度-現在速度が正ならば、加速（減速）させる必要があります。

{ \displaystyle{ f(x) = dx + speed (0 \leq dx \leq t_i)}}

{ \displaystyle{ dx = \sum_{j=0}^{i}t_j - x}}

逆順調査の時だけ、dxの計算が違いますのでご注意を。傾き-1の簡単な関数です。

4.全ての関数をまとめる

全ての関数をまとめます。関数をグラフにするとこんな感じです。

関数をまとめるとこのようになります 関数をまとめるとこのようになります 関数をまとめるとこのようになります 関数をまとめるとこのようになります 関数をまとめるとこのようになります

橙色が最大速度の関数(1)、黄色が正順調査の加速関数(2)、灰色が逆順調査の加速（減速）関数(3)です。

5.全ての関数の中で最小の値をマッピングする

集めた関数の中で最小の値を配列に入れましょう。公式解説によると、0.5ごとにマッピングすればよいとのことです。

マッピングをグラフにするとこんな感じです。

まとめた関数の最小値を示すとこのようになります

まとめた関数の最小値を示すとこのようになります

まとめた関数の最小値を示すとこのようになります

まとめた関数の最小値を示すとこのようになります

まとめた関数の最小値を示すとこのようになります

青色の部分が最小の値ですね。

6.面積を台形の公式を使って求める

マッピングした配列から台形の公式を使って面積を求めましょう。回答に必要なのは移動した距離です。

距離(m) = 速度(m/s)×時間(s)

ですね。つまり、面積が距離になるわけです。

台形の公式は

面積 = (上底＋下底）×高さ÷2

ですね！懐かしい！

{ \displaystyle{ T = \sum_{i=0}t_i}}

{ \displaystyle{ S = \sum_{x=1}^{2T}(f_{min}(\frac{x-1}{2}) + f_{min}(\frac{x}{2}))*0.5/2}}

{ \displaystyle{ S = \frac{1}{4}\sum_{x=1}^{2T}(f_{min}(\frac{x-1}{2}) + f_{min}(\frac{x}{2}))}}

ポイント DoubleFunctionとOptionalDoubleを使い関数を表現する

Java8から追加されたDoubleFunction1インターフェースとOptionalDouble2クラスをうまく使うことで、関数を表現しました。

DoubleFunctionインターフェースを使うことで動的に関数を生成できます。

また、OptionalDoubleクラスは値が含まれていない可能性を考慮してくれるもので、Optional.empty()のように値がない状態を明示して返すことができます。

また、ifPresentやisPresentなどの条件メソッドも標準であるので便利です。

成績

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

実行時間 メモリ使用量
390 ms 49440 KB

うーん…厳しいですね… ACできればOKという事で。なんだかぐちゃぐちゃなプログラムになってしまいましたが、独自性は抜群なのではないでしょうか？(開き直り) こんな面倒な方法取る人いないでしょう…(´;ω;｀)

まとめ

難しかったですが、最終的にはすべてACできてよかったです。本当ならば本番中にすべてクリアしたいですが、まだまだ難しそうですね。

頑張っていきたいと思います。

今回はCの問題が考えててとても楽しかったです。Cのような問題にまた出会いたいですね。

終わりに

ここまで読んでくださってありがとうございます！

AtCoderの復習もようやく終わりました。と思いきや？

今月の予定がびっしりと！

今週末から三週連続でABCがあるようです。頑張っていきたいと思います。

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

またね('ω')ノ

  1. DoubleFunction (Java Platform SE 8)↩

  2. OptionalDouble (Java Platform SE 8)↩

画面上に常に画像を表示させる方法

はてなブログ プログラミング

こんにちは鬱太郎です。昨日書いた記事

www.neetaro.com

で画面の左上や左下に画像を常時表示させてみました。その方法があまりにも簡単だったため、記事にしてご紹介したいと思います。

スマホなど画面が小さい方は申し訳ありません。画面がうるさいですが、少し許してください...お願いします！

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

画面上に何かを常時表示させる

画面上に何かを常時表示させる場合はJavaScriptなどのプログラム技術は一切いりません。多少のHTMLコードをかける知識（コピペ等で十分）があれば大丈夫です！

基本はこれposition:fixedを使用していきます。

<div sylte="position:fixed; 位置指定">

</div>

です。これで常時表示させたい要素を囲むだけでOKです！

位置指定には

  • top
  • bottom
  • left
  • right

という上下左右から何ピクセルという指定方法があります。

実装例

画面左上に画像を常時表示させる

HTMLコードの場合（そのまま記法など）はHTML閲覧ページから、画像を表示しているタグ<img>を見つけ、それをdivで囲みましょう。

<div style="position:fixed; top:50px; left:0px;">
 <img class="hatena-fotolife" width="50px" title="f:id:neet-utsu-taro:20171031222939p:plain" src="https://cdn-ak.f.st-hatena.com/images/fotolife/n/neet-utsu-taro/20171031/20171031222939.png" alt="f:id:neet-utsu-taro:20171031222939p:plain" />
</div>

Markdown記法の場合は特に簡単で、はてな記法の画像表示部分を<div>で囲むだけです。

<div style="position:fixed; top:50px; left:0px;">
[f:id:neet-utsu-taro:20171031222939p:plain:w50]
</div>
f:id:neet-utsu-taro:20171031222939p:plain:w50

topやleft等を指定をしないと、親の位置を元に初期値が決まります。

左下に読者登録ボタンを常時表示する

勿論、画像の部分を他のものに変えることもできます。文章だったり、読者登録ボタンだったり...

という事で、読者登録ボタンを左下に常時表示させてみましょう。読者登録ボタンは設定->詳細設定ページからコピペできます。

<div style="position:fixed; bottom:0px; left:0px;">
<iframe src="https://blog.hatena.ne.jp/neet-utsu-taro/neet-utsu-taro.hatenablog.jp/subscribe/iframe" allowtransparency="true" frameborder="0" scrolling="no" width="150" height="28"></iframe>
</div>

はい。左下に読者登録ボタンが見えているかと思います。

応用編

マウスオーバーした時のアクションを消したい

ブログのテーマ等の影響で、画像ファイル等にマウスカーソルを合わせた場合にいろいろなアニメーションが表示されることがあります。

それを消したい場合は、pointer-events: none;を追加しましょう。

<div style="position:fixed; top:120px; left:0px; pointer-events:none;">
 <img class="hatena-fotolife" width="50px" title="f:id:neet-utsu-taro:20171031222939p:plain" src="https://cdn-ak.f.st-hatena.com/images/fotolife/n/neet-utsu-taro/20171031/20171031222939.png" alt="f:id:neet-utsu-taro:20171031222939p:plain" />
</div>
f:id:neet-utsu-taro:20171031222939p:plain

画面の左上の1番目が、何もしてないものです。2番目がpointer-events:none;を追加した画像です。マウスを使づけても影が表示されず、タイトル（ID）も表示されません。

完全に背景としたい場合はおすすめです。ただ、読者登録ボタンなどのクリックしてアクションをするものと組み合わせる場合はそちらのアクションも停止させる恐れがあるため、注意が必要です。

真ん中に表示させる

中央揃えで表示させたい場合はまず表示させたい要素のサイズを調べる必要があります。表示させたいもののサイズが分からない場合は難しいので今回は省きます。

今回表示させたいのは画像幅50pxのものです。

左右に対して中央に表示させたい場合は、left:50%; margin-left:-25pxという風にします。

<div style="position:fixed; bottom:0px; left:50%; margin-left:-25px; pointer-events:none;">
 <img class="hatena-fotolife" width="50px" title="f:id:neet-utsu-taro:20171031222939p:plain" src="https://cdn-ak.f.st-hatena.com/images/fotolife/n/neet-utsu-taro/20171031/20171031222939.png" alt="f:id:neet-utsu-taro:20171031222939p:plain" />
</div>
f:id:neet-utsu-taro:20171031222939p:plain

margin-left: -○

○は幅/2ですね。

上下に対して中央に表示させたい場合も同じです。高さが68pxのため、margin-top:-34px;にしています。

<div style="position:fixed; right:0px; top:50%; width:60px; margin-top:-34px;">
<p style="font-size:10px;">いつも見ていただき、ありがとうございます！</p>
</div>

こんな感じですね。

いつも見ていただき、ありがとうございます！

要素のサイズを調べるには

要素のサイズといってもどんくらいの大きさかわからない！という方はブラウザのデベロッパーツールをお勧めします。

chromeの例：

調べたい要素を右クリックし、検証を選択します。

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

すると、下のように要素の範囲を色付けし、詳細な情報を見ることができます。

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

左下の読者登録ボタンのdivは幅150px高さ36pxですね。

動かないといった場合は

うまく表示されない場合は、

  • HTMLのタグが完全に閉じられていない
  • styleやposition、fixed等のスペルミス
  • style="..."が正しいが、style="...という風になっている
  • styleの記述を;区切りで行っていない

などが考えられます。

注意

この手法は、ウィンドウのサイズや見ているユーザーの機種に関係なく表示させるものです。例えばスマホなどの画面が小さいものでも左上や左下に表示させてしまいます。

そういった場合分けを考慮すると、CSSやJavaScript等で動的に場合分けする必要があります。

ただ、特に何も考えずに表示したい場合はこの手法でOKです。

終わりに

ここまで読んでくださってありがとうございます！

ハロウィンやクリスマスなどのイベントの記事にこういった飾りつけをしてみてはいかがでしょうか？

ぜひ試してみてくださいね！

またね('ω')ノ

祝！ ブログ継続2か月目！ ありがとうございます！

月末まとめ はてなブログ その他
f:id:neet-utsu-taro:20171031222939p:plain:w100
f:id:neet-utsu-taro:20171031223725p:plain:w100

こんにちは鬱太郎です。今日はブログ継続2か月の節目です！2か月目のブログの活動をまとめて反省していきます。

ん？ハロウィン要素…？安心してください！画面の左上と左下に可愛いカボチャさんを映しておきますから大丈夫ですって…（スマホなどで目障りな方…すみません。）

カボチャさんを削除する場合はこちらをクリックorタップするとページをリロードするまで永遠に消えます…さらばカボチャさん…

それでは決算開始！

てっててってててー♪（ちゃららん♪） てーっててててててってっててー♪

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

ブログでの1か月

この1か月をブログに関することでまとめてみました。

ダッシュボードで見てみる

10月末のダッシュボードを見て

継続日数63日(*'ω'*)ホクホク

10月の実績は

名目 値 9月分 先月分との差
アクセス数 4053 4605 552
投稿数 30 34 4
コメント数 4 6 2
総スター数 979 282 697
読者数 75 71 4
総ブックマーク数 112 34 78

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

アクセス数は若干落ちてますが、十分です！十分です！

何より、2か月間継続できたことがよい！お休み2回使ってしまったのは内緒...

ブログに訪問してくださった方々、スター、ブックマーク等を下さった方々、読者登録してくださった方々のおかげでここまで続けられました。ありがとうございます！

AtCoderにはまったよ

今月はAtCoderにはまった1か月でした。

記事のほとんどがそれに関することでしたね。

ようやくブログのタイトル通りの記事になってきました。

来月の目標

  • 忘れられたAndroid君を開発する
  • AtCoderのレートを上げる
  • 継続を3か月に伸ばす

終わりに

ここまで読んでくださってありがとうございます！

スターやブックマーク、読者登録等いつもありがとうございます！おかげさまで2か月継続できました

本当にありがとうございます！

可愛いカボチャさんの画像はhttp://frame-illust.com/?p=4140さんのものを使わせてもらいました。ありがとうございます。

来月もよろしくお願いします。

またね('ω')ノ

AtCoderの本番に初挑戦したよ！

AtCoder プログラミング

こんにちは鬱太郎です。昨日の21時からAtCoderの生コンテストに参加しまてきました！そのことについて記事にしたいと思います。

AtCoderとは

プログラミングコンテストの一つです。問題が日本語であることが英語のできない私にとってとても大きな特徴です。

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

http://atcoder.jp/

ルール

決められた制限時間の中で問題を解きます。問題はA-Dの4問あります。

問題には点数がつけられてます。難しい問題ほど配点が高くなっています。

今回私が挑戦したBeginner Contest 076は制限時間が100分、配点がA:100,B:200,C:300,D:400でした。全問正解で1000点ですね。

また、同点数の場合は正答した時間で順番が決まります。また、誤答するとペナルティもあるため、回答速度と回答精度の両方が求められます。

結果

本番は初めてでした。

めっちゃ緊張したー_(:3」∠)_

しかも当たり前と言えば当たり前ですが、過去問でやってた初期の問題よりもそれぞれが若干難しくなってましたね。

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

4問中3問正解！600点GETです！ 過去問でも3問目まではらくらく解けていたので、本番も練習と同じ実力が出せてよかったです。

緊張もあってか2問目3問目でしばらくフリーズしていましたｗ文章読んでも頭の中に入ってこない状態でしたが、過去問を数回解いたおかげで何とか解けました。

過去問を繰り返しやっていると、大体ABCDの問題の各難易度が分かってきます。

Bの問題は絶対難しくない！初心者でも解けるやつ！

Cの問題は高度なアルゴリズムは不要！

という風に自分に言い聞かせられたので、うまく解法にたどり着けたと思います。

いきなりやってたらCは解けなかったかも…

順位

そして、順位は

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

387位でした！問題を回答していたのが1145人でした。1000点満点の方は141人でした。1000点回答の方たちに加われるように頑張っていきたいです。

参加人数 1000点 私の順位
1145人 141人 387位

私と同じ600点の方でも、240人の方は私よりも早く問題を解いたという事ですね。凄い…

レート

AtCoderに参加したので、私にレートが付きました！(*'ω'*)

レート:159

まだ始めたばかりで低いのでしょう。レートランキングは7244位です。これも徐々に上げていきたいですね。

AtCoderのマイページにレートのグラフがあったので、サイドメニューにコピペしてみました。ちっこくてかわいいですね('ω')

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

終わりに

昨日はとても楽しかったです。大会終了後は興奮して少し眠れませんでした。これから昨日の問題の解けなかった部分に挑戦してみたいと思います。

ここまで読んでくださってありがとうございます！

スター、ブックマーク、読者登録等いつもありがとうございます！とても嬉しいです！

そろそろ10月も終わりですね…

ん？ハロウィン？

ニートにハロウィンなんて関係ないんだよぉ…！現実から逃げて妄想という名の仮装をしているニートなんていつもハロウィン状態でしょ…(´;ω;｀)もう、魑魅魍魎状態よ！

冷静に考えるとニートって身だしなみ整えないままハロウィン会場に行ったらゾンビかなんかの仮装としていけるかも…？いや、無理か…

またね('ω')ノ

今日は包除原理について少し勉強したよ

プログラミング その他

昨日やったABC003-dの問題の解説で包除原理を使うという事を目にしたので、今日は包除原理について少し勉強しました。といっても記事にできる事は何もないのですが( ;∀;)

個人的なメモです。

www.neetaro.com

これのD問題のラスト1点部分について

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

求めたいもの（灰色）は

|U|-白色の部分

なんですけど、白色の部分が、

それぞれ円の和 - 2つの円の共通部分の和 + 3つの円の共通部分の和 - 4つの円の共通部分の和

これで求められるらしいんですよね。記号で表すと、

  |T| + |R| + |B| + |L|  //それぞれの円の和
-(|T∩R| + |R∩B| + |B∩L| + |L∩T|)  //2つの円の共通部分
+(|T∩R∩B| + |R∩B∩L| + |B∩L∩T| + |L∩T∩R|) //3つの円の共通部分
- |T∩R∩B∩L|   //4つの円の共通部分

です。多分。

この理論でプログラムを実装してみたんですけど、一向に正答しないんですよね。

プログラムの実装の仕方でミスしてるのか、そもそもこの考えが間違っているのかわからなくて悩んでます。

しばらく棚上げですかね。

終わりに

ここまで読んでくださってありがとうございます！

今日はAtCoderのコンテストがあるため記事は簡略で早めに終わろうと思います。

機能やった問題を完答させることはできませんでしたが、しばらく寝かしておきます。もしかしたら、未来の成長した私が見事解いてくれるかも？(*'ω'*)

スター、ブックマーク、読者登録ありがとうございます！ものすごく励みになっています！そういえば豊田議員書類送検されたようですね

またね('ω')ノ

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↩