Indeedなう 予選A 解説
- 1. Indeedなう 予選A 解説 AtCoder株式会社 代表取締役 高橋 直大 2015/3/14 1
- 2. 競技プログラミングを始める前に ? 競技プログラミングをやったことがない人へ – まずはこっちのスライドを見よう！ – http://www.slideshare.net/chokudai/abc004 2015/3/14 2
- 3. ?AtCoder Inc. All rights reserved. 3 A問題 桁数 1. 問題概要 2. アルゴリズム 2015/3/14 3
- 4. A問題 問題概要 ? 整数A,Bが与えられる ? A×Bの掛け算の筆算を行う ? この掛け算の筆算では1桁の掛け算を(Aの桁 数)×(Bの桁数)だけ行う ? (Aの桁数)×(Bの桁数)を出力する ? 制約 – 1 ≦A,B≦ 1,000,000 2015/3/14 4
- 5. A問題 アルゴリズム ? ある整数xの桁数を求めたい．いろいろ方法がある↓ – xを10で割って切り捨てるを，xが0になるまで行う(10で割った 回数が答えになる) ? 例: 123: 123→12→1→0 ∴ 3回 – そもそも読み込む整数を文字列で受け取って，その長さを求 める ? 上記の方法を用いてAとBの桁数が求まったら それらを掛け合わせたものを出力する 2015/3/14 5
- 6. ?AtCoder Inc. All rights reserved. 6 B問題 INDEEDなう！ 1. 問題概要 2. アルゴリズム 2015/3/14 6
- 7. B問題 問題概要 ? 文字列Sが与えられる ? Sが”indeednow”のアナグラムになっているか判定 ? SはNコ与えられるので全部について判定する ? 制約 – 1 ≦ N ≦ 100 – 1 ≦ Sの長さ ≦ 100 2015/3/14 7
- 8. B問題 アルゴリズム ? 文字列Aが文字列Bのアナグラムである ?A,Bをそれぞれ辞書順でソートした文字列が等しい – 例: A=“abca,B=”cbab” ソートを行うとどちらも”aabc”となるためAはBのアナグラム ? 今回の問題も上記の事実を用いるとよい． ? 入力される文字列をソートしたものが”indeednow” をソートしたものと等しければ”YES”，そうでなけれ ば”NO”を出力すればよい． 2015/3/14 8
- 9. B問題 アルゴリズム ? 別解 – 出現する文字数を数えて比較 – 実際にアナグラムを全列挙しても良い(しかし，手間がか かる上に遅い) 2015/3/14 9
- 10. ?AtCoder Inc. All rights reserved. 10 C問題 説明会 1. 問題概要 2. アルゴリズム 2015/3/14 10
- 11. C問題 問題概要 ? 予選コンテストを行った．N人の学生の点数がある． ? 予選の選抜基準はボーダーがxのとき以下のように行う ? ボーダーがxのとき正の点数を取っていてかつx点以上の学生 を全員選抜 ? 選抜人数がk人以下となるようにボーダーを調整せよ ? ただし，会場はQコあり，それぞれkが異なる．それらの 会場でそれぞれ行う場合についてのボーダーを求める． ? 制約 – 1 ≦ N ≦ 100000 – 1 ≦ k ≦ N – 1 ≦ Q ≦ 100000 2015/3/14 11
- 12. C問題 アルゴリズム ? まず与えられた点数から 0点の学生を取り除く ? 点数を降順にソートした数列を用意する ? ボーダーは，その数列のk番目の点数+1を答えれば よい ? 計算量: O(Q + NlogN) 2015/3/14 12
- 13. ?AtCoder Inc. All rights reserved. 13 D問題 パズル 1. 問題概要 2. アルゴリズム 2015/3/14 13
- 14. D問題 問題概要 ? H*Wのスライドパズルの盤面が与えられる ? 最小手数が24手以内という制約の下で最小手数を 求めなさい ? 制約 – 2 ≦ H,W ≦ 6 – 最小手数は24手以下 2015/3/14 14
- 15. D問題 アルゴリズム ? スタート地点からナイーブに幅優先探索を行うと状 態数が爆発して時間切れしてしまう ? いくつかの改善を行うと通る． – 状態の持ち方については，特に凝った工夫をしなくても一 応通るようになっている(C++) ? 具体的な改善の仕方について次スライドから説明 2015/3/14 15
- 16. D問題 アルゴリズム ? 汎用的な改善案: 24手以内?23手まで探索して見 つからなかったら24手と出力することで少し速くなる ? 改善案1: 両側探索 – スタート地点から12手,ゴール地点から12手分のノードを 列挙(それぞれ全列挙できるサイズ) – それらの共通の可達ノードを比較して最小手数を求める – しかし，定数倍が重いとTLEするかもしれない – 定数倍改善すれば通るようにしている 2015/3/14 16
- 17. D問題 アルゴリズム ? 改善案2: A*探索 – (今の距離+最低限かかる暫定距離*)をコストに持ち，そ のコストが小さいものから確定するダイクストラ的探索 – その暫定距離が24を超えたら打ち切るようにする – A*探索に対する最悪のケースは作るのが非常に難しい ため，ある程度時間のかかるケースを用意したがそれで も想定解法だと数十ms程度 *たとえば空きマス以外の全てのマスについて本来の位置 とのマンハッタン距離差の総和を求めたものを用いるとよい 2015/3/14 17
- 18. D問題 アルゴリズム ? 今回の問題は，A*探索を用いると高速に解ける 「両側探索の計算量の見積もり」 ? 12手探索して得られる盤面の状態数が高々 708588(=4*3^11) 通り (これは，常に4方向に動けるとし て操作を打ち消すような遷移を行わないときの状態数．実際 にはもっと少ない) ? なので，両側探索だと定数倍改善を意識すれば通る 「A*探索の計算量の見積もり」 ? 難しいため見積もり困難だが，実測してみると探索 ノード数がかなり減っていることが分かる 2015/3/14 18