ACM-ICPC参加記(?)

民です.久しぶりの更新です.

(だいぶ前ですが)1年生へのC言語ゼミも無事に終わり,教えたことを定着させるためにオンラインジャッジをしばらくやらせています.目標としては来年の新入部員に教えられるくらいのレベルまではいってほしいなと思ってます.
プロコンの予選結果発表もあり,慌ただしくなってくる時期ですが,9月にはパソコン甲子園の予選もあるので高専プロコンと両立して競技プログラミングを頑張っていきたいですね.頑張りたいけどきつそう悲しい…

さて本題ですが,昨日,ACM-ICPC国内予選がありました.当部活からは4年生3人の1チームが参加しました.
国内予選公式サイトはこちら
http://icpc.iisf.or.jp/2017-tsukuba/domestic/

僕は2年生なのでまだ参加できないのですが,問題は公開されていたので解いてみました.参加できないので提出が出来ず,正確な結果はわからないのですがおそらくA,B,Cの3完でした.B問題が例年に比べて若干難化してたように感じましたが果たしてどうなんでしょうか…?D問題はbitDPな気がしてたけどbitDPをまず書いたことがなく,さらに具体的な解法が全然分からなかったです.悲しい.DPに対して強くならないと競技プログラミングコンテストにおいて上位を狙うのはやはり相当厳しいですね…

解けた問題に関しての簡単に方針を載せておきます.
 

A問題
1問目なので難易度はまあはいという感じでした.
N個の数字の中から2つを選ぶ組み合わせの最大の和を求める問題.
2重for文で全列挙するだけ


B問題
概要を説明しようとすると僕の日本語力じゃ説明が足りないので省略.
いつもより難化しているようには感じましたが,難化というより実装が面倒になった問題のように感じました.
二重引用符で囲まれている文字列とそれ以外の文字列を取り出していって,それぞれ比較.STLで殴りました.


C問題
1つ1つに高さが設定されてる3*3以上の長方形において内部のセルが外周より低い長方形から外周の高さとの差の最大値を求める問題.
制約が3≦d,w≦10と小さめなので4重for文での全探索.中の処理も含めても多くてO(N6)ぐらいなので十分間に合う.


これでちゃんとACできるかは分からないけど変なコーナーケースを作れるような問題でもなさそうなので多分あってるはず(?).
4年になることには国内予選を突破できるぐらいまでには精進したいなと.尚,チーム戦なので競技勢をもっと部内に増やさないといけないですね.

高専プロコンまでも時間があるわけじゃないのでコツコツと頑張っていきましょう!