blog.sorah.jp

CTPC (College of Technology Programming Contest) 参加記

journaltech

高専生向け競技プログラミングコンテストらしい。 http://koj.cms.am/contest/index.html

起きたら twitter の TL で話題になっていたので寝起きで参加しました。

結果: 400/1100点 (39/65位), 2 WA.

といた順番は A→C→B→E. A の後 B は一見難しそうに見えて C を解き、その後他の問題を物色して E を解き始めたのだけど、 途中これはグラフ理論とか使うのかなあ、と思って物色を再開した所、実は B が簡単だった事に気づいて B を解き、時間が余った。E をもう一度見たら実は Time Limit 8 秒とか入力の制約を見るにシンプルな 探索でも通るだろうということで再度解き始めて、ギリギリで通した。

問題 A - Average

http://www.atcoder.jp/problem/detail/151

改行区切りで 4 つの数値が与えられるので、(それらの最高値+それらの合計)/5 を求め、60 以上であれば Yes, 60 未満であれば No を表示すれば良い。

Codeforces とかだと YES, NO (全て大文字) なのでそこで引っかかってる人が多かったイメージ。

コード

きたないですね。

問題 B - Macaron

http://www.atcoder.jp/problem/detail/152

幅 W 高さ H の盤面 (自分は空白マスを false, 壁マスを true とした) を用意、その後 X, Y, L の 3 つの数値がスタンプとして与えられるので、 座標 (X,Y) 中心に L 間隔の正方形の形になるように盤面のマスを反転 (空白マスなら壁マスへ、壁マスなら空白マスへ) した。 自分は前述のように bool で管理したので ! つかって反転させるだけ。らくちん。

正方形の作り方は、n を任意の 1 以上の整数として、 頂点の座標は X, Y に下の式から求められる数値を足したり引いたりすれば求められる。(コードでは 27 行目の変数 s への代入)

s = L + (L+1)(n-1)

左上、右上、左下、右下の座標は以下のようになる:

  • 左上: (X-s,Y-s)
  • 左下: (X-s,Y+s)
  • 右上: (X+s,Y-s)
  • 右下: (X+s,Y+s)

処理は n を初期値 1 でループを回し、まず頂点を反転し頂点と頂点の間の線となるマスも反転、 一つの正方形の処理において反転させようとしたマスがすべて盤面の外ならループを打ち切り、 そのスタンプの適用を終了して次のスタンプの適用に入る。

そして与えられたスタンプを全部適用したらおわり。それを整形して表示するだけ。

もっと賢い方法あるのかなあ。

日本語が書けないのでうまく解説できないな。しかし。

コード

問題 C - Communication Tool

http://www.atcoder.jp/problem/detail/153

n つの文字列が改行区切りで2行目以降に入力されてくる。

それぞれの文字列は以下のルールに従ってカテゴリ分けできる。

  • その文字列は 1 文字以上 140 文字以下であるなら Tw○tter からの情報 であり、また:

    • @ で始まる文字列であるなら リプライ
    • @ で始まらない文字列である つぶやき

  • それ以外の文字列 (リプライでもつぶやきでもない) はすべて mix○ または gre○ からの情報となる。

表示するものは つぶやき と リプライ の割合であるため、リプライでもつぶやきでもない文字列は無視して問題がない。 また文字列自体もどうでもよくただ個数だけ数えれば良い。

割合については以下のように求めて (C++ なのでつぶやきとリプライを数えた変数を double 型にしておく) 小数点以下を切り捨てたものを表示すれば良い (C++ だと普通に int にキャストしてしまえば良い)

つぶやき もしくは リプライ / (つぶやき+リプライ)

しかし入力によっては つぶやきもリプライも存在しない 事があるので、その場合は "NA" を割合の代わりに表示すれば良い。

この問題で Wrong Answer を唯一 2 回も出してしまって、理由はそれぞれ以下。非常にクズであると思います。

  1. NA を表示しなかった
  2. NA を表示する条件がどちらか片方が 0 以下だった (ひどい)。

|| から && に修正してやっと通った。

コード

問題 E - Airport

http://www.atcoder.jp/problem/detail/155

空港の名前と、空港同士の便 (出発地, 目的地) が与えられる。

与えられた空港と便を見て、以下の条件に当てはまれば Yes, 当てはまらなければ No を表示しろという問題。

  • すべての空港 A において、他全ての空港 B (A != B) との間に、便 A → B もしくは B → A が存在する事
  • 任意の空港 A, B (A != B) の間に、便 A → B と B → A 両方が存在しない事
  • すべての空港 A は空港 A から出発する任意の便に搭乗し、他の空港の便と乗継、最初に搭乗した空港 A に戻ってくる事ができる事

最初 3 番目の条件をみて間違いなく自分のコードだと Time Limit Exceeded になってダメだろうと思ったがよく制約と time limit を見ると、 time limit は 8 秒だったり、空港は最大でも 17 個、つまり便は最大でも 272 個なので幅優先で挑戦してみた。

(メモ化再帰の深さ優先探索とどっちが良いのかは知らない)

コード

  1. map で空港名 (string) をキーに Flights* (実態は vector<string>, 空港名を格納) を保管。空港毎にその空港からの便の行き先を列挙しておく。
  2. 便を受け取って Flight flights (Flight は ↑の map<string,Flights*>) に格納していく課程で、同じ空港同士で逆方向の便がみつかれば即座に No を表示して終了
  3. 便を Flight flights に保存したらとりあえず総当たりで 1 番目の条件に当てはまるか確かめ、当てはまらない物があったらその場で No を表示して終了。
  4. 最後に全ての空港に対し check_loop を呼び出して、3 番目の条件に当てはまるかを確かめる。一つでも当てはまらなければ No を表示して終了。

check_loop は queue 使った幅優先探索。

あと、最初 typedef vector<Flights*> Flights しようと思ったけどできないのね。残念。

反省

くだらない 2 WA は酷かった。 もうちょっと問題の難易度を推定して自分の実力で時間以内に解けるかどうかの判断を迅速に間違いなく下したいなあ。

@kyuridenamida さん, @kagamiz さんへ: 面白いコンテストをありがとう。次回はありますか?

Backfilled at , Published at