競プロ参戦記 #25 「クリスマス多次元バーガー」 ABC 115
今週も AtCoder プログラミングコンテストに参加したので、考察を書いていきます。先週と同じく ABC-only 回です。
## AtCoder Beginner Contest 115
問題一覧:
## A - Christmas Eve Eve Eve
問題概要：D=25 なら Christmas を、D=24 なら Christmas Eve を、 D=23 なら Christmas Eve Eve を、D=22 なら Christmas Eve Eve Eve を出力せよ。
考察：問題文の通りに if 文を連ねれば解けます。めんどくさいならループを使ってもいいです。
D = 25, 24, 23, 22 のそれぞれについて「Eve」の個数が 0, 1, 2, 3 個なのがポイント。つまり「Eve」は (25 - D) 個です。(25 - D) 回ループして Eve を足していく、というのをやれば解けます。
let mut s = "Christmas".to_owned(); // &str → String への変換
for i in 0..25 - D {
s += " Eve";
}
println!("{}", s);ところで、 Rust では文字列リテラル (&str 型) 同士を + でつなぐことができない点に注意です。コンパイルエラーとともに「to_owned を使ってはどうか？」というヒントが出ます。
上のコードでは to_owned によって文字列リテラル "Christmas" を String 型に変換しています。つまり、メモリを新たに確保して、そこに "Christmas" を書き込むということです。ここで確保されたメモリは可変な変数 s が独占的に所有するので書き換えが可能です。そして += で文字列の連結ができます。
ちなみに &str 型の値を + でつなげるようにすることは技術的には可能なはずなので、何らかの理由があって (おそらく望ましくない振る舞いを防ぐために) 実装していないんだと思います。
## B - Christmas Eve Eve
問題概要：N個の品物を購入する。もっとも価格が高いものだけ半額で購入するとき、合計の購入額を求めよ。
考察：もっとも高い価格をみつけて、その半額を合計から引けばいいです。
ループして最高額を探すのが模範的な回答です。
あるいは、価格の配列をソートする方法もあります。末尾に最大値が来るので、それ半分にして、合計を求めるという手順。計算量は無駄に悪くなりますが、コードが短くなるかもです。
## C - Christmas Eve
問題概要：N本の木からK本を選ぶ。選べる組み合わせのうち、「選ばれた木の高さの最大値と最小値の差」の最小値を求めよ。
考察：木の選びかたが数多あっても、「選ばれた木の高さの最小値」が N 通り以下しかない点に注目します。これを全列挙すると最大値が O(1) 時間で求まるのが今回のポイントです。具体的にはこうです。
いま高さ h の木を選んで、その高さが最小になるように残りの木を選ばなければならないとします。つまり、高さ h 未満の木は選びません。このとき「選ばれた木の高さの最大値と最小値の差」はどうでしょうか。 **最小値が固定されているのであれば、最大値が最小のときが最善** です。
最大値がもっとも小さくなるように選ぶには、低い木から順番に選んでいけばいいです。あらかじめ木を高さ順に並べておけば「下から K 本」。そのK本目が最大の高さになります。
したがって h ごとに最大値の候補は1つしかないので、差を計算して最小値を求めればOK。全体としては O(N) 時間です。
問題概要：関数 F を以下で定義する。文字列 F(N) の前から X 文字に含まれる "1" の個数を求めよ。(数学的な表現に置き換えています。)
1. F(0) = "1"
2. F(L) = "0" + F(L-1) + "1" + F(L-1) + "0" (L≥1)
考察：F(N) の文字数は16桁ぐらいなので、1文字ずつ数えるのは無理です。文字列は似たようなパターンの繰り返しなので、それをうまくスキップしながら数える、という方法で考えます。
試しに N が小さいケースで F(N) を計算してみます。読みやすさのためにカッコと空白を補っています。
F(1) = 01110 (5文字)
F(2) = 0 (01110) 1 (01110) 0 (13文字)
F(3) = 0 (0 01110 1 01110 0) 1 (0 01110 1 01110 0) 0 (29文字)一般に F(N) は 0, F(N-1), 1, F(N-1), 0 という5層構造です。F(N-1) の長さは事前に計算しておけば分かります。そのため、 X がどのあたりを指しているかは、数回の比較で判定できます。場合分けを考えてみると以下のような感じです。
1. 最初の 0 の前後 (X≤1) なら明らかに 0 です。
2. 最後の 0 の前後なら F(L) 全体に含まれる "1" の個数が答えになります。これは事前に計算しておけばOK。
3. 1 ≤ X < 1 + |F(L-1)| なら F(L-1) の途中です。「F(L-1) の前から X 文字に含まれる "1" の個数」を計算することになります。つまり、関数の再帰呼び出しをするだけでOK。L の値が小さくなるので、この再帰はいつか停止します。
4. 中央の 1 の前であるケース: (F(L-1) に含まれる 1 の個数)
5. 中央の 1 の後であるケース: (F(L-1) に含まれる 1 の個数) + 1
6. 2つ目の F(L-1) の途中であるケース: 3. と同様
解けることが分かったので実装を考えます。上記のように X の値で場合分けするより、文字列を前から読みながら「1の個数」を数えていくほうが楽です。ただし X=0 になった時点で終わりにします。
1. "0" を読み飛ばす (Xを1減らす)
2. X < |F(L-1)| なら再帰呼び出しして終了。X ≥ |F(L-1)| なら F(L-1) 全体を読み飛ばして (Xを|F(L-1)|だけ減らして)、「1の個数」を加算する
3. "1" を読み飛ばす (Xを1減らす)。「1の個数」を増やす
4. X < |F(L-1)| なら再帰呼び出しして終了。X ≥ |F(L-1)| なら F(L-1) 全体を読み飛ばして (Xを|F(L-1)|だけ減らして)、「1の個数」を加算する
5. "0" を読み飛ばす (Xを1減らす)
これで間に合うでしょうか。再帰呼び出しにかかる時間を除けば、計算量は O(1) です。再帰の深さは最大 N なので、再帰呼び出し全体として O(N) 時間です。
おわりに
全完でした。D は再帰下降パーサーを書くのと似た感覚で書けるので、構文解析をやったことがある人にはボーナスでしたね。
今回は問題概要の書きかたを少し変えました。C問題の問題概要はどっちが分かりやすいでしょうか。
1. N本の木からK本を選ぶ。選べる組み合わせのうち、「選ばれた木の高さの最大値と最小値の差」の最小値を求めよ。
2. N本の木がある。K本を選んだ。選ばれた最も高い木と、最も低い木の差は、あらゆる選びかたで最小だった。このときの高さの差を求めよ。
この記事が気に入ったらサポートをしてみませんか？