AtCoder Beginner Contest 175に参加しました！ + 最近やってたこと
タイトルの通り先週末はAtCoder Beginner Contest 175に参加しましたー。
ABCの三問しか解けなくて悔しかったけどパフォーマンスは1119なので緑ぐらいのパフォーマンスにはなりました！
C問題を開始20分で解けて気分良くD問題に行けたのですが、結局Dをうまく通せずに終わってしまいました。
atcoder.jp D問題、Kの範囲に対してNがむっちゃ小さい+飛び先が自分自身でない事から循環しうる事がまず分かって、一周した時に0より大きいかで場合分けが必要なのもなんとなく分かってパフォーマンス的にもO(N2)程度で済みそうやしいけるかなと思ったものの、これ結構大変じゃない？？ってなって解くのにひよってしまいました。Dなんだからもっと簡単なのあるでしょ？とか思って20分ぐらい悩んでも思いつかないから諦めて循環見つけようってなりました。多分一般には循環は深さ優先探索で見つけるんだと思うんですけど、グラフアルゴリズムはまだあまり勉強してない状態だったのでこの前趣味で書いたFloydのうさぎとかめのアルゴリズムを使いました。 Floydのうさぎとかめのアルゴリズムは動画でたまたま知って面白かったのでその時に実装しました。
でも今思うと循環を難しく考えすぎですね。
今回の場合なら循環の開始地点と開始地点は一致すると考えていいので、単に開始地点をメモって、開始地点に戻ってくるまでfor文を回すだけで十分ですね。
で、一周させた時にスコアが0より大きいなら何周もさせればどんどん大きいスコアにする事ができます。一方で0より小さいなら何周もさせる意味は無いので一周させる中でベストの値を返せば良いです。ここまでは制限時間内に思いついてそこそこ通るものができたのですが、いくつか通らないまま終わってしまいました。何で引っかかっていたかというと一周のスコアが0より大きい場合に先に周れるだけ周ってからあまりを足してたんですけど、それが良くなかったんですよね。
4 40 3 1 4 2 1000 2000 4000 -6000
↑みたいな入力の時って10周させるよりも9周して残りいい感じのところでやめた方がいいスコアになるんですよね。なので周るだけ周ってからあまりを進むのではなく、一周回るまでの範囲で連続する長さをいろいろとって、残りの値で周れるだけ回った中で一番いいスコアをとるのが実際はいい戦略になります。こういうの結構教育的ですね。端数をあまり雑に扱うと痛い目をみるんだなーって思ったので次からの教訓にします。Eからは見てないです。正確にはEはチラ見してそっ閉じしました。問題にはなんか見覚えあると思いつつ全然分からなかったので諦めました。
前のABC174から二週間あって、その間はほとんどCとDの問題を解いていました。全探索とか合同式を使う問題をパッと解けたいなーと思ってその辺を勉強していました。2値の全探索ならbit演算でシュッとかけると思うんですけど3値以上のめんどくさいやつの時の実装がなんかうまく書けないなーってなってました。一回アドリブで再帰を使って実装したんですけど、こちらの記事にきれいにまとまってるように考えて書くとすごくいい感じになりました。
あとは「アルゴリズムイントロダクション」とか「離散数学への招待」みたいな本を読んでました。まだちゃんと勉強できてないんですけどマトロイドとかいうやつむっちゃかっこよくないですか！？凸関数の一般化みたいな感じっぽいですね。凸関数、最適化がスムーズにいくのがイメージつくと思うんですけどそれをもっと抽象化する事で貪欲法が使えるかを判断できるって感じですよね。ちょーかっこいい！！なんか面白そうだからちゃんと勉強したいですね！！
あとはなんか急にどうやってグラフって描画されるんだろう？ってのが気になってコンピューターグラフィクスのラスタライズのアルゴリズムを調べたりしてました。アルゴリズムの勉強、なんか自分の肌に合ってる気がしているのでもっと深くやっていきたいです。
