![B問題 アルゴリズム
?一桁ごとに処理していく
–数字で扱うなら、10で割った余り
?BigIntegerなどの多倍長クラスが必要であることに注意
?10で割った余りで必要な数字を取り出す
?10で割ることで、次の数字に移動する
–文字列で扱うなら、後ろから何文字目か
?文字列Sとして、S[S.Length – 1 – k] のような感じ
?数字の0ではなく文字の’0’なので、S[k]-’0’のような処理が必要
?足し算が終われば、それぞれの値を出力するだけ
–偶奇を間違えないように！
2014/8/28
7](https://image.slidesharecdn.com/codeformula2014-qualb-140828075958-phpapp02/85/Code-Formula-B-7-320.jpg)
More Related Content
What's hot (20)
Viewers also liked (20)
Similar to Code Formula 予選B 解説 (11)
More from AtCoder Inc. (20)
Code Formula 予選B 解説
- 1. Code Formula 2014 予選B 解説 AtCoder株式会社 代表取締役 高橋 直大 2014/8/28 1
- 2. ?AtCoder Inc. All rights reserved. 2 A問題 サイコロ 1.問題概要 2.アルゴリズム 2014/8/28
- 3. A問題 問題概要 ?サイコロの表面を表す整数Nが与えられる ?サイコロの底面に書かれた数字を出力しなさい。 ?制約 ?1 ≦ N ≦ 7 2014/8/28 3
- 4. A問題 アルゴリズム ?方針 –7 – Nを求める ?対面の合計が7なので、この計算で求まる。 2014/8/28 4
- 5. ?AtCoder Inc. All rights reserved. 5 B問題 11の倍数 1.問題概要 2.アルゴリズム 2014/8/28
- 6. B問題 問題概要 ?11の倍数を求める時には、下から数えて偶数桁目 の数字の和と、奇数桁目の数字の和を比較する ?これら2つの和を求めよ ?制約 –1≦N≦101000?1 2014/8/28 6
- 7. B問題 アルゴリズム ?一桁ごとに処理していく –数字で扱うなら、10で割った余り ?BigIntegerなどの多倍長クラスが必要であることに注意 ?10で割った余りで必要な数字を取り出す ?10で割ることで、次の数字に移動する –文字列で扱うなら、後ろから何文字目か ?文字列Sとして、S[S.Length – 1 – k] のような感じ ?数字の0ではなく文字の’0’なので、S[k]-’0’のような処理が必要 ?足し算が終われば、それぞれの値を出力するだけ –偶奇を間違えないように！ 2014/8/28 7
- 8. ?AtCoder Inc. All rights reserved. 8 C問題 仲良し文字列 1.問題概要 2.アルゴリズム 2014/8/28
- 9. C問題 問題概要 ?長さが同じ文字列A,Bが与えられる。 ?Aの文字をちょうど3回swapしてBに出来る場合、A,B を仲良し文字列と呼ぶ ?A,Bが仲良し文字列であるかどうかを判定しなさい ?制約 ?2 ≦|A|=|B|≦1000 2014/8/28 9
- 10. C問題 アルゴリズム ?まずは、3回しかswapしないことに注目！ –あんまり回数が多くないので、探索ができそう？ –1回の文字の選び方は、N*(N-1)/2通り ?NはA,Bの長さ、最大999 ?3回繰り返すとO(N^6)となり、これは間に合わない。 –でも、もうちょっと工夫すれば間に合いそう！ 2014/8/28 10
- 11. C問題 アルゴリズム ?3回のswapで文字列が同じになる –つまり、変更する文字は最大6文字 –7文字以上が違っていた場合、明らかに不正解！ ?これを利用して、探索範囲を減らそう！ –使っている文字の数が一致しない場合も不正解！ ?A,Bで一致している文字は無視して良い？ –“ab”, “ab”のような、ケースで不正解になってしまう。 ?3回ちょうどでなければならないため 2014/8/28 11
- 12. C問題 アルゴリズム ?方針1: ちょうどの判定を行うにはどうしたら良い か？ –もし同じ文字がAの中に存在すれば、同じ文字を交換する ことで、時間稼ぎが出来る –これを活用すると、「一致している文字の中でも、同じ文 字を2つ残しておけば、残りは排除して良い」 ?残る文字数は、不一致6 + 一致26*2 = 58 ?O(N^6)でも、不一致数などで枝刈をすれば十分間に合う ?方針2: 厳密には、以下のような処理で良い –一致した文字を全て排除する –元々の文字列Aに、同一文字が1つでも含まれていた3回 以下の探索、そうでなければ3回の探索を行う 2014/8/28 12
- 13. ?AtCoder Inc. All rights reserved. 13 D問題 お釣りの嫌いな高橋君 1.問題概要 2.アルゴリズム 2014/8/28
- 14. D問題 問題概要 ?N種類の硬貨がある ?K番目の硬貨は10^(k-1)円である ?K番目の硬貨をA_k枚持ってる時、払える金額は何 パターン存在するか.10億7で割った余りを出力せよ ?制約 –1≦N≦50 –0≦A_K≦ 2014/8/28 14
- 15. D問題 アルゴリズム ?普通に全列挙するのは間に合わない。 ?方針１：動的計画法を使って纏める –各硬貨ごとに、「今見ている硬貨何枚分余計に払えるか」 を状態とし、それを満たすパターン数を調べる ?例えば26枚の1円があったとすると、10円を調べる時には、 –残り2枚分の自由度があるのが7パターン ?1の位が0,1,2,3,4,5,6の時 –残り1枚分の自由度があるのが3パターン ?1の位が7,8,9の時 ?のように、何枚自由度があるパターンが何通りあるか、を動的計 画法で求める –むずかしい！ ?もっと簡単な方法が存在する！ 2014/8/28 15
- 16. D問題 アルゴリズム ?方針2：掛け算をしよう！ –入力例3 ?{12, 3, 7, 34}という入力 ?これを{12, 3} {7} {34}という風に分ける –{12, 3} では、0円から42円までが表現可能 43通り –{7}では、0～7 * 100円が表現可能 8通り –{34}では、0～34 * 1000円が表現可能 35通り ?よって、パターン数は、43*8*35-1=12039通り、と求められる –このように、幾つかのブロックに分けてあげると、独立に 計算可能！ ?では、どのように分ければ良いか？ 2014/8/28 16
- 17. D問題 アルゴリズム ?方針2：掛け算をしよう！ –入力例3 ?{12, 3, 7, 34}という入力 ?これを{12, 3} {7} {34}という風に分ける –{12, 3} では、0円から42円までが表現可能 43通り –{7}では、0～7 * 100円が表現可能 8通り –{34}では、0～34 * 1000円が表現可能 35通り ?よって、パターン数は、43*8*35-1=12039通り、と求められる –このように、幾つかのブロックに分けてあげると、独立に 計算可能！ ?では、どのように分ければ良いか？ 2014/8/28 17
- 18. D問題 アルゴリズム ?ブロックの分け方 –今見ている硬貨までの価値の和が、次の硬貨の価値に 達している場合 ?具体例 –{13} （13円なので、次の10円よりも大きい） –{12, 9} (102円なので、次の100円よりも大きい） –{100, 0, 0} (100円なので、次の100円と等しい） ?などは、0～価値の合計までの金額を、全て表現可能 –次の硬貨の価値に達していない場合 ?具体例 –{7} –{9, 9} ?これは、次の硬貨に影響を与えないので、ブロックを分けてしまう 2014/8/28 18
- 19. D問題 アルゴリズム ?ブロックの分けた後 –それぞれのブロックについて、掛け算して組み合わせを 計算 –それぞれの組み合わせを掛け合わせると、全ての組み合 わせとなる。 2014/8/28 19
- 20. D問題 アルゴリズム ?注意点 –0は含まないので、どの解法でも最後に1を引くのを忘れ ずに！ 2014/8/28 20