CODE FESTIVAL 2017 Team Relay
作成日：2017.12.07
カテゴリー：競プロ 参戦記録
はじめに
これはCompetitive Programming Advent Calendar 2017の7日目の記事である(ことにした)。
目次
チームリレーについて
(2017年では)1チーム10人で戦い、10問ある問題を各人1問ずつコーディングする競技である。
コーディング中以外ではチーム内での相談が可能なので、解法の確認をコーディング前にしたり、バグを発見してもらったりできる。
その過程で、他の人のサンプルも通っていないような未完成のコードを見たり、自分より強い人がどれだけすごいかを目の前で見れたりという普段なかなかできない体験ができる。
だから、最も面白い競技形式だと個人的には思っている。
競技中の様子
私はTeam Bであり、結果は全完4位であった。
Team Bは競技が始まる前に最初に見る問題を各人に割り振っておいた。
私はF問題の担当になったので開始直後にその問題文を読んだところ、すぐに解法を思いつくことができた。
ほどなくG問題担当のpachicoさんに話しかけられ互いの問題を説明し合い、こちらの解法を説明した(途中で面倒になって言葉にするのを放棄したのは申し訳なかった)。
しかしG問題の解法に対しこうなんじゃないかとか言って、嘘解法を吹き込んでしまった(ごめんなさい)。
その後はぼんやりしてても面白くないと思ったので、デバッグや考察をしていそうなところに積極的に突っ込んでいった。
色んなところに突っ込んでいったので細かくはあまり覚えていない。
ただD問題のデバッグに成功したので、G問題の失敗を帳消しにできたかと思う。
他に特筆すべきことは、競技中に実況が入ったり、全完を達成したチームのインタビューがあったりしたことである。
これによって、普段とは違うお祭りっぽさを感じることができた。
各問題に対するコメント
- A : Kaidan
- B : Evergrowing Tree
- C : Garden
- D : Shock
- E : White and Blue
- F : Capture
- G : Coinage
- H : Akashic Records
- I : Nice to Meet You
- J : Indifferent
A : Kaidan
問題文
競技でデバッグに手間取った問題。
デバッグに成功したところにいなかったので、何が間違っていたかは分からない。
ただ、除算が絡むと被除数に足しておく数が1ずれたりやすいので案外難しいのかもしれない。
B : Evergrowing Tree
問題文
競技では一発ACしていたので関われなかった問題。
親の頂点番号が簡単に求められることと$N=1$の時がコーナーケースであることに気付けば良い。
WAをもらってもチーム戦だと誰かが気付くだろうから、コーナーケースのある問題はリレーに向いているのかもしれない。
C : Garden
問題文
競技中に詰まっていた印象はあったが、関われなかった問題。
後日自分で解いた時に1WAを出してしまったが、これはオーバフローが起こったためである。
乗算がなくても、大きい数を何度も足し合わせる操作は注意が必要である。
D : Shock
問題文
競技中に私がデバッグに成功した問題。
原因は頂点が1-indexedで与えられるのに、0-indexedで処理していたことである。
個人的にはUnion-Findライブラリを貼るだけの問題であった。
E : White and Blue
問題文
競技では一発ACしていたので関われなかった問題。
一目では解けないが、不等式を変形していくと貪欲が見えてくる。
比較的明らかな性質に関する等式や不等式を変形していくと解ける問題はたまに見る気がする。
このような問題は具体例からひらめくのは難しいので、考察の糸口の一つとして頭に入れておきたい。
F : Capture
問題文
競技で自分が担当した問題。
Segment Treeを使いそうな見た目だが、実は使わなくて良いというのが面白い(使いそうと思う時点で弱い?)。
区間の端の片方を固定して考えるとすぐに解法にたどり着ける。
他の問題でも自由度を下げて考察するのは強力である。
G : Coinage
問題文
競技中に嘘を吹き込んだ問題(改めてごめんなさい)。
辞書順最小は貪欲にということで先走ってしまった。
文字列$S$と$T$を並べる時に$ST$と$TS$の辞書順を比較するのは定番という話を競技中に聞き勉強になった。
H : Akashic Records
問題文
私自身も考えていたが海外勢はすぐに方針を立てたので、やはり強いと思った問題。
制約の最大値の平方根より大きいか否かで扱いを変えることで状態数を減らすテクを私は忘れがちなので改めて頭に入れておきたい。
I : Nice to Meet You
問題文
競技中はあまりちゃんと考察できなかった問題。
制約を見てbitDPをしそうだということは分かるが、具体的にどうすればよいのかは難しい。
そのままでは考えにくい時は余事象を考えるというのがこの問題のカギである。
この問題を解く上で集合から2つの部分集合でそれらの共通部分が空であるようなものを取ってくる必要がある。
これを愚直にやると$O(4^N)$であるが、工夫すれば$O(3^N)$になる。
この事実はよく解説等で出てくるが、同時に具体的で簡潔な方法が提示されることはほとんどないような気がするので以下に提示する。
for(int i = mask ; i >= 0 ; --i){ //maskは1つ目の部分集合の補集合
i &= mask;
//何らかの処理
}
(参考:『ビットによる部分集合の列挙』,リンク先にあるTopcoderへのリンクは恐らく間違っているので注意)
J : Indifferentn
問題文
競技中にKsun48さんがすぐに解いていた問題。
レッドコーダーは強いと改めて実感した。
$N$が小さい場合を考えると答えの予想ができる。
このような問題があるので、どんな問題でも具体例からエスパーしようとしがちである。
しかしこれは具体例を試すのは問題の理解が正しいかを確かめる時か、他に考察の糸口がない時にすべきことだと思う。
また具体例から解法にたどり着かないと少しでも思ったならば、すぐさまやめるべきである。
(最後の2文は、自分の失敗例から導き出された自論にすぎない。異論は歓迎である。)
＜(古い記事) CODE FESTIVAL 2017 qual C
関連
(新しい記事)＞