ABC183の感想
AtCoder Beginner Contest183に参加しました。
問題はこちら。
結果はこんな感じでした。
3967 / 7199 位でパフォーマンスは557でした。
今回はabcの3完でした。悔しさを感じつつも、実力通りだと思わされる結果ですね。
毎度のことながら c 問題を解くのが遅いなーと感じます。また、d 問題を飛ばして e 問題に手を出していました。これに関しては、まあ悪くない判断であったとは思います。高跳び選手がバーをパスするあの感じですかね。結局解けませんでしたが、、、
感想を書いていきます。
A 問題
ReLU という問題名でした。
正の値はそのまま出力、マイナスの値は0となるReLU関数を実現する問題です。
機械学習の研究ではスパース性（疎、情報量の削減）の実現、また非線形性もあるということで、非常にお世話になる関数です。
問題名を見た瞬間に解答が浮かびました。max(0,x)で終了です。
B 問題
ボールを壁に当てたのち、目標地点に到達させる問題。この手の問題は高校数学の教科書によく出ています。
目標地点を壁と線対称の位置になるように座標変換をします。といっても、y = 0対称なので、y座標の符号を入れ替えるだけです。
あとは、(sx,sy)と(gx,-gy)を通る直線とy=0の交点の x 座標を求めてあげましょう。
C 問題
C問題は小さな巡回セールスマン問題(TSP)です。n 個の都市を訪問した際に時間が k となるものは何通りあるかを求めます。
TSPは全探索すると宇宙の寿命が尽きるといわれるnp困難の代表です。とはいうものの、本問題は n<=8であり、開始点も指定されているため、最大でも 7! で収まります。
ただ、この7!をどうやって全探索するか悩みました。どうしようと悩んでいるときに、偶然にもc++の「next_permutation」という関数に出会いました。本関数は{1,2,3}が与えられた際に、
{1,2,3}{1,3,2}{2,1,3}{2,3,1}{3,1,2}{3,2,1}
といった感じで、全通りの順列を表現してくれます。この関数を引っ提げて順列全探索を実装したら解けました。
ただ、結構な時間悩んでました。
D 問題
n 人がお湯を奪い合う問題です。この問題は5~10分ほど考えたのち、e 問題をちらっと見たら 「dpになんかすれば解けそうだなー」ってなったので飛ばしました。
一応解答は見ましたが、シミュレーションをしても工夫次第で間に合うみたいですね。あと、imos法という方法も紹介されていました。他の問題を解く中で、この手法の名前は見たことあるんですが、詳しくは知りません。これを機に勉強しておきます。
E 問題
チェスにおいてクイーンが目標地点にたどり着く方法は何通りあるかという問題。
なんか解けそうな波動を感じたので、D問題を飛ばしてこちらに時間を割きました。
まず、愚直にdp を組みました。右、下、右下方向の遷移を書くだけなので、比較的あっさりと終わりました。制約も 盤面の縦横 <=2000 で、「もしかしたら、もしかしたら！！」と思いながら提出したらTLEでした。
まあ、そうですね。わかってはいました。
各方向の遷移において、たびたび同様な遷移が繰り返されていますので、累積和をもってうまいことやれば解ける、という謎の自信がありました。ただし、実装中に時間切れとなりました。100分って短いですね。
他の方の解答によると、累積和の方針はあっているみたいなので、もうちょっと実装を続けてみます。
F 問題
見てないです。
今回はパフォーマンス的には満足いかないのですが、まあ3問解けているのでよしとしました。ギリギリですがレートも上がっていますし。
反省することは多々ありながらも、よく学べたコンテストだったのかなと思います。
よく学べたと書いてしまいましたが、学ぶのはこれからですね。しっかりと復習をして解答記事を書いていきます。
この記事が気に入ったらサポートをしてみませんか？