AtCoder Beginner Contest 177に参加しました
ABC177に参加しました。
A~Eの5完でかなり満足しました。自分にも解けるということは、現状ほかの人も解けるということなので、順位はそこまでよくはなかったですが…。
Tasks - AtCoder Beginner Contest 177
All Submissions - AtCoder Beginner Contest 177
A-Don't be late
小学校の算数みたいですね。
B-Substring
Tの大きさをLとして、1文字目からL文字目までがTと一致するように書き換えた文字数を数えます。同様に始点を2文字目にして、そこからL文字の間をTと一致するように書き換えた文字数を数えます。以下同じように始点をずらしていくと、書き換える必要のある最小文字数が分かります。Sの大きさはたかだか1000文字なので、この方法で間に合います。
C-Sum of product of pairs
愚直に計算していては時間制限に間に合わないので、工夫しました。i<jとなる組の積の和を求めるので、iを固定して考えると、i=1の時にjは2~Nまで、i=2の時にjは3~Nまで、以下iが増えるごとにjの取る範囲が減っていきます。固定したiごとに考えると、A1*(A2+A3+.......+AN)、A2*(A3+A4+.......+AN)というようにまとめることができます。あらかじめN個のAの値を足しておくことで、そこからAiの値を引いてからAiとの積を取ることで高速に計算できます。
D-Friends
友達の友達はみんな友達理論です。N人の集合の中に友達関係でつながった友達集団がいくつかできているということになります。これを、同じグループに友達が一人もいない状況に全員がなるようにグループ分けし、グループ数の最小値を求めるという問題です。これは、友達集団の構成人数が一番多いところを全員バラバラのグループに入れることで達成できるので、最大の友達集団の構成人数が答えになります。
Union-Findでできるやつや！と思いましたが、実装したことがないですし、構成人数が分かればいいので、DFSで友達関係を辿っていくことでそれぞれの集団の規模を調べることにしました。一度確認した人を複数回確認する必要はないので、確認の有無を入れておく配列を用意し、再帰関数で実装しました。
再帰関数でDFSを書く練習になってよかったと思います。
E-Coprime
方針が出来れば解けるタイプの問題なのかなと思いました。
pairwiseとsetwiseを独立で考えるか、両方をまとめて判定するかでまず大きな方針が決まるように思います。私ははじめ、1つの判定方法でまとめて一気に求めようとしていましたが、どうにも考えがまとまらなかったので独立で考えることにしました。pairwiseではない時のみsetwiseになる可能性があるので、まずはpairwiseであるかどうかを考えます。各Ai,Ajの組み合わせについてそれぞれ確認していては時間が足りないので工夫します。すべてのGCDが1ということは、N個のAのなかで、1以外の約数を共有していないということになります。そこで、エラトステネスの篩の要領で配列を用意し、まずAiの約数を列挙し、それぞれの約数について、倍数をチェックしていきます。この時、初めに小さい順にsortをかけておくことで、各Aiについて最初にAiがすでにチェックされているかを確認し、その後は約数とその倍数をチェックしていくだけでいいようになります。もし、約数が重複していた場合はpairwiseではないのでそこで確認を打ち切ります。計算量が多くなるかなとも思ったのですが、100万以下の素数の数は10万個もないですし、約数が重複しないように制限の中で数を用意した場合は1つ1つの値が小さくなり、また制限時間を超えるほどの数を用意できないと思ったのでこの方針で出しました。
次にsetwiseについて考えます。これはGCDを順に考えていくだけで済みます。最初にsortしているので、小さいものから順にGCDを取っていくことができます。GCD=A1としてスタートして、A1からANまで順にGCD(GCD, Ai)としていくことで拘束に求められます。GCD=1となった時点で打ち切ります。
今回は以上です。
コンテスト中に自力で解いた方法を記録していると、ほかの方のきれいな解法や実装と比べた粗がはっきりするので勉強になる、と言い聞かせてやってきました。これまではなかなか実感としてはそのようには思えませんでしたが、ABC170ごろからははD,Eまで解けることも増えてきて、比較的難しい問題を何とか通す、という状態によくなるので価値を感じ始めています。
AtCoder Beginner Contest 176に参加しました
ABC176に参加しました。
A~Cまでは6分ほどで解くことができ、Eも3ペナ67分で通せたので良かったと思います。Dは、解けそうで解けないまま2週間が過ぎました。
Tasks - AtCoder Beginner Contest 176
All Submissions - AtCoder Beginner Contest 176
A-Takoyaki
余りを切り上げる必要があります。(N+X-1)/Xとすることで、簡潔に書くことができます。
B-Multiple of 9
string型でないとNを受け取れないことにまず注意します。各桁の数字を足していき、最後に9で割り切れるかどうかを確認します。
C-Step
前から順番にチェックしていきます。
一番前の人は台を使わなくてもいいです。自分の直前の人が、自分よりも背が高い場合は、差分を足し合わせていき、さらに、前の人の高さを自分の高さとして更新します。このように前からチェックしていくと、一つ前の人の高さを確認するだけで、条件をすべて満たすことができるようになります。
差分の合計が最小値になります。
E-Bomber
各行、各列ごとにいくつの爆弾があるかをそれぞれカウントし、一番多い行と列の数字を足し合わせます。この時、選んだ行と列の交点にあたるマスに爆弾がある場合は重複してカウントしていることになるので、足し合わせたものから1引く必要があります。最多の行ないし列が複数ある場合もあるのでその点にも注意が必要です。
各行と列については行番号列番号と爆弾の数をpairにしたvectorで管理しました。爆弾の位置も管理しないといけないため、初めは二次元配列で管理しようとしましたが、サイズが大きくてバグっていることに気が付きませんでした。爆弾の数は30万個以下なので、setでx、y座標を管理することで交点についてチェックできるようにしたところACとなりました。
今回は以上です。
Dも出来そうで出来ない状態なので、早めに通しておきたいです。
AtCoder Beginner Contest 175に参加しました
ABC175に参加しました。
コンテスト中にD、Eの解法が分かったはずなのですが、ACしきれずに三完でした。Cまでがそれなりの速さで解けた点についてはよかったと思います。
D、Eが解けそうで解けない状態が続いて、だらだら書かないまま三週間もたった上にまだ解き切れていないという体たらくです。
とりあえずA~Cをまとめておきたいと思います。
Tasks - AtCoder Beginner Contest 175
All Submissions - AtCoder Beginner Contest 175
A-Rainy Season
方針をちょっと迷いました。
3日間しかないという点に注目することにしました。まず、雨の日の回数を数えます。雨の日の回数が2回以外は、特にこれ以上の操作を必要としません。0日と1日の時は晴れの日の位置の影響を受けませんし、3日の時は晴れの日が1日もないからです。2日の時は、2日目が晴れの場合のみ、雨の日が連続していた最大の日数が1日になります。
B-Making Triangle
本数がたかだか100本しかないので、全通り試すことができます。i<j<kの組である(j<i<kなどとなってはいけない)という点に注意して、三重のfor文だけで解くことができます。
最初に小さい順にsortしておけば、三角形が成り立つかどうかを判定する際に簡潔に書くことができます。三辺をA,B,Cとして、A<B<CであればA+B>Cの一つの条件式で判定可能です。当然A<B<Cである保証がない場合は、B+C>A,C+A>Bも確認する必要があります。
C-Walking Takahashi
最小値の候補となる値は二つあります。0に向かって行ってぎりぎりで止まるか、そこからさらに一度だけ進むか、です。二つ手前で止まったり、二つ向こうで止まったりするよりもぎりぎりのところで止まる方がよいです。このように考えるとき、ぎりぎり手前で止まるか、一度だけ進んだところで止まるかは2で割って、余りが出るかどうかで判断することができます(必ずK回ちょうど移動する必要があるため)。
コンテスト中に解けたものは以上です。
過去に参加したコンテストで、復習してACできたものも追記していきたいです。
AtCoder Beginner Contest 174に参加しました
ABC174に参加しました。
CとFでハマって結局ABDの三完でした。
つれえ～～～～～～～～～。
A-Air Conditioner
何もいう事がないです。
B-Distance
NとDが先に与えられているので、各点の値を受け取るたびに逐一計算していくのが楽かと思います。
sqrtで平方根を計算してもいいですが、単純に二乗した状態で比較すればいいだけです。制約が2*10^5なのでオーバーフローしないように整数型には気を付けます。
C-Repsept
ドツボポイント1。かなり混乱してまともに考察できませんでした。7の数列の中で、最初にKで割り切れる数がどこにあるかを答えるという問題です。
冷静に考えると、Kで割るので余りの種類はK通りしかありません。さらに、項が1大きくなるごとに桁数が1増えていき、新しい桁には7が入ります。一般化すると、(前の項をKで割った商*K)*10+(前の項をKで割った余り)*10+7ということになります。つまり、ある項が割り切れるということは、(前の項をKで割った余り)*10+7がKで割り切れるということです。ひっ算をイメージするとわかりやすいです。ここで、Kで割った余りの種類に関心を戻すと、K種類しかないということはK+1桁目まで確認すれば必ず重複する余りが出てくることになります。余りが重複した場合、余りを10倍して7を足しても当然先の結果を繰り返すことになり、ループすることになります。こうなった場合は割り切れる数が数列に登場することはあり得ないので、-1を出力します。
コンテスト中は、Kが7と互いに素かどうか、11...1を割り切れるかどうか、などに注目して考察を進めてしまった結果、さっぱりわからなくなってしまいました。
D-Alter Altar
左から順にすべての赤い石を並べ、その後に白い石を並べるようにしたいということです。
操作が二種類ありますが、石の色を変える操作は使わなくてもいいです。というのも、操作を行わなければならない時というのは、どこかで赤い石の左に白い石があるときです。この時に、一番左側にある白い石と一番右側にある赤い石を入れ替えると、条件を確実に満たして、二か所の石の色を変更することができます。一つしか選べない操作をする必要はないことが分かります。
コンテスト中は、右からどこまで見ていったかを保持する変数を用意して左から順に確認していきました。白い石が出てきたら、右端から順に確認していき、赤い石が出てきたらカウントして、また左から見ていくようにします。左右から見ていっており、災いを招く置き方になっているところは逐次入れ替えているので、右側から一度見たところを左側からチェックする必要はありません。
E-logs
コンテスト中はよく分からなかったので飛ばしました。
貪欲的に考えようとしましたが、毎回なるべく半分になるように切ると最適ではないので(ex.貪欲に10を一回切ると5,5、もう一回切ると5,3,2になるが、二回切るのであれば当然4,3,3となるように切る方がよい)、この辺りまで考えて無理っぽいと判断しました。
解説を見て、二分探索は知っていたので、「こういう時に使うのか～」と感心しながらコードを書きました。関数を作ってコードをすっきりさせようと意識してみたら、かなり見やすく書けたような気がします。加えて、変数名に統一感を持たせたりした方がいいんだろうなと思いながらも問題ごとに適当に考えて使っているのを、やめたほうがいいような気がしました。
実装の方針としては、出力の最小値は、切る回数が十分多い時に、1になり(切り上げのため)、出力の最大値は、切る回数が0回である時に、Aの最大値になります。Aを小さい順にソートしておくことで、二分探索を使うことができます。ある値が条件を満たすかどうかはO(N)で判定できるので、O(N*longN)で時間制限をクリアできます。
二分探索と、条件判定を別々の関数に分けて書くとかなりすっきりしてよかったと思います。
F-Range Set Query
ドツボポイント2。
ある位置までに出てきた石の種類とその個数をmapで管理して、クエリごとに差分を計算してみる、という単純な方法を思いつきました。時間が間に合うか微妙な気がすると思いながら投げたところ、2270msほどでした。270msなら何とか高速化できないかなあと思って粘ったのが失敗でした。順位表を見たら結構ACしている人が多かったので、方針はあっていて何か見落としているだけかもしれないと思ったからです。グーグル先生に聞くという発想も出てきませんでした。
解説は見たので、Seg TreeやFenwick Treeについて勉強してからACしておこうと思います。
今回は以上です。
せめてCは落ち着いて解いておきたかったです。珍しくFまで分かるような回だったので復習しておきたいですね。
M-SOLUTIONS プロコンオープン 2020
参加しました。
とりあえず四完でしたが、もうちょっと頑張りたかったです。
Tasks - M-SOLUTIONS Programming Contest 2020
All Submissions - M-SOLUTIONS Programming Contest 2020
A-Kyu in AtCoder
200点ごとに級が分かれているので、for文で繰り返し200を引いていくことで出力を得ました(1回引いて400点未満になれば8級、2回なら7級、3...)。繰り返し引くということは割り算そのものなので、なぜわざわざfor文を使ったのかコードを書き終えてから疑問に思いました。
B-Magic 2
真に大きいという言い回しはAtCoderではあまり見ないように感じましたが、サンプル2から、(ある数)より大きいという意味(その数を含まない)で解釈しました(4を一度2倍して8、2を二度2倍して8で、合計3回の操作になるが、これは成功ではないとなっている)。
シンプルにBがAより大きくなるまで2倍し、その操作後のBよりもCが大きくなるまで2倍して、操作回数を数えました。操作回数をKを比較して出力を得ることができます。
Aに操作を行うと、BとCの必要操作回数が増える可能性はあっても減る可能性はありませんし、Bも同様にAを越すギリギリの回数よりも多く操作を行っても、Cの必要操作回数が増える可能性が生まれるだけになります。
C-Marks
評点は直近K回の期末テストの点数を掛け合わせたものになるので、ある学期の評点とその一つ前の学期の評点は、決定するために勘案する点数の大半が重複しています。重複していない部分は二か所だけで、ある学期の期末テストの点数と、一つ前の学期の評点に勘案される一番最初の期末テストの点数だけです。ある学期の期末テストの点数は当然一つ前の学期の評点には影響せず、一つ前の学期の評点に勘案される一番最初の期末テストの点数は、ある学期の評点には影響しません。
以上のことから、K+1学期から順にi-k学期の期末テストとi学期の期末テストの点数を比較していきました。
A-Road toMillionaire
方針はすぐに固まったものの、コードの間違えている部分を修正するのに時間がかかって勿体なかった問題です。
安い時に買って、高い時に売ると儲かるというふんわりしたセオリーはなんとなくわかります。買い時と売り時を同時に考えるとややこしいので、初期の状態から考えることにします。まず、株を持っておらず所持金が1000円のところからスタートになります。ですので、どういうときに株を買えばいいのかから検討しました。基本的に1日目に株を買ってはいけない状況というのは、2日目の株価が下がっている時です。1日目は何もしないで、2日目に株を買う方が安くたくさん買えるからです。逆に、2日目に株価が上がっていれば1日目に買っておくべきです。2日目に売ることで確実に利益になるからです。買い時については、2日目以降も同様に考えることができます。翌日の株価が今日よりも安くなっているのであれば買うことは控えます。
買い時については決定しました。次は売り時について考えます。基本的には買い時ではない時に売るべきです。つまり、翌日の株価が下がっている時です。この場合は今日すべて売ってしまうことで、翌日により多くの株を買うことができます。
また、株を売るときや買うときは持っている株やお金をすべて使うべきです。一番安い時に買っているので、所持金があるのに買い控えると次に売るときの金額が少なくなりますし、逆に売るときに株を残しておいても次に買うときの資金が少なくなるからです。
持っているお金や株を、取引をする場合は都度すべて使うように気を付けて、前述の基本方針に則って取引をした場合、株を買うお金がないのに株を買うべき日や、株がないのに売るべき日があります。しかし、このような場合は前日までにより株価の安い日に株を買い切っていたり、より株価の高い日に株を売り切っているということになります。なので、これらの状況は無視していいことになります。
コンテスト中は買い時と売り時をチェックして配列にメモしていき、その後前から順に買い時と売り時にそれぞれ操作して出力を得ていました。今考えると、あらかじめ買い時と売り時をチェックしておく必要は特になさそうです。
コンテスト中に時間がかかったのは、買い時と売り時をメモしていく際に買値の更新を間違えていることに気が付かなかったからです。特に必要のない手間を増やして、さらにそこでバグらせていたのでかなり嫌な気持ちになりました。
今回は以上です。EとFはかなり厳しいですね…。
エイシング プログラミング コンテスト 2020
参加しました。
難しかった～。
Tasks - AIsing Programming Contest 2020
All Submissions - AIsing Programming Contest 2020
A-Number of Multiples
dで割った商がdの倍数の個数なので、RとL-1をdで割った差を取りました。Lがdで割り切れる場合は答えに含まれることに気を付けます。
B-An Odd Problem
Nは100以下なので、前から順にみていくだけでいいです。
C-XYZ Triplets
かなり変な解き方をしました。
1以上N以下の各iについて、x,y,zをx<=y<=zの順に固定して、1<=x*x<=nの範囲でそれぞれ動かしました。iに一致していた場合はx,y,zの重複具合に応じて答えに加算していくことで答えを得ました。3つが一致していれば1、2つであれば3、一致するものがなければ6です(x,y,zの大きさの順を固定していたが、実際には大きさの順は決まっていないため)。
わざわざややこしい方針で解いてしまったので、実行時間もぎりぎりでした。
一応解説を見てACし直しました。
今回は以上です。
D以降は厳しかったです。Dは一回目の操作をうまく処理できませんでした。
近いうちにACしておきたいです。
AtCoder Beginner Contest 173
ABC173に参加しました。
Dまでをそれなりの速さでペナルティを出さずに終えられたのでよかったです。
Eがかなりつらいですね…。
Tasks - AtCoder Beginner Contest 173
All Submissions - AtCoder Beginner Contest 173
A-Payment
Nを1000で割った商に1を足して、それを1000倍してNで引きました。
Nを1000で割った商が0以外なら1000から引く、という方が簡単でいいですね。
B-Judge Status Summary
入力を受け取る際にif文を4回書いて計数しました。
C-H and V
なんか最近bit全探索多くないですか？
すぐ思いついて書くことができてよかったです。前よりかは早く書けるようになりましたが、まだまだ遅いので練習したいですね。
D-Chat in a Circle
フレンドリーさの大きい人から訪ねていくようにすると最大化できることが分かります。大きい人から訪ねることで、原則その人がきた直後に左右両隣に来た人はその人の心地よさを感じることができます。この原則が当てはまらない人は一番最初に訪れる人の見になります。
E-Multiplication 4
めちゃくちゃつらい。
N個がすべてマイナスかつKが奇数の時にしかマイナスになることはないということは分かりました。1つでも0以上の数があれば、偶数個のマイナスを選び、Kが奇数でも非負整数でKに合うようにできるからです。
コンテスト中はマイナス同士をかけたものとプラス同士をかけたものを比べて大きいほうを使う、という方針で実装しようとしました。この時、マイナス同士は2つ使わないとプラスにならないのですが、プラス同士は1つだけでもプラスなので1つずつ使うのが最適です。しかし、これには気が付きませんでした(例えば残り3個選ぶ必要があり、{-6, -3, 1, 4, 5}が選択肢の場合、4*5=20、(-6)*(-3)=18となりますが、5*4*1=20ではなく、(-6)*(-3)*5=90が最大になる、など)。
コンテスト後は絶対値が大きいものから掛け合わせて最後に符号を調整しようとしましたが、いまいち雑なせいでまだACできていません。
今回は以上です。
EはAC出来そうで、これまではACしてから書いていたのですが、記憶が薄れる前に書いたほうがいいかなということで先にまとめておくことにしました。
Fも難しくないようなのであわせてACしておきたいです。
