| ■67874 / inTopicNo.9) | Re[6]: 過去問 |
| ■No67857 (sun さん) に返信 > その方法をとってやってみましたがそれでもAOJで3/6しか通りません。何度も入力して自分でも解を確かめてみたんですが全てあっているように思われます。何かほかに問題があるのでしょうか？それともコードのどこかにミスがあるのでしょうか？ なぜソートするのでしょうか。問題文には、 「i番目のジョイントは、i番目とi+1番目のパイプだけをつなげることができる。」 とあるので、ソートする必要はないでしょう。 また、パイプやジョイントの配置を入れ替える必要もないでしょう。 > 過去問のソースを読み解いている 質問の中でこの言葉がどのような意味を持っているのか、よくわかりません。 ここからは、過去問に対して解答があり、その解答のコードを読み解いていると理解できます。 が、ここに提示されているコードは、上に指摘した誤りからも、解答ではないようです。 Ｐ…パイプ □, ■…ジョイント（□…つながない、■…つなぐ） Ｐの数＝ｎ とすると、全パターンはこのようになります。 １：Ｐ1□1Ｐ2□2Ｐ3□3Ｐ4□4Ｐ5 ２：Ｐ1■1Ｐ2□2Ｐ3□3Ｐ4□4Ｐ5 ３：Ｐ1□1Ｐ2■2Ｐ3□3Ｐ4□4Ｐ5 ４：Ｐ1■1Ｐ2■2Ｐ3□3Ｐ4□4Ｐ5 ５：Ｐ1□1Ｐ2□2Ｐ3■3Ｐ4□4Ｐ5 ６：Ｐ1■1Ｐ2□2Ｐ3■3Ｐ4□4Ｐ5 ７：Ｐ1□1Ｐ2■2Ｐ3■3Ｐ4□4Ｐ5 ８：Ｐ1■1Ｐ2■2Ｐ3■3Ｐ4□4Ｐ5 ９：Ｐ1□1Ｐ2□2Ｐ3□3Ｐ4■4Ｐ5 １０：Ｐ1■1Ｐ2□2Ｐ3□3Ｐ4■4Ｐ5 １１：Ｐ1□1Ｐ2■2Ｐ3□3Ｐ4■4Ｐ5 １２：Ｐ1■1Ｐ2■2Ｐ3□3Ｐ4■4Ｐ5 １３：Ｐ1□1Ｐ2□2Ｐ3■3Ｐ4■4Ｐ5 １４：Ｐ1■1Ｐ2□2Ｐ3■3Ｐ4■4Ｐ5 １５：Ｐ1□1Ｐ2■2Ｐ3■3Ｐ4■4Ｐ5 １６：Ｐ1■1Ｐ2■2Ｐ3■3Ｐ4■4Ｐ5 ここから、ジョイントをつなぐ位置について、ｎ−１ビットの2進数と考えることができます。 つまり、2^(n-1) 通りのつなぎ型があるので、これら全部を調べます。 インデックスを 0〜2^(n-1)-1 変化させ、得られた数を2進数にして、 ビットが立っている位置のジョイントをつないだ結果を得ます。 パイプの数は、「つながなかったジョイントの数＋１」で求められます。 ところが、パイプの数の最大は65000ということなので、 工夫しないと桁あふれを起こします。 というより、全検索による回答をはじくための仕様だと思います。 パイプの長さを 5, 4, 2、ジョイントの長さを 2, 3 として、全パターンを計算すると (5+4+2)*3=33 (11+2)*2=26 (5+9)*2=28 16*1=16 つなぐと、掛ける数が減るので、ジョイントの長さが十分に長くないと、 つなぐことで給与が減ってしまいます。 ということは、長いジョイントから調べて、全くつながないときよりも、 多くなったか、少なくなったかを見るようにするという、shuさんの方法がいいでしょう。 で、単に「長いものをつなげばよい」のではなく、 「i番目のジョイントは、i番目とi+1番目のパイプだけをつなげることができる。」 なので、長いジョイントが何番目かを覚えておかなければなりません。 ジョイントの長さを、長さだけでなく、「何番目のジョイントか」も記録できる様にすればいいでしょう。 |