おはようございます。しほみんです。
朝に読むのはちょっと微妙なのでまた夜に確認してもらえばいいと思います。今日は、競技プログラミングについてお話しします。年始最初に行われたABC150についてです。一応初心者として初心者なりに考えていることを共有するために更新しているので、プログラムについて考えたい人はぜひ読んでみてください。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは650前後の茶色です。まずは700目指します。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約25回参加、7か月。
・目標はD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
今回はリアルタイムで参加しましたがUnratedだったです。ただ、ABCの3完でD問題は詰めが甘かったし、C問題も実装に悩んで時間かかってしまいました。とにかく工夫してできるようにしたいです。
あと、最近問題が聞いていることを数学的にどうしたらいいか自体はよくわかるのですが、実装力があまりにもなくてエラーが取れなかったり、オーバーフローしていて解答できず苦しい思いをしている感じです。随時書いていきたいですが、よわよわなので許してください....。
早速問題に移っていきます。話もコードもD問題まで載せます。
A問題
500円コインがk枚あります。X円以上ならYes、違うならNoを出力してください。
500*kがX円以上かどうかで出力します。
500*k >=XならYes, それ以外ならNoで出せば十分です。
B問題
文字列が与えられたときABCが含まれている数を調べよ。
例えば、BABCDRGABCだったら、2つABCがあるので2です。
これも素直に、頭から文字を読みます。Aを見つけて、その次がB、その次の次がCならカウントすればいいです。
つまり、文字列をSとして、S[i] = A,S[i+1] =B,S[i+2] = Cのときカウントして出力します。
C問題
数が辞書順に並んでいます。2つの並び順P,Qがあるので、この順番の差を求める問題です。
N=3のとき辞書順に並べると、123,132,213,231,312,321です。
P=123,Q=312のときは1番目と5番目でその差は4になります。
Nは2から8までなので、N!のそれぞれの並びを出してあとは照合すればいいって感じになります。
多分素直にN!通りを出してその順序を求めていくってことをすればいい気がしますが、思いつかなかったので、普通にPとQは何番目にあるか求めることにしました。
それぞれ頭から読むとその数がある順番はわかります。
例えば、N=3のとき
1. 123
2. 132
3. 213
4. 231
5. 312
6. 321
です。で1番目の文字が1なら1,2番目、2なら3,4番目、3なら5,6番目になります。
よって、その頭の数は3!/3*(その数-1)+1です。
これをただ繰り返せば答えが出てきます。ただし、2のときは注意が必要です。
2のときは1,3しかないので、辞書順では3は2番目となります。よって、2より大きい数は1引いて辞書として順番を減らす必要があります。
よって、アルゴリズムとしては
1. 頭からの文字を読んで、（辞書文字数 - その読んでいる文字の番数)!がその頭とした数なので、この数に(読んだ文字-1)をかけて足せば、その数の一番頭になります。
2. それ以降も同じように繰り返しますが、ただし、前に読んだ数が途中のとき、その数はもうないので、それ以降は辞書順として一つ数を減らす。
です。詳しくはコードを見てみてください。
D問題
ある数列はすべて偶数です。その数列のすべての数が以下の条件を満たすとき、その数Ｘをその数列の半倍数とします。
X = ai×(p+0.5)となるpが非負の数がある。
このXの数を求めます。
まず、X = (ai/2)*(2p+1)となる数があればいいです。
ここで条件を考えます。
・Xはai/2の倍数である
・Xとai/2で割り切れる2の数は同じである。
この二つの条件を出せばいいです。私はこの２つ目の条件を見落としていて解けませんでした。式変形してきちんと突き詰めるのも大切だと実感しました...。
あとはこれをアルゴリズム的にどうするかですが
まずは後者の条件を考えます。
Xはすべてに共通なので、aiとaj（iとjは任意）ですべて同じ2で割れる回数でないとなりません。まずはこの判定をします。
次に、前者の条件を考えます。
これは与えられた数を2で割ったときの最小公倍数を求め、その奇数倍の数を数えればいいです。
ただし、数が一つしかない場合は最小公倍数が求められないので、例外として考えるといいです。
これもコードで確認してみてください。
最後に....
最近のABCにしてはちょっと考えないとできないD問題だった気がします。C問題も全検索慣れていないと難しいので難しいセットだと感じました。ただ、きちんと問題を理解していれば解けなくないので、ちゃんとここら辺を解いていきたいなって思います。ではでは。
