K^2PC 解説Phase (kagamiz担当分) [コンテスト]
こんにちは！ kagamizです.
去る8月17日に行われた, K^2PCの問題の解説を行いたいと思います.
公開遅いですね.後悔してます(激寒)
参加していただいた皆さん, ありがとうございました!!
また, コンテスト環境を提供してくれたAtCoder社の皆様, テスターをしていただいたfura2さん, CTPCに引き続き一緒に作問していただいたkyuridenamidaさんには大変お世話になりました.
たくさんの方の協力があって開けたコンテストでした. ありがとうございました!
きっときゅうりさんもそのうち公開してくれます.きっと.
今回は, Easyの A, C, D ・ HardのA, B, Dを担当しました.
Easy A. ハンバーガー(Hamburger)
問題文 : http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_e1
First Acceptance : roxion1377 (02:06)
Submission : 195
Accepted : 71 (36 %)
解説 : 問題文に出てくる数字が汚かったです. 反省してます. (後悔はしてません.)
問題文にある条件より, ハンバーガーをN個作りたいとき, 肉が N 枚, パンが2 * N 枚, トッピング類が 3 * N個必要です.
肉は現在a枚, パンはb枚, トッピング類はc個あるわけですから, N - a, 2 * N - b, 3 * N - cを順に出力すればよいわけです.
ですが, それぞれの材料が必要な量より多いとき, すなわち, N - a などが負になってしまうときは, 0 を出力しましょう.
単純な引き算および条件分岐のみで書けるので, O(1)の計算量で問題が解けます.
講評：僕が思っていたより少しだけAC率が低かったように思いますが, 正解者数は概ね予想していたとおりでした.
AC率が低くなった理由としては, 急いでコードを書いていて, N - aの部分を a - Nと書いていたり, これらの数値が0未満になったときの処理をしていないものなどがあげられると思います.
また, 改行がなくWAになっていた回答も見受けられました. 問題文中にも記述したのですが, 最後に改行をするのを忘れないようにしましょう.
解答例： (C, 17行) http://ideone.com/sesrj
Easy C. / Hard A. 紅茶(Tea)
問題文 : http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_e3
http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_h1
(Easy)
First Acceptance : chronotable (11:05)
Submission : 74
Accepted : 39 (53 %)
(Hard)
Fist Acceptance : banana (06:04)
Submission : 73
Accepted : 51 (70 %)
解説 : 問題文の前半に出てくる問題は, 高専の数学2 問題集という数学の問題集に出てきます.
きゅうりさん「彼には簡単すぎた...」
最後のサンプルは相変わらず汚いですネ.
この問題で踏む手順は二つで, まずは, 与えられたi番目, j番目のペアを見つけることを考えます.
まず, 与えられたペアたちを, 中に書かれている2つの和でグループ分けしてみると
和が2 => (1, 1),
和が3 => (2, 1), (1, 2),
和が4 => (3, 1), (2, 2), (1, 3), ...
と, 和の通りの順番になっています.
実際にn番目のペアの和がどれくらいかは, 簡単なforループを回せばわかるので, この作業はO(√n) で行えます.
次に, 実際にi番目の数がわかったら, (ai + aj, bi + bj)というペアが何番目かを求めます.(ai + aj = m, bi + bj = nとしておきます.)
組(m, n)は, 和がm + nのペアのn番目ですから, 和が(m + n - 1)までの数の総和 + nで答えがもとまります. この作業は O(1)で行えます.
よって, 計算量はO(√i + √j) ほどとなります.
講評：Easy, Hardとも正答率は高かったです.
最初のステップが少し厄介ですが, 次の方は簡単だったと思います.
オーバーフローの悲しみが起きないように, すべての演算をintで行っても大丈夫な範囲で制約を設定しました.
Easyではこれを解くだけでAとBの得点になるので, 大きかったのではないでしょうか.
解答例： (C, 28行) http://ideone.com/EfAmk
Easy D. / Hard B. 虫歯(Cavity)
問題文 : http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_e4
http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_h2
(Easy)
First Acceptance : chronotable (36:16)
Submission : 57
Accepted : 9 (16 %)
(Hard)
Fist Acceptance : k_operafan (14:30)
Submission : 115
Accepted : 31 (27 %)
解説 : きゅうりさんの歯の神経をズタボロにしました. あとかっこよくしました.
とりあえず(0, 1)だけ治療すればいいんじゃないか, という意見もありますが, それは聞こえなかったことにして解説に移りたいと思います.
・40 % 解法
最初に, すべての神経が根にたどり着けると仮定します. (ans = (2^K) - 1)
まず, 治療されている虫歯神経のうち, もっとも上にあるものの部分木は, 確実に根にたどり着けません. ゆえに, 部分木の大きさをansから引いてやります. このとき, この治療されている神経をメモしておきます.(ここでは配列に格納しておくことにします)
それ以降の治療された神経は, 実際にO(K)の時間をかけて, 根まで遡ります. このとき, 先祖が治療されていれば, その神経はすでに引かれているので, 何も操作をしないで大丈夫です. そうでなければ, 部分木の大きさをansから引いて, その神経をメモします.
このとき, 先祖が治療されているかの判定を, 配列を線形探索すればO(N)でできます.
ここまでを実装すれば, O(KN^2)時間でプログラムが動作し, 得点の40%を得ることができます.
・100 % 解法
40 %解法で時間がかかっているのは, 配列を線形探索しているところです. ここを, 二分探索に変えたり, 配列ではなくsetを使うことで, O(KNlogN)時間でプログラムが動作し, 得点の100%を得ることができます.
講評：writer解はC++で書かれており, 0.5secくらいで動作するものだったので制限時間を8倍の4secにしました.
少し時間制限が厳しいかと思いましたが, 使われていたほとんどの言語でのACを確認できたのでよかったです.
解答の中に再帰関数をつかっているものがあり, コードがシンプルかつ短く書けていたので, 私も参考になりました.
細かい条件が多いので, デバッグがし易いコードを書くようにしましょう.
解答例： (C++, 61行) http://ideone.com/igvVD
Hard D. マシュマロ(Marshmallow)
問題文：http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_h4
Fist Acceptance :rng_58 ▲ペ▲ロ▲リ▲ン▲ (21:22)
Submission : 34
Accepted : 16 (47 %)
解説 : 散歩にいく途中で水溜りがあって, 帰りには消えていたり, いきには水溜りがなくて, 帰りには水溜りがあったりする不思議な場所での問題です.
30 %解法のベースとなった漸化式は, マスターオブ場合の数という本にのっている, 明治に出題された大学入試の問題からもってきたものです.
しかし, 30 %解法の数列は OEISで調べると一瞬で出てくるので, この水溜りの設定がつきました.
(3000km散歩するkagamizとミズゴロウはなんなんですかね...)
・K <= 15の, 20 % 解法
探索する場所が高々16箇所しかないので, 深さ優先探索で間に合います.
行きのためのdfsの関数, 帰りのためのdfsの関数をもって, 訪れた場所はbitで管理するなどをすると楽に実装できます. O(2^K)時間ほどで動作します.
これだけで 配点の 20 % を得ることができます.
・R = 0 の, 30 % 解法
水たまりが1つもない, つまり, いつでも全ての地点に訪れて良い場合を考えましょう.
このとき, "行きのみに訪れる地点" "帰りのみに訪れる地点" "両方で訪れる地点"を, すべての地点に割り振ると, 散歩の仕方が一意に定まることに注意します.(ただし, 前者2つは連続してはいけないことに注意します.)
上のことに気づけば, n[m]の地点に行きのみに訪れる総数をa_n, 帰りのみに訪れる総数をb_n, 両方で訪れる総数をc_nとすることで
a_n = b_{n - 1} + c_{n - 1}
b_n = a_{n - 1} + c_{n - 1}
c_n = a_{n - 1} + b_{n - 1} + c_{n - 1}
という漸化式が成り立ち, Kmの地点には行きも帰りもよるので, 答えがc_Kとなることがわかります.
この漸化式をそのまま実装することによって, R = 0のケースにO(K)時間で答えることができ, 配点の 30 % を得ることができます.
・100% 解法
100% 解法は, R = 0の30 %解法を少し改造するだけで実装できます.
上の漸化式において, 水溜りが行きの地点にある場合は, そこは通れないのでa_P = c_P = 0とします.
同様に, 帰りの地点にある場合は b_P = c_P = 0とします.
K <= 3 * 10^6程度であれば, 配列をとることができるので, O(1)でこの作業ができます.
これで, O(K)時間で漸化式をうめていくことができ, 100%の得点を得ます.
講評：思っていたよりも正答者数が多く, とくにりんごさんペロリンさんが30分以内にといていてびっくりしたのは覚えています.
writer解はCでかかれており, 0.1secくらいで全てのケースに答えることができ, 時間は10倍の1secほどでとっていました(0.5secと迷いましたがこれで良かったと思っています).
解答のなかには, ただしく実装ができていてもTLEするものが多く見受けられました. これは, forの定数ループが原因だと思われます.
定数が10以上あるとどの言語でも死んでしまうので, できるだけforループはすくなくなるように実装しましょう.
解答例： (C, 33行) http://ideone.com/aTOWC
去る8月17日に行われた, K^2PCの問題の解説を行いたいと思います.
公開遅いですね.後悔してます(激寒)
参加していただいた皆さん, ありがとうございました!!
また, コンテスト環境を提供してくれたAtCoder社の皆様, テスターをしていただいたfura2さん, CTPCに引き続き一緒に作問していただいたkyuridenamidaさんには大変お世話になりました.
たくさんの方の協力があって開けたコンテストでした. ありがとうございました!
きっときゅうりさんもそのうち公開してくれます.きっと.
今回は, Easyの A, C, D ・ HardのA, B, Dを担当しました.
Easy A. ハンバーガー(Hamburger)
問題文 : http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_e1
First Acceptance : roxion1377 (02:06)
Submission : 195
Accepted : 71 (36 %)
解説 : 問題文に出てくる数字が汚かったです. 反省してます. (後悔はしてません.)
問題文にある条件より, ハンバーガーをN個作りたいとき, 肉が N 枚, パンが2 * N 枚, トッピング類が 3 * N個必要です.
肉は現在a枚, パンはb枚, トッピング類はc個あるわけですから, N - a, 2 * N - b, 3 * N - cを順に出力すればよいわけです.
ですが, それぞれの材料が必要な量より多いとき, すなわち, N - a などが負になってしまうときは, 0 を出力しましょう.
単純な引き算および条件分岐のみで書けるので, O(1)の計算量で問題が解けます.
講評：僕が思っていたより少しだけAC率が低かったように思いますが, 正解者数は概ね予想していたとおりでした.
AC率が低くなった理由としては, 急いでコードを書いていて, N - aの部分を a - Nと書いていたり, これらの数値が0未満になったときの処理をしていないものなどがあげられると思います.
また, 改行がなくWAになっていた回答も見受けられました. 問題文中にも記述したのですが, 最後に改行をするのを忘れないようにしましょう.
解答例： (C, 17行) http://ideone.com/sesrj
Easy C. / Hard A. 紅茶(Tea)
問題文 : http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_e3
http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_h1
(Easy)
First Acceptance : chronotable (11:05)
Submission : 74
Accepted : 39 (53 %)
(Hard)
Fist Acceptance : banana (06:04)
Submission : 73
Accepted : 51 (70 %)
解説 : 問題文の前半に出てくる問題は, 高専の数学2 問題集という数学の問題集に出てきます.
きゅうりさん「彼には簡単すぎた...」
最後のサンプルは相変わらず汚いですネ.
この問題で踏む手順は二つで, まずは, 与えられたi番目, j番目のペアを見つけることを考えます.
まず, 与えられたペアたちを, 中に書かれている2つの和でグループ分けしてみると
和が2 => (1, 1),
和が3 => (2, 1), (1, 2),
和が4 => (3, 1), (2, 2), (1, 3), ...
と, 和の通りの順番になっています.
実際にn番目のペアの和がどれくらいかは, 簡単なforループを回せばわかるので, この作業はO(√n) で行えます.
次に, 実際にi番目の数がわかったら, (ai + aj, bi + bj)というペアが何番目かを求めます.(ai + aj = m, bi + bj = nとしておきます.)
組(m, n)は, 和がm + nのペアのn番目ですから, 和が(m + n - 1)までの数の総和 + nで答えがもとまります. この作業は O(1)で行えます.
よって, 計算量はO(√i + √j) ほどとなります.
講評：Easy, Hardとも正答率は高かったです.
最初のステップが少し厄介ですが, 次の方は簡単だったと思います.
オーバーフローの悲しみが起きないように, すべての演算をintで行っても大丈夫な範囲で制約を設定しました.
Easyではこれを解くだけでAとBの得点になるので, 大きかったのではないでしょうか.
解答例： (C, 28行) http://ideone.com/EfAmk
Easy D. / Hard B. 虫歯(Cavity)
問題文 : http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_e4
http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_h2
(Easy)
First Acceptance : chronotable (36:16)
Submission : 57
Accepted : 9 (16 %)
(Hard)
Fist Acceptance : k_operafan (14:30)
Submission : 115
Accepted : 31 (27 %)
解説 : きゅうりさんの歯の神経をズタボロにしました. あとかっこよくしました.
とりあえず(0, 1)だけ治療すればいいんじゃないか, という意見もありますが, それは聞こえなかったことにして解説に移りたいと思います.
・40 % 解法
最初に, すべての神経が根にたどり着けると仮定します. (ans = (2^K) - 1)
まず, 治療されている虫歯神経のうち, もっとも上にあるものの部分木は, 確実に根にたどり着けません. ゆえに, 部分木の大きさをansから引いてやります. このとき, この治療されている神経をメモしておきます.(ここでは配列に格納しておくことにします)
それ以降の治療された神経は, 実際にO(K)の時間をかけて, 根まで遡ります. このとき, 先祖が治療されていれば, その神経はすでに引かれているので, 何も操作をしないで大丈夫です. そうでなければ, 部分木の大きさをansから引いて, その神経をメモします.
このとき, 先祖が治療されているかの判定を, 配列を線形探索すればO(N)でできます.
ここまでを実装すれば, O(KN^2)時間でプログラムが動作し, 得点の40%を得ることができます.
・100 % 解法
40 %解法で時間がかかっているのは, 配列を線形探索しているところです. ここを, 二分探索に変えたり, 配列ではなくsetを使うことで, O(KNlogN)時間でプログラムが動作し, 得点の100%を得ることができます.
講評：writer解はC++で書かれており, 0.5secくらいで動作するものだったので制限時間を8倍の4secにしました.
少し時間制限が厳しいかと思いましたが, 使われていたほとんどの言語でのACを確認できたのでよかったです.
解答の中に再帰関数をつかっているものがあり, コードがシンプルかつ短く書けていたので, 私も参考になりました.
細かい条件が多いので, デバッグがし易いコードを書くようにしましょう.
解答例： (C++, 61行) http://ideone.com/igvVD
Hard D. マシュマロ(Marshmallow)
問題文：http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_h4
Fist Acceptance :
Submission : 34
Accepted : 16 (47 %)
解説 : 散歩にいく途中で水溜りがあって, 帰りには消えていたり, いきには水溜りがなくて, 帰りには水溜りがあったりする不思議な場所での問題です.
30 %解法のベースとなった漸化式は, マスターオブ場合の数という本にのっている, 明治に出題された大学入試の問題からもってきたものです.
しかし, 30 %解法の数列は OEISで調べると一瞬で出てくるので, この水溜りの設定がつきました.
(3000km散歩するkagamizとミズゴロウはなんなんですかね...)
・K <= 15の, 20 % 解法
探索する場所が高々16箇所しかないので, 深さ優先探索で間に合います.
行きのためのdfsの関数, 帰りのためのdfsの関数をもって, 訪れた場所はbitで管理するなどをすると楽に実装できます. O(2^K)時間ほどで動作します.
これだけで 配点の 20 % を得ることができます.
・R = 0 の, 30 % 解法
水たまりが1つもない, つまり, いつでも全ての地点に訪れて良い場合を考えましょう.
このとき, "行きのみに訪れる地点" "帰りのみに訪れる地点" "両方で訪れる地点"を, すべての地点に割り振ると, 散歩の仕方が一意に定まることに注意します.(ただし, 前者2つは連続してはいけないことに注意します.)
上のことに気づけば, n[m]の地点に行きのみに訪れる総数をa_n, 帰りのみに訪れる総数をb_n, 両方で訪れる総数をc_nとすることで
a_n = b_{n - 1} + c_{n - 1}
b_n = a_{n - 1} + c_{n - 1}
c_n = a_{n - 1} + b_{n - 1} + c_{n - 1}
という漸化式が成り立ち, Kmの地点には行きも帰りもよるので, 答えがc_Kとなることがわかります.
この漸化式をそのまま実装することによって, R = 0のケースにO(K)時間で答えることができ, 配点の 30 % を得ることができます.
・100% 解法
100% 解法は, R = 0の30 %解法を少し改造するだけで実装できます.
上の漸化式において, 水溜りが行きの地点にある場合は, そこは通れないのでa_P = c_P = 0とします.
同様に, 帰りの地点にある場合は b_P = c_P = 0とします.
K <= 3 * 10^6程度であれば, 配列をとることができるので, O(1)でこの作業ができます.
これで, O(K)時間で漸化式をうめていくことができ, 100%の得点を得ます.
講評：思っていたよりも正答者数が多く, とくに
writer解はCでかかれており, 0.1secくらいで全てのケースに答えることができ, 時間は10倍の1secほどでとっていました(0.5secと迷いましたがこれで良かったと思っています).
解答のなかには, ただしく実装ができていてもTLEするものが多く見受けられました. これは, forの定数ループが原因だと思われます.
定数が10以上あるとどの言語でも死んでしまうので, できるだけforループはすくなくなるように実装しましょう.
解答例： (C, 33行) http://ideone.com/aTOWC
2012-09-06 13:27
nice!(0)
コメント(0)
トラックバック(0)
コメント 0