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

LoL/LJL好きのエンジニアのブログ

技術的な話やら、最近はLoLやLJLの話など。

天下一プログラマーコンテスト2015予選Bに参加しました

はじめに

天下一プログラマーコンテスト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 - 天下一電卓英作文

これも初めから部分点を狙いに行きました。アルゴリズムとしては、

  1. DFSで、入力できる候補の文字列を全て列挙する
  2. それぞれの文字列について、数字に変換し、大小比較をする
  3. もっとも大きな数字を選び、余分な0を削除する
  4. 出力する

といった感じです。

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位でした。

f:id:yoshiki_utakata:20150823102518p:plain

Cさえ解けばTシャツ獲得できたと思うのですが、完全に経験不足でした。十分有り得る範囲だったので残念です。まだまだ経験が足りません。もっと問題数をこなします。