ABC226 茶色コーダーが解けたところまで

AtCoder Beginner Contest 226

ABC226の問題を、本番で自分が解けた所までの解説です。

Dまでで1時間切り。このペースを常に安定してアウトプットしたいものです。

A - Round decimals

Difficulty: 14

問題文

小数第三位までで表すことのできる実数$X$が、小数第三位まで入力されます。
$X$を小数第一位で四捨五入した結果として得られる整数を出力してください。

制約

• $0 \leq X < 100$
• $X$ は小数第三位までで表現可能である。
• $X$ は小数第三位まで与えられる。

考察

Xを四捨五入したい

• 堅実に条件分け
  • 小数点の1つ右にある数字が0~4なら…
    • 小数点より左の数字をそのまま出力
  • 小数点の1つ右にある数字が5~9なら…
    • 小数点より左の数字に1足したものを出力
• ライブラリとか使って一発で小数(float)から整数(int)へ四捨五入！ドン！
  • Pythonの場合は丸め誤差とか色々あるから要注意
    • 小数点以下が0.5の時、挙動が不安定になったりとかとか
      • 一応、$0.0005$を足すことで回避するなんていう小技もある

パターン1：堅実に条件分け

B - Counting Arrays

Difficulty: 192

問題文

$1$ から $N$ までの番号がついた $N$ 個の数列が与えられます。
数列 $i$ は、長さが $L_i$ で $j (1 \leq j\leq L_i)$ 番目の要素が $a_{i,j}$であるような数列です。
数列 $i$ と数列 $j$ は、 $L_i=L_j$かつすべての $k (1 \leq k \leq L_i)$に対して $a_{i,k}=a_{j,k}$が成り立つ時に同じであるとみなします。 同じ数列は $1$ 種類として数えるとき、数列 $1$ から数列 $N$ の中に全部で何種類の数列がありますか？

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq L_i \leq 2 \times 10^5(1\leq i \leq N)$
• $0 \leq a_{i,j} \leq 10^9 ( 1\leq i \leq N, 1 \leq j \leq L_i)$
• すべての数列の要素の個数の和、すなわち $\sum_{i=1}^{N} L_i$は$2 \times 10^5$を超えない。
• 入力は全て整数である。

数列の比較？なんか問題文難しいね？

• 実際公式放送でも難しい話してる
  • ハッシュテーブルとか平衡二分探索木とか…
• $L$(長さ)も含めて全部一括で文字列として見てあげて、setに突っ込んでいけば重複排除できる…！（力技）

C - Martial artist

Difficulty: 539

グラフとして捉える

• 技$N$にを覚えるために必要な技は、$A_{N,1},A_{N,2}\dots A_{N,K_N}$
• ゲームのスキルツリー的なイメージで、Nから$A_{N,1},A_{N,2}\dots A_{N,K_N}$にそれぞれ辺を張る
  • 次は$A_{N,1},A_{N,2}\dots A_{N,K_N}$から、それらの技を覚えるために必要な技に辺を張って…
  • 繰り返すと、必要な技の一覧が出てきますね。後はBFSやDFSと同様の流れで、「$N$から到達可能な点」の技を覚えるのに必要な時間の和を求める

D - Teleportation

Difficulty: 706

問題文

AtCoder 国は無限に広がる直交座標の上にあります。 AtCoder 国には $N$ 個の街があり、 $1,2,…,N$ と番号が付けられています。街 $i$ は地点 ($x_i,y_i$)にあり、2 つの異なる番号の街が同じ座標にあることはありません。

AtCoder 国には転移魔法(以下、魔法と表記)があります。魔法は整数の組 ($a,b$) によって識別されていて、地点 ($x,y$) にいるときに魔法 ($a,b$) を使うと ($x+a,y+b$) にワープすることができます。

すぬけ君は、任意の整数の組 ($a,b$) を選んで魔法 ($a,b$) を覚えることができる大魔術師です。また、すぬけ君は何種類でも魔法を覚えることができます。 魔法を使って街と街の間を移動したくなったすぬけ君は、全ての相異なる街の組 ($i,j$) について次の行動を取れるようにいくつかの魔法を覚えることにしました。

覚えた魔法のうち $1$ 種類の魔法のみ を選ぶ。その後、選んだ魔法 のみ を繰り返し使って街 $i$ から 街 $j$ に移動する。 すぬけ君が上の条件を満たすように魔法を覚えるとき、少なくとも何種類の魔法を覚えればよいですか？

制約

• $2 \leq N \leq 500$
• $0 \leq x_i \leq 10^9(1 \leq i \leq N)$
• $0 \leq y_i \leq 10^9(1 \leq i \leq N)$
• $i \neq j$ならば$(x_i,y_i) \neq (x_j,y_j)$である。

考察

地点(0,0)から地点(x,y)に行く方法を考える

1. そのまま(x,y)の魔法を覚える
   • １回の魔法で地点(x,y)に行けるね
2. (x/2,y/2)の魔法を覚える
   • 2回の魔法で地点(x,y)に行けるね
   • 制約より、x,yともに２で割り切れる必要がある
     • (x/2,y/2)にも(x,y)にも行けるので汎用性が高い
3. (x/3,y/3)の魔法を覚える
   • 3回の魔法で地点(x,y)に行けるね
   • 制約より、x,yともに3で割り切れる必要がある
     • (x/3,y/3)にも(2x/3,2y/3)にも、(x,y)にも行けるので汎用性がもっと高い

$x$と$y$の最大公約数でそれぞれを割った魔法を覚えると汎用性が高く、覚える魔法が少なくて済みそう！

• $x$と$y$のどちらかが０の場合、条件分岐が必要
  • 0で割っちゃうようなことになっちゃいます

後は制約

• $N \leq 500$より、地点i,地点jを全探索O(N^2)でも余裕で間に合いますね