SRM 726 Div.2 雑感

Easy

題意：n種類のアルファベットを2文字ずつ使用した文字列が与えられる。この文字列から、n種類のアルファベット2文字ずつのうち1文字ずつを消去してできる文字列のうち、辞書順で最も早いものの頭文字を求めよ

あるアルファベットが2回出てきたら、そのアルファベットの2回目の出現位置よりも後ろのアルファベットが先頭に来ることは絶対にありません。（どちらのアルファベットを消しても、もう片方のアルファベットがより前に来るため）

解法は、まず与えられた文字列の先頭から順に各アルファベットの出現回数を記録していき、どれかのアルファベットが2回出現したところで記録を止め、それまで見てきたアルファベットのうち一番アルファベット順で若いものを出力します。

Middle

これは制限時間内に解くべきでした。

題意：ある盤面が与えられ、' . ' は通行可能なタイルを、' # 'は通行できないタイルを表している。2人のプレーヤーが通行可能なタイルを交互に取り除いていって、左上から右下までの最短経路が無くなるようにタイルを取り除いた方が負けとなる。双方が最善手を取った時に先攻は勝つか負けるか

双方のプレーヤーにとっての最適手は、『最短経路を確保しながらタイルを取り除く』です。与えられた盤面には最短経路が存在することが保証されているので、このゲームの勝敗は、最短経路のみが残っていてその最短経路上のタイルを取り除かなければならなくなった時点で決定します。

ゆえに、（与えられた文字列中の ' . ' の数　－　盤面の左上から右下までの最短経路長）を2で割った余りが1ならば先攻の勝ち、0ならば後攻の勝ちとなります。

P.S. 3問サブミットしてすべて撃墜され、自分も4回チャレンジして1勝3敗だったコンテスタントのHNがdreamer_0だったのがいろいろ示唆に富んでいるなぁと思いました。