昨日行われたAtCoder Regular Contest 050に参加しました。
結果はA問題しか解けず、100点の259位でした。200点取れると順位がふた桁以内になるようなので頑張りたいところですね。
以下各問感想
A問題 大文字と小文字
最初A-Zとa-zは数字が続いているものと思っていたので入力をAとaで受け取ったとすると A - a == 26
とすれば判定できるのではないかとか考えていました。やってみると全然違う数字が出てきてしまったので、しばらく悩んだあと諦めて小文字の方にtoupper()
を適用して比較しました。解説放送であったとおり A - 'A' == a - 'a'
と比較すればスマートにやれたのですね。解説放送のコメントでXORを使うとかもありましたが、よくわからないですしまだそんなことを気にするレベルではないかなという感じもします。
B問題 花束
入力がとあって、の束を個、の束を個作るとすると、できる花束の総数は個となるのでこのを最大化すれば解けるのではないかと考えました。このとき、赤い花による条件は , 青い花による条件はとなり、からを消去すれば
という不等式を両方満たせば良いことになるので、つまりが定まったとき
ということになります。
から まで変化させたときのの最大値を返せばいいのではないかと考えましたが、最大とする を三分探索で求めようと実装していたところで時間が尽きました。この方針でいけるのかわかりませんが実装を速くしないと試せるアイデアが少なくてもどかしいですね。
解説では花束の数を与えれば二分探索で解けるとのこと。二分探索は数式に使える条件が増やせるし関数の返り値はbool
型で良いしで、ぜひとも適用できるかどうかを見極める力を身につけたいテクニックですね。
C問題 LCM 111
愚直に処理をプログラム化しただけでは絶対通らないんだろうと思いつつも、ユークリッドの互除法の実装をしたことがなかったのでその練習も兼ねてということで小さいサンプルだけ通るようなものを書いて提出もせずに終了。ユークリッドの互除法は引数の2整数の大小関係を気にしない書き方ができるらしいのですが、いちいち大小関係見てスワップさせながらみたいな実装をしました。こういうところもなんとかしたいですね。書いたコードを他のコンテストで再利用するってどういう方法が最適なのかわからず、とりあえず今は手を動かすことを再優先にやっています。 解説を聞いたあとでも、多分うまく大きい数を関数でバラしていくあたりが実装できないんだろうなと思いました。まぁ慣れればなんとかできるんじゃないかと思いますが。
D問題 Suffix Concat
コンテスト中は問題文を読みすらしてなかったのですが、解説を聞く限りとても難しそうでまだ手の届くものではなさそうだなという感じです。
A問題のタイムアタックみたいな状況からは一歩抜け出したいですね。