ZONeエナジー プログラミングコンテスト “HELLO SPACE”の感想
ZONeエナジー プログラミングコンテスト “HELLO SPACE”に参加しましたのでその感想を書いていきます。問題はこちらから。
結果はこんな感じでした。
問題：ABD(24:03)
順位：1396 / 7051
パフォーマンス：1303
エナジードリンクのZONe様のコンテストでしたので、私もエナジードリンクを飲んで臨みました。そのおかけか、いつもよりも早く解けたんじゃないかなと思います。WAもなく、落ち着いていたのもまた良いでしょう。ただ、難しい問題は解けませんね。今回に関しては考える時間こそありましたが、結果としては結構方針が違ってました。まだまだ先は長そうです。
感想いきます
A問題
どうやって解こうかな？と15秒ぐらい悩みました。
S[0] == 'Z' && S[1] == 'O' ...
みたいなことをやろうと思いましたが、書くのがめんどくさそうでしたので断念。結局、A = "ZONe"とし、
S.substr(i,4) == A
こんな感じでやりました。iの繰り返し回数に注意です。
B問題
少し悩みました。
N 個あるうちのどれか一つが邪魔するんだろうな、と思ってからどうすればその1本がわかるのかについて結構考えました。だって、高さと距離の2つのパラメータがあるんですもん。
結局、原点からの柱の頂点を見たときに一番首を上げなきゃいけないやつだということに気づきました。UFO側からすると頂点との傾きの大きさが一番小さいやつです。
追記：
これ嘘です。今回は人が動くためUFO側からみて塔との傾きが最も小さいものが適切となり、首のしんどさは関係ないです。
その傾きにて切片を求めました。ただ、サンプル2にて負の場合がありました。サンプルに救われました。
max(切片,0)にして無事ACです。次に行きます。
C問題
先にDを解きました。
30分ほど考えましたが方針が見えませんでした。考えたことを箇条書きにて、、
・2人を決めればあと一人はなんかうまいこと決まらないか？
・答えになりうる値は各パラメータの最小値のうちの最も小さい値い以下になる。
・もしかしたらO（N^3）通らないか？
結局解法は見えずE問題に行きました。
D問題
良く見る問題ですね。前回のABCでも似た問題がありました。
これは文字列でやると先頭に追加する操作が重くなってしまうので今回はdequeを用いました。といいましても、あとは前後のフラグに従って、前側と後ろ側から文字を入れていくだけです。
・dequeが空のときにアクセスしようとする
・「同じ文字が並んだら消す」を忘れる
により少々てこずりましたが無事ACです。WAが出なくてホッとしました。
E問題
Cが解けずにこちらに避難してきました。
まず、問題を理解するのに5分ぐらいかかりました。が、何とか無事理解できました。と思いきや誤読してました。
rが縦、cが横なのですが、r-i移動の際に
これは左への移動だ
と強く思い込むことにより、戻れなくなりました。このまま考察を進めます。こうなると縦は一方通行なので各行ごとに独立して考えることができます。ですので、左から i 番目から出発し、j 番目に行く際のコストなるものを計算しました。これをすべての i と j について行うと、その時点までの最短コストがわかります。一段下るときはそのコスト＋B[i][j]です。
これをdp[r-1][c-1]まで行えば無事答えです。というわけもなく、、残念ながらサンプルが合いません。１だけ合いません。２は合いました。不思議ですね。
結局、ここで間違いに気づきましたが時間切れでした。
F問題
見てないです。
あとがき
4月はレートがずっと下がっていたので、久しぶりにレートが上がったことは素直に嬉しいです。やっぱり、失敗してばっかだと気持ちがげんなりしちゃいますからね。たまには上がってくれるとありがたいです。
ただ、相変わらず解ける問題層はたいして変わっていないですね。ここをどうにかしたいです。今までは緑を落とさないように精進をしてきましたが、難しめの問題を時間をかけて解くことをやるべきなのかもしれません。どうしよう。
また今回も解説記事は書こうと思っています。とりあえず、すぬけさんの解説を聞いてお勉強をしてきます。
この記事が気に入ったらサポートをしてみませんか？