A問題の分析
エイシング プログラミング コンテスト 2020、A問題、ナンバーオブマルチプルス、問題文、L以上R以下の整数のうち、Dの倍数であるようなものはいくつありますか?
L、R、Dが与えられます。L、Rは100以下、Dも100以下ですので、
L、R、DをmapIntInput.splitで受け取って、4文ですね。
IinRange、Lstart、Rプラス1。 その前にAns,アンサーを0で入れといて、
If IperfetD == 0 だったら、Ans2プラスイコール1、最後プリントAnsで答えが出ると思います。
今回コードテストなしで出してみます。
はい、閉止したのでB問題いきます。
B問題、アン・オッド・プロブレム、問題文、1からNの番号がついたN個のマスがあります。
各マスには整数が書かれており、マスIにはAIが書かれています。
以下の2つの条件の両方を満たすマスはいくつありますか?
マスの番号は奇数、マスに書かれた整数も奇数。
N、AI共に100以下ですので、これも4文で回すだけですね。
Nイコールイントのインプット。
Lイコールリフトのマップ。
イント、インプットドットスプリット。
Ansイコール0、Iインレンジ、N。
Iプラス1パーセント2がノットイコール0だったら判定していきます。
Liがパーセント2ノットイコール0だったらAnsプラスイコール1。
プリント、Ans。
どうでしょうか。一回出してみましょう。
C問題の解説
これもACしたのでC問題いきます。
C問題、XYZトリプルヘッド問題文。
FN関数ですね。
以下の2つの条件の両方を満たすような3つの整数の組、XYZの個数とします。
XYZは1以上。
X次乗プラスY次乗プラスZ次乗プラスXYプラスYZプラスZXイコールN。
整数Nが与えられるのでF1、F2…FNまでをそれぞれ求めてください。
Nは10の4乗以下。
N行出力せよ。I行目にはFYの値を出力せよ。
入力例20。
Nイコール6において1、1、1のみが問題文中の2つの条件の両方を満たします。
Nイコール11において1、1、2、1、2、1、2、1の3つが問題文中の2つの条件を…
うーん、なるほど。
つまり、基本的に0を出して全部同じ数字で条件を満たすのであれば1を出力。
どれか1つ違う数字だった場合3つ条件を満たす要素があるので出力は3になると。
0、1、3のどれかですね。
で、その求め方がX事情、Y事情、Z事情、XY、YAZ、ZXを全部足した数が…
うん?
足した数がそのNになるかどうかっていうのを判定しろってことか。
まあ1回愚直に方文でやってみましょうか。
Nイコールイントのインプット。
入力例1は20。
で、関数書いてみますか。
D、F、F括弧小文字N。
違うか。ここに入れるのはX、Y、Zだ。
ん?違うか。Nでいいのか。
Nでよくて…
で、IF。まあいいか、IF文は。
4Xの中でも、IFX事情がNを超えたのならリターン…
ブレークでいいか。ブレーク。
IFX事情を足すY事情を足すX×YがNを超えたらブレーク。
で、4ZインレンジN。
IFX事情を足すY事情を足すZ事情を足すX×Yを足すY×Zを足すZ×X×Zを足すX×ZがイコールイコールNであれば…
いや、オーバーしたらまずか。
大なりNだったらブレークして、同じIF文をブレークの後に書いて、
これがNとイコールだったらリターン、トゥルー。
で、何もなく4文が終わったらリターン、フォルス。
本当か?えっと…違うね。
IFXなんちゃらかんちゃらがNだった場合、
IFXイコールYイコールイコールZだったら全部同じ数字だったらリターン1。
全部違う数字の場合はないのかな?
全部違う数字の場合は…
でも入力例の中には提示されていないので、ちょっとないものとして考えましょうか。
else…もしあったらもう知らん。
else return 3。
で、そうでなければ0を返すようにしておいて、
ホワインレンジ1からNプラス1、プリント、F括弧、i。
で、1回テストを実行。
0、0、3、3、0、1、3。
だいぶ違うね。
XYZが1以上っていうのが判定できてないですね、おそらく。
なので、4分全部に1始まりを入れて、もう一回実行。
0、0、0、0、0、1、0、0、0、0、3、3、3。
できてるっぽいね。3、0、0、OKですね。
3、3、0、0、なってるね。
1番最初が0が5つ。
1、2、3、4、5。
1が出て、0、4つの3。
出てるっぽいですね。
1回これでコード出力っていうか提出してみましょうか。
オーバーしそうな気がするんですけどね、こんだけ4分重ねてたら。
オーバーしたらちょっとコード解説見ていこうと思います。
だいぶ時間かかってるっぽいんで、たぶんDLEしますね。
しましたね。
テストケースが3つしかなくて、1個だけDLEしてますね。
たぶんこれがMAX入れてるのかな。10の4乗で判定してるんだと思います。
解説を見ていきます。
こういう系が初見だと何から手をつければいいかわからないかもしれない。
基本は全探索なので全探索を考える。
Nをそれぞれ答えるのでNの全探索を考えたくなるが、これは罠である。
XYZを全探索しよう。
全探索範囲について。
XYZが1以上の整数としか条件になっていないので上限が困るところ。
この上限がどのくらいかで全探索ができるかが変わる。
XYZは実は上限100までで探索すればいい。
これはXイコール100であるだけで、X次乗部分で10の4乗となるので、これ以上増やしても計算結果がN以下とならない。
よってXYZは100で全探索する。
XYZでやると全体で10の6乗通りとなるのでこれは問題ない。
探索空間が10の6乗通りならいけるし、10の7乗くらいなら怪しいし、それ以上なら無理。
あとはリストアンサーのNが計算結果がNである組み合わせを数え上げていって最後に順番に答えればいい。
C++でコードを書いていただいてますのでちょっと見てみましょうか。
リスト作ってるな。
リストを作って30ループしてる。
あーなるほど。
0のリストをめちゃくちゃいっぱい作っておいて、
もしその○×○っていうもろもろのやつがN以下だった場合、
そのリストに作ったやつのインデックス数になるからそこのインデックス数にプラス1していくだけでいいんだ。
最後、アンサーリストをそのまま出すとめちゃくちゃでかい数字になっちゃうから
Nの数分、4分でプリントしていけばいいという理屈ですね。
なるほど。関数作らなくていいんだな。
じゃあちょっと関数全部消して今見たものを間隔で作ってみましょうか。
Lイコールゼロフォーアイレンジ10101。
これでプリントLを1回確認。
0が並んでればOKですね。
で、フォーアイン、フォーXインレンジ。
1から100まで。
100まで?101にしてますね。0インデックスなので。
1から101まで。フォーYインレンジ。
1から101まで。
フォーZインレンジ。
1から101まで。
以後、XかけXプラスYかけYプラスZかけZプラス
XかけYプラスYかけZプラスZかけXが
N以下?
N以下だったらなのか?
だね。
N以下だったらLの中にこいつを入れる。
こいつをちょっと変数に作る。
XYZイコールこの長い計算式を入れておいて
FXYZイコール
イコールじゃない。小なりイコール。Nだったら
LのXYZ番目にプラスイコール1。
で、最後フォーアインレンジ
N回
LのXYZ
LのI番目をプリントすればいいのかな?
1プラスするかどうかですね、インデックス数に。
1個プラスした方が良さそうかな。
プリントLのIプラス1。
これでさっきと同じ入力例20の答えは出てるっぽいので
提出し直してみましょうか。
1回デカいリストを作っておいてっていう処理が
未だに身につかないんですよね。
ACしましたね。なるほど。
では、今日はここまでにしておきます。
お疲れ様でした。