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

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

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

こんにちは鬱太郎です。先週の土曜日に開催された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 回の操作後の、電光掲示板に書かれている整数として考えられる最小の値を求めなさい。

制約

  • 1N,K10
  • 入力はすべて整数である

入力

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

N
K

出力

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


入力例 1

4
3

出力例 1

10

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


入力例 2

10
10

出力例 2

76

高橋君は、操作 A, A, A, A, B, B, B, B, B, B の順にやると、整数を最小化できます。この時、電光掲示板に書かれている整数は 124816263646566676 と変わり、最終的に 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' を見つけ、これは文字列 S0 個以上 |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,..., ztcoder26 個がありますが、その中で最も辞書順で小さいものは 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 以内で走っていなければならない。

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

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

制約

  • 1N100
  • 1ti200
  • 1vi100
  • 入力はすべて整数である

入力

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

N
t1 t2 t3tN
v1 v2 v3vN

出力

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


入力例 1

1
100
30

出力例 1

2100.000000000000000

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

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


入力例 2

2
60 50
34 38

出力例 2

2632.000000000000000

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

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


入力例 3

3
12 14 2
6 2 7

出力例 3

76.000000000000000

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

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


入力例 4

1
9
10

出力例 4

20.250000000000000000

  • 最初の 4.5 秒は、加速度を 1ms2 にし、加速します。その間に列車は 10.125m 走ります。
  • 最後の 4.5 秒は、加速度を −1ms2 にし、減速します。その間に列車は 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()のように値がない状態を明示して返すことができます。

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

成績

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

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

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

まとめ

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

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

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

終わりに

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

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

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

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

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

またね('ω')ノ