狠狠撸

狠狠撸Share a Scribd company logo

CODE FESTIVAL 2015 予選B 解説

?
?
A
AtCoder Inc.

CODE FESTIVAL 2015 予選B 解説

1 of 21
Download to read offline
CODE FESTIVAL 2015 予選B 解説 AtCoder株式会社 代表取締役 高橋 直大 2015/10/25 1
A問題 ?解説 「ダブル?文字列列」 CODE ?FESTIVAL ?2015 ?予選B
問題概要 ?? “2015/10/25” ?のように、各?文字が２度度ずつ現れる?文字 列列を「ダブル?文字列列」と呼ぶことにする ?? ?小?文字アルファベットからなる?文字列列 ?S ?が与えられる ?? S ?に含まれる?文字を全て含むダブル?文字列列を１つ出?力力し なさい ?? 例例 –? “no” ?→ ?“noon”（“onno”, ?“lemonmelon” ?なども可） –? “meat” ?→ ?“teammate”
解法１ ?? ?文字列列 ?S ?を、標準?入?力力から?入?力力する ?? ?文字列列 ?S ?を２回標準出?力力に出?力力する ?? 例例 –? “no” ?→ ?“nono” –? “meat” ?→ ?“meatmeat” –? “z” ?→ ?“zz” ?? 注意点 –? ２回の出?力力の間にスペースや改?行行などを?入れないこと –? 末尾に改?行行を出?力力するのを忘れないこと
解法２ ?? ?入?力力が何であろうと 全ての?小?文字アルファベットを２回ずつ出?力力する ?? 例例 –? “no” ?→ ?“aabbccddee?gghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz” –? “meat” ?→ ?“aabbccddee?gghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz” ?? 注意点 –? 抜けた?文字や、３回以上現れる?文字がないようにすること –? プログラムを書いて?文字列列を?生成するとより安全
B問題 解説 「採点」 CODE FESTIVAL 2015 予選B
問題概要 ? N 人の答えの採点をする ? それぞれの人の答えは 0 以上 M 以下の整数 ? 正解を忘れてしまった ? 過半数の人が同じ答えならそれを正解とする ? 正解を決められるなら正解を、決められないなら「?」 を出力せよ ? 制約 – 1 ≦ N ≦ 105 – 1 ≦ M ≦ 105
40点解法 ? 部分点制約 – N ≦ 100, M ≦ 100 ? 解法 – 0 から M まで正解を仮定する – 過半数の人が正解を答えているか調べる ? 計算量 – O(NM)
満点解法 ? 解法 – M+1 要素の配列を用意し、それぞれの答えが何回答えられたか を数える – それぞれの答えが過半数かを調べる ? 計算量 – O(N+M)
C問題 解説 「旅館」 CODE FESTIVAL 2015 予選B
問題概要 ? N 部屋の旅館を経営している – それぞれの部屋の定員は Ai 人 ? M 組の予約がある – それぞれの予約の人数は Bi 人 ? ひとつの予約にひとつの部屋を割り当てる ? 定員が予約人数を下回ってはならない ? すべての予約に部屋を割り当てられるか判定せよ ? 制約 – 1 ≦ N ≦ 105 – 1 ≦ M ≦ 105 – 1 ≦ Ai ≦ 105 – 1 ≦ Bi ≦ 105
60点解法 ? 部分点制約 – N ≦ 100, M ≦ 100 ? 解法 – 一番人数の多い予約に一番定員の多い部屋を割り当てればよい ? それより人数の少ない予約に割り当てて大丈夫なら、一番人数の多 い予約と交換しても大丈夫 – 予約人数の多い順に、大きい部屋を割り当てる ? 計算量 – O((N+M)M)
満点解法 ? 解法 – 部分点解法で、先にソートしておく ? 計算量 – O(N log N + M log M)
D問題 ?解説 「マスと駒と?色塗り」 CODE ?FESTIVAL ?2015 ?予選B
問題概要 ?? ?白いマスがたくさん並んでいる ?? N ?個の駒がある ?? N ?回の操作を?行行い、i ?回?目の操作では、 –? 駒 ?i ?をマス ?Si ?に置く –? 「駒 ?i ?のあるマスが?白なら塗り、?黒なら次のマスに駒を移動」 を繰り返し、新たに塗ったマスが ?Ci ?個になったら終了了 ?? という操作を?行行う ?? 操作終了了後の各駒の位置を求めよ ?? 制約 –? 1 ?≦ ?N ?≦ ?105 –? 1 ?≦ ?Si ?≦ ?109 –? 1 ?≦ ?Ci ?≦ ?109
35点解法 ?? 部分点制約 –? 操作終了了後に駒のあるマスの番号は ?105 ?を超えない ?? マスを塗る回数の合計は ?105 ?回以下となる ?? 解法 –? 駒の動かし?方を、 ?? 今のマスから右にある最も近い?白マスに移動して?黒く塗る –? と考えてシミュレーションを?行行う –? 「最も近い?白マス」を?高速に?見見つけられれば良良い –? 以下のような、いくつかの?方法がある ?? setで?白マスの場所を管理理しておき、lower_?boundで「番号が ?x ?以 上のうち最も?小さいもの」を?見見つける（c++） ?? 上の?方法で、setの代わりに ?RMQ（Range ?Minimum ?Query）に 対応した ?segtree ?を?用いる ?? 次のページに?示したような?方法を使う
35点解法 ?? 以下のようなコードでも ?35 ?点を得ることができる import ?sys ? sys.setrecursionlimit(1024*1024) ? N ?= ?int(raw_input()) ? state ?= ?[-?‐1] ?* ?100001 ? def ?find_next(i): ? ? ?if ?d[i] ?== ?-?‐1: ?return ?i ? ? ?d[i] ?= ?find_next(d[i]) ? ? ?return ?d[i] ? for ?i ?in ?xrange(N): ? ? ?s,c ?= ?map(int,raw_input().split()) ? ? ?for ?j ?in ?xrange(c): ? ? ? ? ?s ?= ?find_next(s) ? ? ? ? ?d[s] ?= ?s+1 ? ? ?print ?s ※ ?言語はpythonです ← 再帰の深さ制限の対策 ← 「最も近い?白マス」を ?　 ??見見つける関数 ← シミュレーションを?行行って ?　 ?答えを求めるループ
35点解法 ?? 「最も近い?白マス」を?見見つける関数について ?? d[i] ?が ?-‐??1 ?のとき、マス ?i ?が?白であることを表します ?? そうでないときは、マス ?i ?よりも右でかつ、「最も近い ?白マス」よりも右でないマスの番号を表します –? そのままでは再帰の呼び出し回数が膨?大でTLEしてしまいます –? そこで、d[i] ?= ?find_next(d[i]) ?というように?高速化します ? ?? Union-?‐Find ??木の?高速化と同様の?手法 ? ?? ならし計算量量は ?O(log(N)) ?となります ? ?? Union-?‐Find ??木を?用いていると考えても良良いです ? def ?find_next(i): ? ? ?if ?d[i] ?== ?-?‐1: ?return ?i ? ? ?d[i] ?= ?find_next(d[i]) ? ? ?return ?d[i]
40点解法 ?? 部分点制約 –? N ?≦ ?1000 ?? 解法 –? ?黒く塗った区間を管理理する –? 以下をそれぞれ ?O(区間の個数) ?で求められる ?? あるマスから右にある最も近い?白マス ?? あるマスから右にある最も近い?黒マス –? このような区間への質問を解説上では「RQ」と呼ぶことにする –? ただし、隣隣り合った２つの区間は併合しておくこと ?? 計算量量 –? １回の操作での区間の個数の増減は、定数 ?-‐?? ?RQの回数 –? Σ(定数 ?– ?各操作でのRQの回数) ?= ?最終的な区間の個数 ?> ?0 –? つまり、RQ ?の回数の合計 ?< ?定数*N ?となる –? 計算量量は ?RQの回数*RQの計算量量 ?= ?O(N^2) ?となる
満点解法 ?? 解法 –? ?黒く塗った区間を管理理する?方法を?工夫する –? 例例えば、c++のsetを?用いる –? RQ ?がO(log ?区間の個数) ?で?行行うことができるようになる ?? 計算量量 –? O(N ?log ?N) ?? 区間ではなく、?白と?黒が?入れ替わる場所を管理理すると、 少し実装が楽になります
満点解法（別解） ?? 問題を?言い換える –? タスクが ?N ?個ある –? タスク ?i ?は時刻 ?Si ?から始める –? タスク ?i ?には全部で ?Ci ?の時間がかかる –? タスク ?i ?の重要度度は ?i ?である（?小さい?方が重要） –? 各時点では、現在のタスクのうち最も重要なタスクを?行行う –? 各タスクの終了了時刻を求めよ ?? 解法 –? 各時点でのタスクについて ?(重要度度, ?残り時間) ?を優先順位付き キューで管理理してシミュレーションする ?? 計算量量 –? O(N ?log ?N)

More Related Content

CODE FESTIVAL 2015 予選B 解説

  • 1. CODE FESTIVAL 2015 予選B 解説 AtCoder株式会社 代表取締役 高橋 直大 2015/10/25 1
  • 3. 問題概要 ?? “2015/10/25” ?のように、各?文字が２度度ずつ現れる?文字 列列を「ダブル?文字列列」と呼ぶことにする ?? ?小?文字アルファベットからなる?文字列列 ?S ?が与えられる ?? S ?に含まれる?文字を全て含むダブル?文字列列を１つ出?力力し なさい ?? 例例 –? “no” ?→ ?“noon”（“onno”, ?“lemonmelon” ?なども可） –? “meat” ?→ ?“teammate”
  • 4. 解法１ ?? ?文字列列 ?S ?を、標準?入?力力から?入?力力する ?? ?文字列列 ?S ?を２回標準出?力力に出?力力する ?? 例例 –? “no” ?→ ?“nono” –? “meat” ?→ ?“meatmeat” –? “z” ?→ ?“zz” ?? 注意点 –? ２回の出?力力の間にスペースや改?行行などを?入れないこと –? 末尾に改?行行を出?力力するのを忘れないこと
  • 5. 解法２ ?? ?入?力力が何であろうと 全ての?小?文字アルファベットを２回ずつ出?力力する ?? 例例 –? “no” ?→ ?“aabbccddee?gghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz” –? “meat” ?→ ?“aabbccddee?gghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz” ?? 注意点 –? 抜けた?文字や、３回以上現れる?文字がないようにすること –? プログラムを書いて?文字列列を?生成するとより安全
  • 7. 問題概要 ? N 人の答えの採点をする ? それぞれの人の答えは 0 以上 M 以下の整数 ? 正解を忘れてしまった ? 過半数の人が同じ答えならそれを正解とする ? 正解を決められるなら正解を、決められないなら「?」 を出力せよ ? 制約 – 1 ≦ N ≦ 105 – 1 ≦ M ≦ 105
  • 8. 40点解法 ? 部分点制約 – N ≦ 100, M ≦ 100 ? 解法 – 0 から M まで正解を仮定する – 過半数の人が正解を答えているか調べる ? 計算量 – O(NM)
  • 9. 満点解法 ? 解法 – M+1 要素の配列を用意し、それぞれの答えが何回答えられたか を数える – それぞれの答えが過半数かを調べる ? 計算量 – O(N+M)
  • 11. 問題概要 ? N 部屋の旅館を経営している – それぞれの部屋の定員は Ai 人 ? M 組の予約がある – それぞれの予約の人数は Bi 人 ? ひとつの予約にひとつの部屋を割り当てる ? 定員が予約人数を下回ってはならない ? すべての予約に部屋を割り当てられるか判定せよ ? 制約 – 1 ≦ N ≦ 105 – 1 ≦ M ≦ 105 – 1 ≦ Ai ≦ 105 – 1 ≦ Bi ≦ 105
  • 12. 60点解法 ? 部分点制約 – N ≦ 100, M ≦ 100 ? 解法 – 一番人数の多い予約に一番定員の多い部屋を割り当てればよい ? それより人数の少ない予約に割り当てて大丈夫なら、一番人数の多 い予約と交換しても大丈夫 – 予約人数の多い順に、大きい部屋を割り当てる ? 計算量 – O((N+M)M)
  • 15. 問題概要 ?? ?白いマスがたくさん並んでいる ?? N ?個の駒がある ?? N ?回の操作を?行行い、i ?回?目の操作では、 –? 駒 ?i ?をマス ?Si ?に置く –? 「駒 ?i ?のあるマスが?白なら塗り、?黒なら次のマスに駒を移動」 を繰り返し、新たに塗ったマスが ?Ci ?個になったら終了了 ?? という操作を?行行う ?? 操作終了了後の各駒の位置を求めよ ?? 制約 –? 1 ?≦ ?N ?≦ ?105 –? 1 ?≦ ?Si ?≦ ?109 –? 1 ?≦ ?Ci ?≦ ?109
  • 16. 35点解法 ?? 部分点制約 –? 操作終了了後に駒のあるマスの番号は ?105 ?を超えない ?? マスを塗る回数の合計は ?105 ?回以下となる ?? 解法 –? 駒の動かし?方を、 ?? 今のマスから右にある最も近い?白マスに移動して?黒く塗る –? と考えてシミュレーションを?行行う –? 「最も近い?白マス」を?高速に?見見つけられれば良良い –? 以下のような、いくつかの?方法がある ?? setで?白マスの場所を管理理しておき、lower_?boundで「番号が ?x ?以 上のうち最も?小さいもの」を?見見つける（c++） ?? 上の?方法で、setの代わりに ?RMQ（Range ?Minimum ?Query）に 対応した ?segtree ?を?用いる ?? 次のページに?示したような?方法を使う
  • 17. 35点解法 ?? 以下のようなコードでも ?35 ?点を得ることができる import ?sys ? sys.setrecursionlimit(1024*1024) ? N ?= ?int(raw_input()) ? state ?= ?[-?‐1] ?* ?100001 ? def ?find_next(i): ? ? ?if ?d[i] ?== ?-?‐1: ?return ?i ? ? ?d[i] ?= ?find_next(d[i]) ? ? ?return ?d[i] ? for ?i ?in ?xrange(N): ? ? ?s,c ?= ?map(int,raw_input().split()) ? ? ?for ?j ?in ?xrange(c): ? ? ? ? ?s ?= ?find_next(s) ? ? ? ? ?d[s] ?= ?s+1 ? ? ?print ?s ※ ?言語はpythonです ← 再帰の深さ制限の対策 ← 「最も近い?白マス」を ?　 ??見見つける関数 ← シミュレーションを?行行って ?　 ?答えを求めるループ
  • 18. 35点解法 ?? 「最も近い?白マス」を?見見つける関数について ?? d[i] ?が ?-‐??1 ?のとき、マス ?i ?が?白であることを表します ?? そうでないときは、マス ?i ?よりも右でかつ、「最も近い ?白マス」よりも右でないマスの番号を表します –? そのままでは再帰の呼び出し回数が膨?大でTLEしてしまいます –? そこで、d[i] ?= ?find_next(d[i]) ?というように?高速化します ? ?? Union-?‐Find ??木の?高速化と同様の?手法 ? ?? ならし計算量量は ?O(log(N)) ?となります ? ?? Union-?‐Find ??木を?用いていると考えても良良いです ? def ?find_next(i): ? ? ?if ?d[i] ?== ?-?‐1: ?return ?i ? ? ?d[i] ?= ?find_next(d[i]) ? ? ?return ?d[i]
  • 19. 40点解法 ?? 部分点制約 –? N ?≦ ?1000 ?? 解法 –? ?黒く塗った区間を管理理する –? 以下をそれぞれ ?O(区間の個数) ?で求められる ?? あるマスから右にある最も近い?白マス ?? あるマスから右にある最も近い?黒マス –? このような区間への質問を解説上では「RQ」と呼ぶことにする –? ただし、隣隣り合った２つの区間は併合しておくこと ?? 計算量量 –? １回の操作での区間の個数の増減は、定数 ?-‐?? ?RQの回数 –? Σ(定数 ?– ?各操作でのRQの回数) ?= ?最終的な区間の個数 ?> ?0 –? つまり、RQ ?の回数の合計 ?< ?定数*N ?となる –? 計算量量は ?RQの回数*RQの計算量量 ?= ?O(N^2) ?となる
  • 20. 満点解法 ?? 解法 –? ?黒く塗った区間を管理理する?方法を?工夫する –? 例例えば、c++のsetを?用いる –? RQ ?がO(log ?区間の個数) ?で?行行うことができるようになる ?? 計算量量 –? O(N ?log ?N) ?? 区間ではなく、?白と?黒が?入れ替わる場所を管理理すると、 少し実装が楽になります
  • 21. 満点解法（別解） ?? 問題を?言い換える –? タスクが ?N ?個ある –? タスク ?i ?は時刻 ?Si ?から始める –? タスク ?i ?には全部で ?Ci ?の時間がかかる –? タスク ?i ?の重要度度は ?i ?である（?小さい?方が重要） –? 各時点では、現在のタスクのうち最も重要なタスクを?行行う –? 各タスクの終了了時刻を求めよ ?? 解法 –? 各時点でのタスクについて ?(重要度度, ?残り時間) ?を優先順位付き キューで管理理してシミュレーションする ?? 計算量量 –? O(N ?log ?N)