0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

ICPC 2018国内予選に参加してきました

M1の@reminさん、B4の自分、B3の@9071tomatoくんの3人で、チームMohuhu UniversityとしてICPC 2018国内予選に参加しました。 なんとかA〜D問題を解いて全体で31位になることができたので、おそらく国内予選を突破できたはずです。

f:id:mizu0x19f:20180707193343p:plain

一応、問題一覧と順位表のリンクを貼っておきます。
問題一覧: All Problems
順位表: LiveSite

A問題:
n個の値が与えられるので、その平均以下の値の数を答える問題。 @reminが考察・実装。 最近の国内予選のA問題だと解きやすい方に入るのかなぁと。

B問題:
紙を横方向または縦方向に折る指示がいくつか与えられて、折った後に特定の場所に何枚紙が重なっているか答える問題。 自分が考察・実装。 パッと見ですごく解きたくない問題だったんですが、実際に解いてみるとものすごく解きたくない気持ちになりました。 少し手間取ったもののなんとか通せてよかったです。

C問題:
連続する正の整数の和がbになるような範囲のうち、範囲に含まれる数の個数が最大のものを答える問題。 @9071tomatoが最初読んでわからないようだったので一旦飛ばしてDを読んでもらいました。 自分もBを解き終えて問題を読んだのですが、なるほど確かにわからない。 昨年のC問題とかもっとずっと簡単だったのに......なんて思いつつ考察してました。 bが109程度であること、範囲の和が2乗で大きくなっていくことを考えると、何かしらがsqrt(109)に収まるんだろうなぁと話していたら、@reminが範囲の幅がsqrt(109)で抑えられることを見つけてくれました。 というわけで、Cは@reminに実装してもらいました。

D問題:
総当たり戦の対戦結果が途中まで埋められた表が与えられて、全チームの勝敗数が等しくなるような対戦結果は何通りあるかを答える問題。 チーム数が最大で9なので試合の数が9C2で36通り、全探索をしても236なので時間をかければ解けそうだし、適当に枝刈りすれば十分な速さで解けそうだなぁと思いました。 実際のところ最大ケースでも236通り試す必要はなくて、たぶん8C4 * 6C3 * 4C2 * 2C1 = 16800ぐらいになるのかな？ @9071tomatoがいけそうだと言ってくれたので実装してもらいました。 @9701tomatoくんにnext_combination(next_permutationの組み合わせ版)を持ってないかと聞かれたのですが、奇跡的に持っていたので写経してもらいました。 何がいつどこで役に立つかわからないものですね。

E問題:
簡易版の浮動小数点を用いて加算をn回繰り返すプログラムの結果をシミュレーションしてくださいという問題。 nが最大で1018なのでダブリングだと思ったんですが、違いました。 実装してからダブリングだとn回加算で起きる誤差が再現できないことに気づきました。 実装する前に@reminから指摘があったとの説もありますが......。 実はサンプルの最後のケースが最大ケースになっているらしく、指数部が増えるタイミングがたかだか50回程度であることがわかるみたいです。 あとは指数が増えるところまでまとめて足すというのを50回ぐらい繰り返せばいいみたいです。 (まだ実装できてないですが......)

F〜Hは一応問題には目を通したもののどうしたらいいのかさっぱりだったので諦めました。

ちなみに、学内1位のWAsedACが選抜チーム内で14位、Mohuhu Universityが学内2位で選抜チーム内で20位、学内3位のWAsita Universityが選抜チーム内で25位なので、学内から3チームアジア地区大会に出場も夢じゃなくなってきてますね。 (学内から3チーム出場するには20位以内に入る必要があるので。)

とまぁ、なんとかアジア地区大会に出場できそうです。 国内予選を通過されたチームのみなさん、横浜でお会いできるのを楽しみにしています。

ちなみに、これは予選終了後に学内の参加者で集まって寿司を食べている様子です。 寿司が食べたいみなさん、来年はぜひICPCに参加しましょう。

(ところでなぜ僕らはコンテストが始まる前にフビライ・ハンとエビフライゴハンの話をしていたんですかね？)