競技プログラミング初体験会

先日27日，工学院大学の競技プログラミングやっている方々にお招きいただき，競技プログラミングを体験してきました．

C++とかほとんど触ったことない言語で関数ググりながらでしたが，みごと1位になりました！

以下，さくっとまとめ

工学院大学 競技プログラミング

  • 2時間30分，言語はC++11

A. +-数列の和

  • Time Limit: 2 sec.
  • Memory Limit: 65536 KB

概略

  • 先手と後手がおり，先手が正の整数を記す．
  • その後お互いは相手の最後に記した数字の正負反転し，絶対値を+1した値を記す．
  • 一定回繰り返した後，それらの数字の総和を求める．

入力

H N
  • H: 最初の数値
  • N: 記した数字の個数
  • 入力はすべて整数
    • {0\leq H\leq 100}
    • {0\leq N\leq 100}

出力

  • 数列の和を求めること．ただし，出力末尾には改行をいれよ．

解説（というよりメモ）

  • for文
  • 数列を考える

自分の解答

感想

  • 最初，answerの値を初期化せずに使っていて，わけのわからない数値が出ていた．
    • 普段使っている言語は，暗黙的に0で初期化されているから忘れてた．
    • こういうところも勉強になるので，とてもよい．

B. フランクフルト

  • Time Limit: 2 sec.
  • Memory Limit: 65536 KB

概略

  • 60分を1分刻みで記録した並び始めた客数とフランクフルトが焼けた時刻と本数が渡される．
  • 最終的に渡せた客の平均待ち時間を求めよ．
    • ただし，渡せなかった客は考慮しない．

入力

C1
C2
...
C60
S
T1 F1
T2 F2
...
Ts Fs
  • Cn: n分目に並んだ人の人数
  • S: フランクフルトを焼き上げた回数
  • Ti: 焼き上げた時刻
  • Fi: 焼き上げた本数
  • 入力は以下を満たす
    • {1\leq S\leq 60}
    • {1\leq T_i\leq 100}
    • {1\leq F_i\leq 100}

出力

  • 客の平均待ち時間を求めること．ただし，出力末尾には改行をいれよ．
    • また，絶対誤差は0.01以下になるようにせよ．

解説（というよりメモ）

  • キューを使った待ち時間行列

自分の解答

感想

  • 最初，入力が多くて気が滅入ってしまい後回しにしていた．
  • しかし，仕組みさえ思いつけば簡単な問題だった．早くやっておけばよかった．

C. フランクフルトとパン

  • Time Limit: 2 sec.
  • Memory Limit: 65536 KB

概略

  • 予算とパン，フランクフルトの値段，パン1セット内のパンの個数を渡される．
  • パンはセットでしか購入できない．
  • フランクフルトは（1セットのパンの個数-1）個余分に確保しても良い．
  • 予算内で，できる限り購入した際の残高を求めよ．

入力

M
F B
N
  • M: 予算
  • F: フランクフルト1本の値段
  • B: パン1本の値段
  • N: パン1セット内のパンの個数
  • 入力は以下を満たす
    • {1\leq M\leq 1000000}
    • {1\leq F_i,B_1\leq 10000}
    • {1\leq N\leq 100}

出力

  • 予算内で，できる限り購入した際の残高を求めよ．ただし，出力末尾には改行をいれよ．

解説（というよりメモ）

  • for文
    • 所持金を引いていく
  • 計算で求める（割り算）

自分の解答

感想

  • 式するだけなので，簡単な問題だった．
    • だが，コードに落とし込んだ時の些細なミスで時間をかなり喰った．

D. フランクフルトとパンとホットドック

  • Time Limit: 2 sec.
  • Memory Limit: 65536 KB

概略

  • 販売価格と原価，仕入れ個数，損益が与えられる
  • 売り上げた個数を求めること．ただし，入力値が実現不可能な場合は-1を返すこと．

入力

Hp
Hc
K
M
  • Hp: 販売価格
  • Hc: 原価
  • K: 仕入れ個数
  • M: 損益
  • 入力はすべて整数
    • {1\leq H_c\leq H_p\leq 100000}
    • {1\leq K\leq 10000}
    • {-1000000000\leq M\leq 1000000000}

出力

  • 売り上げた個数を求めよ．ただし，出力末尾には改行をいれよ．
    • 入力値が実現不可能な値だった場合は，-1を出力せよ．

解説（というよりメモ）

  • for文で回しながら計算
  • （自分は）計算だけで解いた

自分の解答

感想

  • 立式して整理すれば簡単だった．

E. Follow me!

  • Time Limit: 1 sec.
  • Memory Limit: 65516 KB

概略

  • ツイート内容が渡されるので，ユーザ名を数えよ．
    • ユーザ名は，@から始まり，半角英数字（大小含む）とアンダースコアでなりたつ．
    • また，ユーザ名は@を含めて5文字以上10文字以下である．

入力

N
S1
S2
...
Sn
  • N: 与えられるツイート数
  • Sn: ツイート文字列
  • 入力は以下を満たす
    • {1\leq N\leq 10}
    • {1\leq |S_i|\leq 1000}
    • |S_i|は，i番目の文字列の長さを表す．

出力

  • ツイートに含まれるユーザ名の個数を求めよ．ただし，出力末尾には改行をいれよ．

解説（というよりメモ）

  • 全文見て定義のものを数える
    • スペースで分割してそれらを後ろから探索する

自分の解答

感想

  • 正規表現を使ってしまった．
    • C++11から使えると聞いていたが，ideoneでは動作しなかった．
  • 標準入力を行ごと取るのに苦戦した．
    • >>を使うのとgetline()は併用できないらしい．（詳しく調べてないが，うまくいかない）

F. R君のお絵かき①

  • Time Limit: 1 sec.
  • Memory Limit: 65516 KB

概略

  • 線図が渡されるので，一筆書きが可能か判定せよ．

入力

N M
A0 B0
A1 B1
...
Am-1 Bm-1
  • N: 頂点数
  • M: 辺の数
  • Ai Bi: 頂点AiとBiを結ぶ辺を表す．
  • 入力は以下を満たす
    • {1\leq N\leq 20}
    • {1\leq M\leq 20}
    • {1\leq A_i\leq N}
    • 頂点番号は1からNの順に割り当てられる．

出力

  • 一筆書きできる場合は"YES",できない場合は"NO"を出力せよ．ただし，出力末尾には改行をいれよ．

解説（というよりメモ）

  • 一筆書きの条件
    • 奇数本の辺が接する頂点が0または2である

備考: 非連結グラフの場合

自分の解答

感想

  • 一筆書きの条件があることは知っていたので，ググった．
  • 配列の番号と頂点番号は1ずれることを忘れて書いていたけど通ってしまった．（上のは修正版）
    • おそらく0または2を2以下と緩く条件指定していたからだと思う．

G. 隕石村のCくん

  • Time Limit: 1 sec.
  • Memory Limit: 65516 KB

概略

  • 次のいずれかで隕石が落ちるので，隕石以外を通り家から大学へ行く最短歩数を求めよ．
    1. 1x1のマス
    2. 3x3のマスを十字，座標は中心座標
    3. 3x3のマスすべて，座標は中心座標
  • ただし，家と大学には隕石が落ちないものとする．
  • また，マップ外には出られないものとする．

入力

W H
Cx Cy
Gx Gy
N
r1 x1 y1
r2 x2 y2
...
rn xn yn
  • W: マップの横幅
  • H: マップの縦幅
  • Cx,Cy: 家の座標
  • Gx,Gy: 大学の座標
  • ri: 隕石の落下タイプ（上記参照）
  • xi,yi: 隕石の座標
  • 入力は以下を満たす
    • {1\leq W\leq 20}
    • {1\leq H\leq 20}

出力

  • 家から大学までの最小歩数を求めよ．ただし，出力末尾には改行をいれよ．

解説（というよりメモ）

  • 幅優先探索
    • 今回マップは広くないため，計算量はあまり考慮しなくて良い．
    • 幅優先はキューを用いる
  • 隕石の位置記録は，余分に配列を作れば例外処理が不要

自分の解答

  • 解けなかった

感想

  • 解説聞いて，こういう考え方があるのかと勉強なった．
  • よく考えれば，こういうものこそ競技プログラミングですよね．
  • 問題見ただけですぐに回避してしまったので，次回は頑張りたい．

H. ダーツゲーム

Topcoder WF2012 easy の類題

  • Time Limit: 2 sec.
  • Memory Limit: 65516 KB

概略

  • 次の条件でダーツを投げた結果，勝率の高いプレイヤーを求めよ．
    • 点数の書いた的が左右1列に並ぶ．
    • 最終的に，点数が高いプレイヤーが勝つ．
    • プレイヤーは，狙った的の左右含む3つのいずれかに当たる．
      • それぞれの的が当たる確率は1/3であり，すべて同様に等しい．
      • プレイヤーは左右に的がない的を狙えない．
    • 自分の点数が勝っている，もしくは同点ならば，期待値の高い場所を狙う．
      • 候補が複数ある場合は，最小値の大きい場所を狙う．
      • それでも候補が複数ならば，2番目に小さい値の大きい場所を狙う．
    • 自分の点数が負けている場合，勝率が一番高くなる場所を狙う．
    • 先手，後手ともに1回投げたら終了である．

入力

N
A0 A1 ... Ai ... An-i
  • N: 的の数
  • Ai: i番目の的の点数
  • 入力は以下を満たす
    • {3\leq N\leq 10}
    • {1\leq A_i\leq 100}

出力

  • 勝率が高いプレイヤーが，先手ならば"M",後手ならば"R"，どちらでもなければ"Draw"と出力せよ．ただし，出力末尾には改行をいれよ．

解説（というよりメモ）

  • ダーツを投げる
    • 投げた場所が確率的で不明
    • 狙う場所を問題文通りに組む
  • 直積集合 AxB = {(a,b)|a∈A,b∈B}, |AxB| = |A|x|B|
    • A := 先手のクエリ
    • B := 後手のクエリ
    • |AxB| = 9事象
  • 全事象に対してシュミレーションを行う
    • A* = 1-B* (X*はXの勝率) は成り立たない
    • 各チームの試行後の点差をとっておくと楽にできる

自分の解答

  • 解けなかった

感想

  • 問題を理解するのに苦戦してしまった．
    • 冷静に考えると，さほど複雑でもない．
  • 時間がなくてちゃんと取り組めなかったので，そのうちちゃんと解きたい．

全体の感想

  • とにかく頭をつかう．大変に疲れるが，成功した時の喜びもひとしお．
  • 開発環境を整えておくべき．
  • 今回は計算量を考えたり，アルゴリズムを活用するような問題はなかったが，むしろそれらが競技プログラミングの本質だと思うので，この程度でくたばっていてはまだまだなんだなって感じた．
  • 競技プログラミングってコード組めない人こそやるべき．C++わからなかったけど，勉強になった．
  • むしろ理論考える方に時間割かれるから，プログラミングできなくても楽しめるのではないだろうか．
  • ぜひとも自分の界隈でも普及させていきたい．
  • あと，競技プログラミングのジャッジサーバ建ててみたい．