競プロ参戦記 第21回 「気温とあみだくじ」 ABC 113
競プロの大会に参加しました！ この参戦記では問題ごとに考察を書いていきます。
今週は ABC-only 回です。
AtCoder Beginner Contest 113
A - Discount Fare
問題概要：位置AからBに移動するのにX円かかり、BからCにはY円かかる。いま、BからCへの移動は半額になる。AからCへの移動にかかる金額を求めよ。
考察：BからCにかかる金額は Y / 2 円です。嬉しいことに Y は偶数とかかれているので、端数は気にしなくてかまいません。
実装： X + Y / 2
B - Palace
問題概要：N 個の地点の標高が与えられる。標高が h の地点の気温が T - 0.006 h であるとき、気温が A に最も近い地点を求めよ。
考察：気温が A に最も近いというのは、気温と A の差が最小であると言いかえられます。つまり、
D(h) = abs((T - 0.006 h) - A)として、各地点の D(h) を計算して最小になったものを答えればいいです。
実装：列の各要素について、それに関連する値が最小のものを探す、というのは定石なので、手順を解説します。
基本的な考えは、ループの各時点での「現時点での最小値」と「その最小値になった原因」を変数で持っておくことです。「現時点での最小値」を正しく更新していけば、最終的に全体としての最小値が得られて、「その最小値になった原因」が探している値であることになります。
地点ごとにループして、いま地点 i (標高 H[i]) をみているとします。この地点での気温差 D(H[i]) が「現時点で最小」かどうかを確認しましょう。
これがループのはじめ、つまり i = 0 なら最小です。オンリーワンならナンバーワン。
ループのはじめでなければ、「現時点での最小」といまの値を比較します。いまの値のほうが小さければ、最小値を更新します。
ループが終わった時点での最小値は本当に最小であり、この値を更新したときの i (地点の番号) が答えです。
C - ID
問題概要：県が N 個、市が M 個ある。市 i が誕生したのが Y(i) 年だと分かっている。県 P に属する市のなかで x 番目に誕生したものの認識番号を (P, x) とする。各市の認識番号を求めよ。ただし以下の点に注意。
- 市はどれか1つの県に属す。
- 1年に誕生する市は1つだけ。
- 市を含まない県もある。
考察：ある市が「その県において何番目に誕生したか」を効率よく計算するのが肝です。市を県ごとに分類しておき、誕生年についてソートするのが楽でしょう。
この問題はコードを見たほうが早いので、解答から抜粋しておきます。(コメントつき。iter を使わずに for で書いたほうが読みやすかったかも。)
let (N, M) = read!(usize, usize); // 入力の1行目を読む
// 県から市のリストへのマップ (のつもりの配列)
let mut pref = vec![vec![]; N + 1];
for i in 0..M {
let (p, y) = read!(usize, i64); // 入力を1行読む
pref[p].push((y, i)); // (年, 市の番号) を追加
}
let mut numbers = vec![]; // (市の番号, 認識番号) の配列
for p in 1..N + 1 {
pref[p].sort(); // 市を年でソート
numbers.extend( // 市のリストを変形して numbers に追加
pref[p]
.iter()
.enumerate()
.map(|(x, &(y, i))|
(i, format!("{:>06}{:>06}", p, 1 + x))),
);
}
numbers.sort(); // 市を市の番号でソート
for (_, n) in numbers { // 市の認識番号を出力していく
println!("{}", n)
}D - Number of Amidakuji
問題概要：H 段 W 列の「あみだくじ」がある。縦棒 1 から辿っていくと縦棒 K に行き着く。このような「あみだくじ」の個数を求めよ。(詳細は問題文を参照。)
考察：数え上げ問題です。雰囲気から察するに、DP で解けるでしょう、解けたらいいな、と思ったのでやってみたら解けました。これについてはあまりスマートな解説はできないので、考えたことを書いていきます。
ここでは、横棒を引ける水平線を「段」と呼び、縦棒を「列」と呼び、縦棒の間 (横棒を引けるところ) を「間隔」と呼びます。
こういう問題でよくあるのが、「前から X 個の選択肢を決めたと仮定して、次の1個の選択肢の決め方を考える」というやつです。今回では、上から Y 個の段に関して横線を引くか引かないかをすべて決めたと仮定して、次の段 (Y段目) の横棒を引く場合と引かない場合について考えます。
これではまだ計算できないので、Y 段目の左から X 個の間隔に横棒を引くか引かないかも決めたと仮定します。さて、Y 段目の X 個目の間隔に横棒を引く場合と引かない場合を考えましょう。
3 段 4 列のあみだくじ
0 1 2 3
0 |-*-|-*-|-*-|
1 |-*-| ? | |
2 | | | |
上から Y=1 段と、左から X=1 個の間隔に、
横棒を引くか否かを決めた (-*- の部分)。
Y 段目 X 列目 (? の部分) に横棒を引くか否かを考える。DP に載せるべき状態は何でしょうか。
最終的に「列 0 から辿った先」を知らなければいけないので、DP の状態として「いま何列目にいるか」を覚えておく必要があります。
また、横棒を横に2つ連続ではおけないという制約がありますから、左側に横棒が引かれているか否かを載せます。
したがって DP 表は次のようになりました。
dp[Y][X][z][b] = n ⇔
上から Y 段の横棒の有無は決まっている。
Y 段目の左から X 個の間隔の横棒の有無は決まっている。
この状態で列 0 から辿ると列 z に到達する。
Y 段 X 列の横棒からみて、左側の横棒を引いたなら b=1 、引いてないなら b=0。
このようなあみだくじの個数が n 。次に状態遷移を考えます。Y, X, z はループで全列挙です。
いまみている横棒を引くか否か決めた後の状態は、Y 段目の X+1 個の間隔の横棒を引いた後の状態なので、 dp[Y][X + 1][ ? ][ ? ] です。
横棒を引かないことにした場合、移動しないので z はそのまま、次の b は 0 です。つまり現時点での b の値によらず、dp[Y][X + 1][z][0] に遷移します。
b=0 なら横棒を引けるので、dp[Y][X+1][ ? ][1] に遷移できます。移動先の z の値は X, z からわかります。z 列にいる状態で z=X 列に横棒を引けば z=X+1 に変わり、z=X+1 列に横棒を引けば z=X に変わります。
さて、Y 段目の横棒について数え上げが終わったので次の段にいきます。段が変われば「左側の横棒」に関しては忘れていいので、 b=0, b=1 を合流させて、 dp[Y+1][0][z][0] を dp[Y][W-1][z][ * ] の和にします。
これをすべての段について繰り返せば数え上げられます。
おわりに
全完できました。
C, D ともに、いつもより考察が短い代わりに、実装が大変な回でした。解説を読むより、コードを読んだほうが分かりやすいかもしれません。
この記事が気に入ったらサポートをしてみませんか？