はじめに
天下一プログラマーコンテスト2015予選Bに参加しました。
tenka1-2015-qualb.contest.atcoder.jp
Klabさんが行っているプログラミングコンテストで、本戦に進めるのは学生だけなのですが、学生でなくても、上位に入ればTシャツを貰えるようなので参加しました。
Tシャツを貰える条件は
- 予選Aの上位20人
- 予選Bで、予選AでTシャツをもらった人を除いた上位20位
ということで、予選Bなら頑張ったらTシャツ貰えるのでは…と思って頑張りました。目標は40位以内です。
A - 天下一プログラマーコンテスト1998
計算するだけです。今回はcatは使わず、C++で書いたものをそのまま提出しました。
B - 天下一リテラル
{ が出現したら深さを+1, } が出現したら深さを-1します。深さが1のところに : が出た場合は dictになります。問題文をよく読むと、「入力が {}」の時も dict です。それ以外は set になります。
C - 擬二等辺三角形
まずは部分点を狙いました。凄い説明しづらいコードを書いてしまいましたがなんとか25点は獲得しました。部分点なら O(n) まで許容されます。
3辺の長さを a, b, c とします。b = a + 1 とし、このとき c が取りうる値の数をカウントしていくことにします。c は、以下の条件を満たすことになります。
- c < a + b
- a + b + c <= L
- c は 1 ではない（b = a + 1 なので c = 1 のとき三角形が成立しない）
- c != a かつ c != b
これだけの条件を満たせば、b = a + 1 の時に取りうる c 数が分かるのですが、ここで問題があります。
- a = 2, b = 3 だったとします。この時、c の候補には4が含まれています。
- a = 3, b = 4 だったとします。この時、c の候補には2が含まれています。
この2つの三角形は重複するので排除しなければなりません。そこで、c != a-1 とします。これで、a, b, c が連続する3つの数字になる時の重複を綺麗に取り除けます。
もうちょっとスマートな方法があるような気がしますが、今回はこれで解けました。後述のDの部分点を取ったあと、これの満点解法に挑んだのですが、解けませんでした… もう少しで解けそうな気がして解けませんでした。Lが 1012 まであるので、どうせ O(1) で解く方法があるのだろう…と思ったので、そのような場合は、適当に値を出力してみて、法則性を見つける方向に転換するべきなのかもしれません。失策でした。
D - 天下一電卓英作文
これも初めから部分点を狙いに行きました。アルゴリズムとしては、
- DFSで、入力できる候補の文字列を全て列挙する
- それぞれの文字列について、数字に変換し、大小比較をする
- もっとも大きな数字を選び、余分な0を削除する
- 出力する
といった感じです。
1. 入力できる候補の文字列を全て列挙する
ここがボトルネックになりますが、n <= 8 なら間に合います。
2. それぞれの文字列について、数字に変換し、大小比較をする
まず、数字は最大200桁までありえるので、今回はJavaのBigDemicalを使いました。一番後ろが0の場合は0.からスタートするようにし、後ろから文字を数字に変換していきます。
3. 最も大きな数字を選び、余分な0を削除する
問題文をよく読むと、0.2010 みたいな数字になった時は 0.201 という形式にして出力しないといけないとのことなので、小数の時は末尾の0は消します。2.000 みたいな数字は 2 と出力しなければなりませんが、この場合は 2000 にしたほうが数字がでかくなるので問題ありません。0.0000 と、0が連続する形になった場合は 0 と出力しなければいけません。
満点解法はDPとか？（適当）
E - 天下一演算
部分点とかあったら探索しようと思ったけどないので諦めました
結果
48位でした。
Cさえ解けばTシャツ獲得できたと思うのですが、完全に経験不足でした。十分有り得る範囲だったので残念です。まだまだ経験が足りません。もっと問題数をこなします。
