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

こんにちは鬱太郎です。先週の土曜日に開催された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特急" の列車を以下のように運行することを計画した。
列車の走行時間は、(t₁+t₂+t₃+…+t_N) 秒である。
最初の t₁ 秒間は、列車は速度 v₁ m/s 以内で走っていなければならない。また、次の t₂ 秒間は、列車は速度 v₂ m/s 以内で走っていなければならない。次の t₃ 秒間、またそれ以降についても同様である。
最後の t_N 秒間は、列車は速度 v_N m/s 以内で走っていなければならない。
ただし、列車の性能上、加速度は ±1m⁄s² 以内でなければならない。また、走行開始時と走行終了時には列車は止まっていなければならない。
列車が発車してから停車するまでに走れる最大の距離を求めなさい。
制約
1≤N≤100
1≤t_i≤200
1≤v_i≤100
入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N
t₁ t₂ t₃ … t_N
v₁ v₂ v₃ … v_N
出力
列車が発車してから停車するまでに走ることのできる最大の距離を出力しなさい。ただし、絶対誤差が 10⁻³ 以内であれば、正解となります。
入力例 1
1
100
30
出力例 1
2100.000000000000000
最初の 30 秒は、加速度を 1m⁄s² にし、加速します。その間に列車は 450m 走ります。
次の 40 秒は、速度 30m⁄s を保ちます。その間に列車は 1200m 走ります。
最後の 30 秒は、加速度を −1m⁄s² にし、減速します。その間に列車は 450m 走ります。
合計で、450 + 1200 + 450=2100m 走ることができます。
入力例 2
2
60 50
34 38
出力例 2
2632.000000000000000
最初の 34 秒は、加速度を 1m⁄s² にし、加速します。その間に列車は 578m 走ります。
次の 26 秒は、速度 34m⁄s を保ちます。その間に列車は 884m 走ります。
次の 4 秒は、加速度を 1m⁄s² にし、加速します。その間に列車は 144m 走ります。
次の 8 秒は、速度 38m⁄s を保ちます。その間は列車は 304m 走ります。
最後の 38 秒は、加速度を −1m⁄s² にし、減速します。その間に列車は 722m 走ります。
合計で、578 + 884 + 144 + 304 + 722=2632m 走ることができます。
入力例 3
3
12 14 2
6 2 7
出力例 3
76.000000000000000
最初の 6 秒は、加速度を 1m⁄s² にし、加速します。その間に列車は 18m 走ります。
次の 2 秒は、速度 6m⁄s を保ちます。その間に列車は 12m 走ります。
次の 4 秒は、加速度を −1m⁄s² にし、減速します。その間に列車は 16m 走ります。
次の 14 秒は、速度 2m⁄s を保ちます。その間は列車は 28m 走ります。
最後の 2 秒は、加速度を −1m⁄s² にし、減速します。その間に列車は 2m 走ります。
合計で、18 + 12 + 16 + 28 + 2=76m 走ることができます。
入力例 4
1
9
10
出力例 4
20.250000000000000000
最初の 4.5 秒は、加速度を 1m⁄s² にし、加速します。その間に列車は 10.125m 走ります。
最後の 4.5 秒は、加速度を −1m⁄s² にし、減速します。その間に列車は 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