読者です 読者をやめる 読者になる 読者になる

AtCoder Regular Contest 050に参加しました

昨日行われた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問題 花束

入力が{R,B,x,y}とあって、{(x,1)}の束をa個、(1,y)の束をb個作るとすると、できる花束の総数M M = a + b 個となるのでこのMを最大化すれば解けるのではないかと考えました。このとき、赤い花による条件は ax+b \leq R , 青い花による条件は a + by \leq B となり、b = M - a からbを消去すれば
{\displaystyle
M \leq R - a (x-1)
}
{\displaystyle
M \leq \frac{B - a}{y} + a
}
という不等式を両方満たせば良いことになるので、つまりaが定まったとき {\displaystyle
M = \min(R - a (x-1),\frac{B - a}{y} + a )
}
ということになります。  a = 0 から  a = \frac{R}{x} まで変化させたときの M の最大値を返せばいいのではないかと考えましたが、最大とする a を三分探索で求めようと実装していたところで時間が尽きました。この方針でいけるのかわかりませんが実装を速くしないと試せるアイデアが少なくてもどかしいですね。 解説では花束の数を与えれば二分探索で解けるとのこと。二分探索は数式に使える条件が増やせるし関数の返り値はbool型で良いしで、ぜひとも適用できるかどうかを見極める力を身につけたいテクニックですね。

C問題 LCM 111

愚直に処理をプログラム化しただけでは絶対通らないんだろうと思いつつも、ユークリッドの互除法の実装をしたことがなかったのでその練習も兼ねてということで小さいサンプルだけ通るようなものを書いて提出もせずに終了。ユークリッドの互除法は引数の2整数の大小関係を気にしない書き方ができるらしいのですが、いちいち大小関係見てスワップさせながらみたいな実装をしました。こういうところもなんとかしたいですね。書いたコードを他のコンテストで再利用するってどういう方法が最適なのかわからず、とりあえず今は手を動かすことを再優先にやっています。 解説を聞いたあとでも、多分うまく大きい数を関数でバラしていくあたりが実装できないんだろうなと思いました。まぁ慣れればなんとかできるんじゃないかと思いますが。

D問題 Suffix Concat

コンテスト中は問題文を読みすらしてなかったのですが、解説を聞く限りとても難しそうでまだ手の届くものではなさそうだなという感じです。

A問題のタイムアタックみたいな状況からは一歩抜け出したいですね。