2016-10-20

ACM-ICPC2016 アジア地区つくば大会参加記

雑記競技プログラミング

チーム t9qmib (九州大学) でACM-ICPC アジア地区予選つくば大会に参加していました．結果は6完19位．これはその参加記です．

メンバーは私，nola_suz，nikollsonの3名にコーチのgrrifon_zero．同じメンバーで参加するのは昨年以来2度目です．チーム名は我らが偉大なる先輩climpetさんからとりました．

前夜

研究室から帰りアイロンがけやら荷造りやらを始める．荷造り終わった時点で既に日付が変わっていたため絶望する．なぜ8:00発の飛行機を取ってしまったんだ．9:00発でも問題無く間に合っただろと愚痴る．

1日目

なんとか飛行機に間に合う時間に起床．睡眠時間は驚きの3時間．空港行ったら福岡空港第一ターミナル閉鎖の影響でレイアウト変わってるし，保安検査場が異様に混んでるし，もしかして飛行機に乗れないんじゃないかと思った．

なんとか飛行機に乗り，羽田に着くなりメールの着信に気づく．コーチからの「飛行機が欠航した」メールである．そして，チームメイトからも「飛行機が欠航した」のDMが．．．

I hate Jetstar.

飛行機はANAかJALを取るべきである．
この時点でチーム4名中2名の遅刻が確定する．

焦ってもしょうがないので空港で軽食を食べたあとつくばへ向かう．空港から出ていたバスに乗っても良かったのだけどICPC運営の推奨ルートでつくばへ．秋葉原まで出てつくばTXのほうが安い．つくば駅近辺で昼食にする．昼食中にコーチからDMが届く．

コーチ「ねえ，もう一人のチームメイトも遅刻するって知ってる？」
私　　「？？？？？？？」
コーチ「いやぁ，僕も今さっき聞いたんだけどどうやら本部のほうには連絡してるらしんだよね．本部から彼も遅刻するって聞いた．」

＼(^o^)／ｵﾜﾀ

無事1日目チームメンバー1人での参加が確定する．

受付を済ませようとするが，4人揃ってregisterらしい．もちろん弊チームは1人しかいない．受付のアミラーゼ伯爵に「2人は遅刻すると聞いていたけどもう1人は？」みたいな感じのことを聞かれる．

伯爵「あー，九大チームね．二人遅刻ってのは聞いてるけどもう一人は？」
私　「彼も遅刻らしいです」
伯爵「まじかー．．．遅刻する理由とか聞いてない？」
私　「聞いてないです．．．」
伯爵「連絡つく？」
私　「つかいないです」
伯爵「あー．．．．．．ジャッジ団の判断を仰ぎます．多分大丈夫だとは思うけども．」

みたいなやりとりの後，ジャッジからregisterして良いとの判断が出てどうにか失格は回避．ほんとご迷惑おかけしました．

で，「一人しかいないので，注意事項のアナウンスだとかルールについて把握してしっかりメンバーに伝えてくださいね」と言われる．英語ﾆｶﾞﾃ勢には辛いが，registerさせてもらえたのでがんばった．

register後，会場までの案内の時
staff A 「九州大学チーム．．．メンバーは1名？？？」
staff B 「ああ，九大チームね．はいはい．」
staff A 「えっ，よくあることなんですか？？？」

というやりとりがある．さすがに，registerにメンバー1人しか間に合わなかったというのは前代未聞なんじゃないのかな．

九大チームt9qmibの周囲には EfficientCoefficient (東大), Do Touch Everything (阪大), nocow (農工大)と有力チームが配置されていることに気づいてびくびく．JAG合宿でお話ししたヘクトさんやら，yazatenさんやらに声かけるなどする．

その後，トイレに行く時は手を上げてスタッフに声をかけて行くことだとか，割と重要な注意事項を聞いたりする．ちょくだいさんが両手を挙げて「トイレトイレー」と叫びながらトイレに行く理由が分かった．

プラクティスではとりあえず問題としてみたり，わざとWAになる提出をしてジャッジシステムがどういう表示になるのかを確認したりする．practice B問題を使ってジャッジサーバの強さを確認してみたが，浮動小数点の計算で1secで1e8はokで2e8ではだめだということがわかった．どうやら，CFやTCのサーバーほど強くはなさそうだ．また，競技環境にログインする時，ID/パスワードを入力してから実際に操作可能になるまで思いの外時間がかかることもわかった．

プラクティス終了後，他チームはスタックの広さを確認するなどしていたことをtwitterで知る．やっとけばよかったな．

つくば大に移動しての懇親会ではメンバーが2人に増えた．
チーム紹介は割とうまくいったと思う．いらすと屋の猪がのっそのっそ歩くアニメーションは結構笑いを取れたようだ．

懇親会終了後，ホテルにてコーチと合流．これで3/4揃った．
とりあえずTシャツや名札や資料を渡して一般的な注意事項を伝えるなどする．

23:00前に最後のチームメンバーが合流ようやくメンバー全員集合．よかった．

Tシャツや名刺を渡して注意事項の説明，そしてプラクティスで分かったことなど伝える．

布団に入ったのは日付変わってからだった

2日目

4:00ごろに目が覚める．二度寝を決意．
5:00ごろに目が覚める．三度寝を決意．
5:50ごろに目が覚める．もう寝るのはあきらめた．

朝食を摂った後，どうせこなるだろうと思ってあらかじめ準備しておいたユンケル黄帝プレミアムを飲む．備えあれば患いなしとはこのことである．

入場

入場前に持ち物検査がある．筆箱に入れておいたUSBメモリを出し忘れている人が多数居た．これは罠だ．筆箱から必要なものだけを取り出して残りはコーチに預けた．

コンテスト

開始と同時にA問題を読む．やるだけだったので8分でAC．
B,Cは任せてD問題を読む．

Dはにぶたんと嘘解法を立て，Bと並行して実装する．BがACした頃に，Dのにぶたんは嘘解法と気づき，Cを実装してもらう．

CがACしたあと，Dをハッシュで書き直す．D問題までAC．

ここまで2時間．ペース的にはだいぶ遅い．

E問題を読んだnikollsonが「あっ，これやろう」と言い始める．僕とnola_suzは「これ，強実装やるだけだし手を出してはいけないやつだ」と判断していたので止めたがnikollsonが「ｲｹﾙｲｹﾙ」と言ったのでそのまま実装してもらった．結果的にこれが fine play で実装開始から2時間ほどでデバッグまで完了していた．nikollson強い．

で，E問題の実装中にAC数の多いG問題をnola_suzと考察．貪欲にシミュレーションすれば解けそうという話になり，コインを置ける位置を区間で持つ感じのシミュレーションをする解法を立てる．オーダー的に難しいよねみたいな話をしていたがクエリ先読みでオーダー落ちるという結論が出た．nola_suz が実装するものだとばかり思っていたが，「じゃ，実装してください」と言われたので実装する．残り30分で6完．

その後はどうせ残り時間で実装まで終わらせるのは無理そうと言いつつ，どうにかなる問題がないか問題を漁っていた．

6完のままコンテスト終了，最終順位は19位でした．

感想

「6完できたし，PC使ってなかった時間は解ける問題がなくなった最後の30分だけだし，チーム戦略としては上手くいってたよね．」という話になった．解ける問題は全部解いたしあとの問題解けないのは実力不足としか言えないので，本当に上手く行ったと思う．

講評・表彰

会場の壁に魔方陣が描かれていたり（本当によく気づいたな），Cxiv-Dxivと上海交通大チームの争いが熱かったり，上海交通大のインタビューがめちゃくちゃかこよかったりした．講評の最中に地震が起きたがそのままスピーチが続けられた．

懇親会

各社の企業ブースで問題を貰って問題を考えてたりした．google問題のネタバレを聞いたが凝っていて面白かった．

まとめ

酷いトラブルがあったが，大会では今持ってる実力を出し切ったと納得できるだけの仕事はできた．これでICPCは引退になってしまうので寂しい．

2016-08-17

Google Code Jam 2016 のTシャツが届いた

Google Code Jam 2016 に参加してました。で、Distributed Code Jamで500位以内に入れたのでTシャツを獲得できました。GCJへのチャレンジは今年で4回目だったのですが、遂に憧れだったTシャツが獲れたのかと思うととても嬉しいです。

来年はDistributedでないCode JamのほうでTシャツを取りたいですね。

f:id:konjo_p:20160817194316j:plain
f:id:konjo_p:20160817194323j:plain

2016-07-18

ctf4b2016博多参加記

ctf4b博多に参加してきましたので参加記を

私のctf経験について

今年4月にgoogle CTFに参加しました．google CTFに参加して0完の洗礼を浴びたCTF初心者です．

web講義

web問題についての講義でした．内容はXSSについて．この講義でgoogle CTFの一番簡単な問題がカバーできたのかなぁ．．．

web問題を解くためのツール類の紹介もあり，google CTFのときに「え？？サーバに盗んだcookie送りつけるの？？管理してるサーバとかないし無理じゃね？？？」と思った私にとっては嬉しい講義だった．

フォレンジックス講義

パッケットキャプチャしたファイルが与えられるから，そこからフラグを探し出してくださいという趣旨の問題群を解くための講義だった．

ツールの機能を活用していかに効率的にパケットを読んでいくか，また，集中して読むべきパケットがどれかという点に焦点を当てての講義だった．前後のパケットの内容から，いつフラグが通信されたかを推測する話や，使用されたプロトコルの統計情報から集中して読むべきパケットを絞り込むと良いらしい．

講義を受けて，プロトコルとその代表的な利用目的について勉強しておくと，通信内容について推測できるから良いのかなと思った．

バイナリ講義

逆アセンブルされたバイナリを読む講義だった．mipsなら3ヶ月ぐらい読んでいたことがあったが，x86は未知の世界．x86はディスティネーションレジスタが決め打ちされてる命令があったりとか，分岐の方法とか覚えるのがmipsと比べて辛い印象を持っている．

幸いにも今回の講義で読んだバイナリたちは素直なバイナリだったので，何がなんだかわからんということはなかった．

パタヘネ読んでたりとか，低級な部分を大学で研究してたりというバックグラウンドがあったせいだろうが，今回の講義の中では一番簡単な講義に感じた．

実際にプログラムを逆アセンブルして読もうとすると，どの処理を集中して読んだら良いかわからん．ということが起こりがちなので，読むべき部分の絞り込みとかの話がもう少し欲しかったかなぁ．．．

あとIDAすごい．ループの構造をグラフィカルに表示してくれる．あれいい．

練習コンテスト

f:id:konjo_p:20160718123928p:plain

コンテストについて

6位でした．やったね！講義でやったことをきっちりやれば解ける問題が出ていたので，練習コンテストとして良い問題セットだったと思う．

MISCと分類されていた問題

基本的にやるだけっぽかった．CountUpGameの必勝法は競技プログラミングのスキルがCTFに活きたなーと．

Webの問題

web100点は憶えてない．web200はダブルクォテーションと山括弧使っていけそうだったけど，うまくいかなかった．あれなんでだろうな．

フォレンジックス

strings hoge.pcap | grep flag

すると良い感じにヒントが取れる．ので，あとはflag.txtだとかflag.pngだとかそれっぽいワードから何が行われているか推測したら200点問題が解けた．

バイナリの問題

100点しか解いてない．grepしたら取れた．

感想

CTF面白かったし，ctf4bも初心者（プロ）向けの話でなくきちんと初心者向けのイベントだったので良かった．ハラスメントが横行していない or 本当の初心者にはハラスメントしない界隈は良い界隈です．ICPC引退まではCTFにがっつり時間をというわけにもいかないので，10月のICPC引退後には競技プログラミングに割いていた時間を少しばかりCTFに割いてみようかなあ．

最後にctf4bの講師，参加者の皆様ありがとうございました．

2016-06-26

ICPC2016国内予選参加記

はじめに

チーム t9qmib としてnikollson, nola_suzと一緒にICPC国内予選に参加しました。結果は4完24位で、正式なアナウンスはまだですがアジア地区筑波大会への参加権を獲得できているはずです。

A問題

A問題の担当でした。2つ目の出力ファイルの作成時間を見ると6分でACしたようです。問題文の印刷が終わらないうちにACしてかなり良い調子。

B問題

nikollsonの担当。30分経過時点で通っていなくて嫌な予感がする。nikollsonの実力でこの時間にAC取れてないのはおかしい。途中でコーダーを交代して51分ごろにAC。図らずもB問題の担当になる。

C問題

素数定理を知っていたので、エラトステネスの篩みたいに書けば計算時間的には問題なく終わることに気づく。最大ケースが与えられていたことにはサンプルを通す段階で気づいた。B問題で詰まっていたので代わってもらい37分でAC。私がコーダーでした。

D問題

問題の概要を説明された時に「これ、TDPCで見た問題だ！」となる。TDPCのiwiの解法の方針は覚えていたものの、細かいところが記憶になかった。もやっとした方針を nola_suz 説明すると「区間DPってこと？」と言われ、そのまま nola_suz が漸化式を立ててコーディングすると64分でACした。強い。自分がiwiを書いたときバグに苦しんだ記憶があったから、バグが出て1時間ぐらいかかることを覚悟していた。

E問題

共有部分の表面積を辺の重みとしたグラフを作って、辺の重みの合計が最大になるような、連結な部分グラフを求める問題。ああでもないこうでもないと言いながら解法が立たずに苦しんでいた。コンテスト終了後にblue_jamさんがやってきて「いやぁ、E問題のEはEASYのEでしたね。」といわれる。一つの立方体は最大でも二つの立方体としか共有部分を持たないという制約を読み落としていたことに気づく。チームメンバーのうち2/3が制約を読み落としていた。

F問題

実装が重いやるだけ問題というnikollsonの直感。根付き木の同型判定を効率的にやる方法を知らなかったが、nola_suzが「ノードを訪れるときに '(' を、ノードから親に戻る時に ')' を文字列に追加するようにして、子から上がってきた文字列を辞書順にソートして親に上げれば良い感じに同型判定できるんじゃない？」と言って効率的に根付き木の同型判定ができることが分かる。完全にプロ。効率的な根付き木の同型判定のアイデアが出た時点で、E問題の解法が立たずに1時間何もしていない状態だったので、何もしないよりは書いていたほうがいいだろうという判断で実装に入る。この時点で残り1時間。途中、H問題の解法が分かったという声が上がったが、その時点で残り30分少々。チームメイトに残り20分時点までに一通りの実装が完了するが、残り20分でデバッグが完了する見込みは薄いことを伝えるが、F問題を解き続けたほうがいいという判断になった。結局間に合わず。1時間PCを占領したのに申し訳ない結果になってしまった。

ちなみに説明された解法はこんなの
f:id:konjo_p:20160626212702p:plain

G問題

よんでない

H問題

やるだけじゃないかという意見が出たが、この時点でコンテスト終了まで残り30分ということで、F問題を書き続けるほうがいいだろうという判断でコーディングせず。

感想

どう見ても5完セット。あわよくば6完狙う感じでやらなきゃだめだった。
A問題の実装、図らずもB問題の実装、C問題の実装、間に合わなかったF問題の実装を担当していました。チーム中レーティング最弱なのになぜこうなった。

2016-06-01

Distributed Code Jam 2016 について

はじめに

Distributed Code Jam R1に参加して、環境構築とか環境構築とか辛かった人を散見したので記事を書くことにした。

Distributed Code Jam とは

Distributed Code Jam (DCJ) とは、Google Code Jam (GCJ) に併設された分散処理のコンテストです。ざっくり言うと、100並列で競技プログラミングをやるコンテスト。2016年はGCJのRound2進出者に参加権がありました。

環境について

普段の競技プログラミングとは異なるところもあるので、思いついたところのまとめ。Mac/C++で参加しました。

並列化用ライブラリ

MPIっぽい関数を実装したライブラリがコンテストの運営から配られます。コンテスタントはそれを使ってプログラムを実装します。基本型の送受信用キューへの追加/読み出しと、送受信用キューの内容の送受信程度でしょうか。ライブラリの詳しい仕様を把握しないまま書いたら書けてしまったので詳しい仕様は言えない。

言語

C++かJavaの二択。

入出力仕様

入力は関数を呼んで取得する。問題ごとに入力用の関数が用意されていて、入力用関数の仕様は問題文中で与えられる。problem_ name.h というヘッダファイルに実装されているので、それをインクルードする必要がある。ヘッダファイルはソースと同じディレクトリの中に置いてね。sample-inputをくれるヘッダファイルは問題文の下のほうにあるリンクからダウンロードできました。答えの出力はどこか一つのノードが標準出力に吐けばよい。

環境構築

Distributed Guideに書かれてある。

Linux || Mac

LinuxかMacがメイン環境の人は環境構築がしやすいから幸せだ。DCJ 用のテスト用ツールを Distributed Guide に書かれてあるリンクから落としてくる。.tar.bz になってるので、コマンドラインで

tar jxvf dcj.tar.bz

とかやって展開する。あとはGoをインストールして、

cd src/parunner/
go build
cp parunner ../../executable/

とやると環境構築おわり。

config.jsonにどのコンパイラを使うかとかを指定するようになってるので、「コンパイラみつかんねーよ」と怒られたりしたらconfig.jsonを書き換えるといいかもしれない。sample-configsの中にいくつか設定例があったので、自分で書き換える必要が出てくることはないかも。テストを行うには、Distributed Guide に書かれてあるコマンドを打てばよい。

problem=prblem_name
srcfile=${problem}.cpp
${DCJ_UNPACK_DIR}/dcj.sh build --source=$srcfile

problem=prblem_name
runnable=${problem}
${DCJ_UNPACK_DIR}/dcj.sh run --executable=./${runnable} --nodes=100 --output=all

とか書いてスクリプトにまとめとくと便利。

Windows

Cygwinで環境構築しようとしたら失敗した。辛い。READMEとか読んだら「MinGWでやれｗ」って書かれてたから、MinGWでやったら上手く行くんじゃないかな。

提出

提出はGCJとは異なりソースコードのみを提出する。例によってsmallとlargeのデータセットがある。smallを提出すると、コンテストサイト側でテストが行われ2分後に結果が分かる。提出後の2分間は結果も分からないし、再提出することもできない。largeはsmallが通った場合に提出でき、コンテスト終了まで何度でも再提出できる。largeの採点はコンテスト終了後に行われる。

practiceについて

DCJは本番前にGCJR2進出者を対象にしてDCJ前にオンラインで練習会が開かれる。今年の場合、練習会の日時・URLはメールで告知され、コンテストスケジュールには載ってなかった。事前練習を行いたいひとはこまめなメールの確認を。

問題難易度

極端に難しい問題は出なかった印象。R2進出者であれば、シングルノード版の解法を書くことにはまず困らない。samllはシングルノードでも解ける程度の制約、largeは並列化しないと無理ゲーな制約。という印象をうけた。Distributedと名がつくだけあり、シングルノードでも解ける制約のsmallの配点がものすごく低い。

2016-03-13

SRM501 div2 hard 1000pts : FoxAverageSequence 解説

競技プログラミングプログラミング

はじめに

SRM501 div2 1000pts を解いたら計算量の落とし方がいい感じだった && 多くの人が自分よりひとつ悪いオーダーで通してて悔しかったので解説記事を書いてみる

問題概要

美しい整数列Aは以下の制約を満たす。

要素数40以下
$0 \leq a_{i} \leq 40$
$a_{i} \leq \sum_{k=0}^{k=i-1}a_{i} / i$
$a_{i} \gt a_{i+1} \gt a_{i+2}$ となるiは存在しない

整数列seqが与えられる。seqの各項は-1以上40以下である。seqの-1の項を0以上40以下の任意の数に変えることが出来るとき、seqから得られる美しい整数列の総数を求めよ。

解法

dp(i,j,k,l)を、i個目までの和がj、i個目の要素がkで、i個目の要素がi-1個目の要素から{ l=0 : 減少していない, l=1 : 減少している}として、

$dp(i+1, j, k, 0) = \sum_{0 \leq k' \leq k}( dp(i,j-k,k',0) + dp(i,j-k,k',1) )$
$dp(i+1, j, k, 1) = \sum_{k \lt k' \leq 40} dp(i,j-k,k',0)$

に従って更新すればとりあえず答えは求まる。
但し、dp(i,j,k,l)はseqのi個目の要素が-1で無くseqのi個目の要素がkでない場合0である。また、k * i ≤ j - kを満たさない場合もdp(i,j,k,l)=0とする。

これを愚直に計算しようとすると、時間計算量はseqの要素数nとseqの各要素が取りうる値の最大値mを用いて $O(n^{2}m^{3})$ となり微妙に怪しい*1。

ということで、よく使う例の方法で計算量を落としにかかかる。
$dp(i+1, j, k, 0) \\ = \sum_{0 \leq k' \leq k} ( dp(i, j-k, k', 0) + dp(i, j-k, k', 1) )$
$= dp(i, j-k, k, 0) + dp(i, j-k, k, 1) \\ + \sum_{0 \leq k' \leq k-1} ( dp(i, j-k, k', 0) + dp(i, j-k, k', 1) )$
$= dp(i, j-k, k, 0) + dp(i, j-k, k, 1) + dp(i+1, j-1, k-1, 0)$

同じ要領で、2番目の式
$dp(i+1, j, k, 1) = \sum_{k \lt k' \leq 40} dp(i,j-k,k',0)$
を変形すると
$dp(i+1,j,k,1) = dp(i,j-k,k+1,0) + dp(i+1, j+1, k+1, 1)$
となる。

これでdp表の更新にかかるオーダーが減り、全体のオーダーは無事 $O(n^{2}m^{2})$ に落ちたのだが、seqのi個目の要素が-1で無い場合のdp表の更新を上の漸化式に従って行うと間違う。なぜならば、 $dp(i+1, j, k, 0)$ を計算する場合を例にとれば、 $\sum_{0 \leq k' \leq k-1} ( dp(i, j-k, k', 0) + dp(i, j-k, k', 1) )$ のつもりで書いている $dp(i+1, j-1, k-1, 0)$ が、k-1とseqのi+1番目の要素が異なる場合、 $dp(i+1, j-1, k-1, 0) = 0$ になるためである。

seqのi番目の要素が-1で無い場合、dp(i,j,k,l)はseqのi番目の要素とkが一致した場合には

$dp(i+1, j, k, 0) = \sum_{0 \leq k' \leq k}( dp(i,j-k,k',0) + dp(i,j-k,k',1) )$
$dp(i+1, j, k, 1) = \sum_{k \lt k' \leq 40} dp(i,j-k,k',0)$

を使って更新し、そうでない場合は0にすればよい。各(i,j,l)の組に対して $O(1)$ の更新が $O(m)$ 回と、 $O(m)$ の更新が $O(1)$ 回しか呼ばれないのだから、DP全体の計算量は $O(n^{2}m^{2})$ に収まる。

実装

バグの箇所がなかなか見つからずにつらかった。書き直す気はない。ぺたり。

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <utility>
#include <cassert>
using namespace std;

#define all(x) ((x).begin()),((x).end())
#define pb push_back
#define mkp make_pair
#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;

const int mod = 1e9+7;
int dp[50][50*50][50][2];
vector<int> S;

int solve(int i, int j, int k, int l) {
	if(i < 0 || j < 0 || j > 40*40|| k < 0 || k > 40)
		return 0;
	if(dp[i][j][k][l] + 1)
		return dp[i][j][k][l];
	if(k * i > j - k)
		return dp[i][j][k][l] = 0;

	if(S[i] + 1) {
		if(S[i] != k)
			return dp[i][j][k][l] = 0;
		dp[i][j][k][l] = 0;
		for(int k_ = k + l; 0 <= k_ && k_ <= 40; k_ = k_ + (l == 0 ? -1 : 1)) {
			dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k_,0)) % mod;
			if(l == 0)
				dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k_,1)) % mod;
		}
	}
	else {
		dp[i][j][k][l] = 0;
		if(l == 0) {
			for(int l_ = 0; l_ < 2; l_++)
				dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k,l_)) % mod;
			dp[i][j][k][l] = (dp[i][j][k][l] + solve(i,j-1,k-1,0)) % mod;
		}
		else {
			dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k+1,0)) % mod;
			dp[i][j][k][l] = (dp[i][j][k][l] + solve(i,j+1,k+1,1)) % mod;
		}
	}
	return dp[i][j][k][l];
}

class FoxAverageSequence {
	public:
	int theCount(vector <int> seq) {
		S = seq;
		for(int i = 0; i < 50; i++)
			for(int j = 0; j < 50*50; j++)
				for(int k = 0; k < 50; k++)
					dp[i][j][k][0] = dp[i][j][k][1] = -1;
		for(int i = 0; i < 50*50; i++)
			for(int j = 0; j < 50; j++)
				dp[0][i][j][0] = dp[0][i][j][1] = 0;
		if(S[0] == -1) {
			for(int i = 0; i <= 40; i++) {
				dp[0][i][i][0] = 1;
			}
		}
		else
			dp[0][S[0]][S[0]][0] = 1;

		ll res = 0;
		for(int i = 0; i <= 40 * 40; i++) {
			for(int j = 0; j <= 40; j++) {
				for(int k = 0; k < 2; k++) {
					res = (res + solve(seq.size()-1,i,j,k)) % mod;
				}
			}
		}
		/*
		cout << endl;
		for(int i = 0; i < 5; i++) {
			for(int j = 0; j < 20; j++) {
				for(int k = 0; k < 50; k++) {
					cout << dp[i][j][k][0] << "," << dp[i][j][k][1] << " ";
				}
				cout << endl;
			}
			cout << endl;
		}
		// */
		return res;
	}
};

感想

$O(n^{2}m^{3})$ 解で解いた人がTLEせずにACしてるのが悔しかった*2。計算量の落とし方としては良くある方法*3だが、seqのi番目の要素が-1でないときにループを回してdp表を更新しても全体的な計算量が悪くならないという点がお洒落だと思った。

*1:通るらしいんだなぁ。。。これが。

*2:40^5 が大体 1e8 なので落ちても良さそう

*3:和をdp表のどっかから持ってきて計算量を落とす方法

2016-02-29

SRM356 div2 medium 500pts : AverageProblem 解説

競技プログラミングプログラミング

はじめに

SRM356 div2 500pts を部内の練習で解いたところ、面白い問題だった && 人々が辛そうにしてた && 日本語の解説記事が見つからなかったので解説記事を書いてみることにした。

問題概要

0 以上 10 以下の範囲の整数で評価する、評価項目が 1 つ以上あるアンケートを 1 つ以上とった。各アンケート毎に、そのアンケートの評価項目毎の評価の平均を小数第4位で切り捨てたものが与えられる。アンケートに回答した回答者の人数としてありうる人数の最小値を求めよ。

1 ≤ アンケート数 ≤ 50
1 ≤ アンケート毎の項目数 ≤ 50

解法

アンケートの回答者を1人から順に調べ、その人数でアンケートを回答したとき、入力として与えられた平均となるような回答の方法があるかどうかを調べればよい。アンケートの項目ごとにどのような判定を行うべきかを解説する。

判定法

アンケートの回答者を $N$ 人、各人のアンケート項目への評価を $a_{i}$ とすると、アンケートの評価の平均 $E$ は、
$E = \cfrac{\sum_{i=0}^{N-1}a_{i}}{N}$
入力として与えられる平均 $E_{in}$ は小数点以下3桁まででそれ以下の値は切り捨てられている。切り捨てられた値を $r$ として、 $E = E_{in} + r$ と表せる。上の式は
$\sum_{i=0}^{N-1}a_{i} = N \cdot E_{in} + N \cdot r$
と変形でき、右辺を整数にできるか否かを判定する問題となる*1。今回の場合、左辺の値が具体的に何になるかを考慮する必要は無い。右辺を整数にするためには、入力として与えられる平均が表現できる最小の値が $p$ *2、アンケートの参加人数が $N$ 人(定数)であったとき、半開区間 $[N \cdot E_{in} ,\ N \cdot E_{in} + N \cdot p)$ に整数があればよい。 $r$ が $0 \leq r < p$ の範囲の値を取るためである。

計算量

アンケートの数を $Q$ 、アンケート $i$ の項目数を $q_{i}$ 、与えられる平均が表現できる最小の値を $p$ とすると、時間計算量は
$O \left( \cfrac{1}{p} \cdot \sum_{i=0}^{i=Q-1} q_{i} \right)$

実装

上で書いたことを実装すればよい。誤差対策として入力として与えれれる値を1000倍して持っておくとよい。整数であれば剰余演算子を用いれるので、判定を行う部分の実装も楽になる。

#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <sstream>
#include <list>
#include <deque>
using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<long,long> pll;

class AverageProblem {
	public:
	int numberOfParticipants(vector <string> marks) {
		vector<int> ave;
		
		// 入力の受け取り部
		for(int i = 0; i < marks.size(); i++) {
			stringstream sstr(marks[i]);
			string s;
			while(sstr >> s) {
				// 入力を1000倍して, ave に追加する
				int a = 0;
				for(int j = 0; j < s.size(); j++) {
					if(s[j] != '.') {
						a *= 10;
						a += s[j] - '0';
					}
				}
				ave.push_back(a);
			}
		}

		// resはアンケートに答えた人の人数の候補
		int res = 1;
		// このループは1000回を超えて回ることはない
		while(1) {
			bool flg = true;
			for(int i = 0; i < ave.size() && flg; i++) {
				// diff は ave[i] * res 以上の最小の整数との差
				int diff = (1000 - (ave[i] * res) % 1000) % 1000;

				if(diff < res) // 条件成立
					;
				else
					flg = false; // 条件不成立
			}

			// ave のすべての要素に対して条件が成立していれば, その res が答え
			if(flg)
				return res;
			// そうでなければresを増やしてまた調べる
			res++;
		}
	}
};

感想

素直な問題で解いていて面白かった。計算量の見積もりや、アンケートの回答者がN人のとき入力として与えられた平均にできるか否かの判定など、div2med(500pts)の問題としては難しいように感じた。この難易度なら最近のdiv1easy(250pts)でも通用するのではないだろうか。切り捨てた値を適当な文字で表して式変形を進めるという考えに至れれば解け、行う式変形も分母を払う程度で難しくないため、その発想に至れるかどうかが勝負の分かれ目のよう。

無視した値を適当な文字で表すというアイデアに関しては、例えば電気系であれば抵抗の誤差を適当な変数として表して、最終的にどの程度誤差が現れるかを調べるなどの応用が利くので押さえておきたい。

*1:右辺が整数になりさえすれば, 左辺は右辺と一致するように選ぶことができる

*2:うまく表現できてる気がしないが、つまりは $E_{in}$ の精度のこと。今回は0.001