おはようございます。しほみんです。
エイシングプログラミングコンテストをやってきました。難しめのD問題をはやめにといて青パフォ出せたので満足です。
https://atcoder.jp/contests/aising2020
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは1000程度になりました。緑中堅へ。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在55回以上参加、2年目。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はABCD、60分でした。A, B, Cはさっさと解いて、D問題にかなり時間を費やしました。最初は意味不明でしたが、時間かけていくと気が付くところに気が付いてACできました。考えられるようになったなあという会でした。レーディングは1630で初青パフォ、レートは945→1035で過去最高を大幅更新です。
今回はD問題まで振り返ります。
長くなるので前半はC問題まで書きます。
前回に引き続き考察をメインに書きます。
コードは別に上げます。
A問題
L以上R以下のうちdの倍数はいくつあるでしょう？
制約がL,Rともに1から100までなので最大でも100個分dの倍数かどうか調べるだけです。
よって、LからRまでをdで割ってみて割り切れるかどうかで判定できます。
割り切れるかどうかはi%dを見ます。%はdで割ったあまりを示す記号でこれが0なら割り切れます。
よって、i%d == 0のときだけカウントすればよいです。
別解として1からRまでのdの倍数はR/d個あり、そのうちL-1以下となる、(L-1)/d個は買いに含まれないので、R/d - (L-1)/dでも求められます。
B問題
1,2,3,....,Nの番号が付いたN個のマスがあります。
各マスには整数がaiと書かれています。
以下の2つの条件を満たすマスはあいくつありますか？
・マスの番号が奇数
・マスに書かれた整数が奇数
ほぼ日本語の問題ですが、奇数番目のマスにおいて、それぞれ見て奇数かどうか判定するだけです。
for文では増やす量をi++からi = i + 2にすることで一つ飛ばしで調べられます。
また、奇数かどうかはa[i]%2で決めればいいので、素直にfor文+if文で完結します。
最大でも100個しかないので時間も余裕で間に合います。
C問題
以下の条件を満たす(x,y,z)の個数をf(n)とする。
・1<=x,y,z
・（xの2乗）+（yの2乗）+（zの2乗）+xy+yz+zx = n
整数Nが与えられるときf(1),f(2),f(3),....,f(N)を求めなさい。
制約条件1<=N<=10000
2つ目の条件の式なんかうまく変換したらうまくいきそうとか思うかもしれないですが、式変形だけだとどうしようもなくなります。
ということで、方針を練ります。明らかに2つ目の式の左辺は人間が求めるには難しいです。よって、逆にx,y,zを決めたときいくつになるか考えてみましょう。
すなわち、x,y,zのあり得る組み合わせを全部試してみて、満たす数をそれぞれ求めていくのです。
例えばx=1,y=1,z = 1なら、6なので、f(6)に1足されます。
こんなふうにx,y,zを入れてnを出していきます。これは全探索っていうアルゴリズムでは比較的基本的なものです。
ただ、かといってx,y,zを無限に調べていったら時間がかかってしまうのでどこかできる必要があります。
x,y,zには対称性があります（対称性とはx,y,zの立ち位置を変えても同じということ。例えば、(1,1,2)(2,1,1),(1,2,1)は全部同じである）。
これを考えるとx,y,zの範囲はすべて同じであることが分かります。
なので、xの範囲だけ決められれば、y,zはおのずと決まります。
ここで注目するのは2つ目の式です。x＝100のとき、どんなy,zでも10000超えます。
よって、x =100まで調べれば十分であり、それ以上は意味を成しません。
よって、x,y,zの組み合わせは1-100までで考えればよく、3重ループをすることで解けます。これはo(100の3乗）なので十分間に合います。
ただし、今回制限範囲の10000を超えたものを記録しても無意味なので、もとめたnが10000以下のときだけカウントすることに注意します。
あとは、普通にあたまから1,2,3,...に該当するものを出していくだけです。
最後に....
C問題も全探索という典型問題だったのですが、慣れていないと難しい気がします。とりあえず、勝負はD問題だったのでそれはまた木曜に話します。
ではでは。
