Hatena::Grouptopcoder

れんしゅうちょう。 このページをアンテナに追加 RSSフィード

2014-10-20ICPC2014 アジア地区予選 東京大会 参加記

[]ICPC2014 アジア地区予選 東京大会 参加記 23:18

去年に引き続き, チーム Sophinyan として, ACM/ICPC アジア地区予選 東京大会に参加しました.

結果は, 7完最下位の, 9 位(チーム順位) でした. 順位表

チーム順位大学順位国内チーム順位国内大学順位解いた問題数時間
98657/111089

酷いバグに苦しんで, 時間さえあれば解ける問題に時間を残せなかったなど, 反省点はありますが, 健闘できたかなぁと思います.

僕は, 選手としての ICPC はこれで終わりです.

運営/手伝いをして下さった方々, スポンサーの方々, JAG の皆様, 応援して下さった皆様, それから(同じチーム, またはライバルとして)一緒に闘って下さった皆様, ありがとうございました.


以下, 詳細.

提出時刻付きの順位表とかが後悔されたら, 時刻を挿入する更新をする可能性があります.

みなさん, 来年は, Twitter ID とアイコンが書いてある名札を下げてきましょう!!!!

*1



序盤以外は, 大体同時に二問を頭に入れるように努力していた.

1問を実装しつつ, もう1問の実装を考えるとか, 1問のバグ埋めてそうな所を思い出しつつ別のを書くとか.


いつものように時系列順(?)にイベントを列挙したやつ.

時系列順にしたかったけど, 割と記憶が危ういので, 色々違いそう.

少なくとも, 同じ問題内での思考順序みたいなのはあっている気がする.


始まる.

us 配列化と caps lock 潰しをし, .vimrc とテンプレを書く.

A(RLE)を聞きつつ, 自分でも読む.

入力形式が, 1回の実行で複数ケースあるいつものアレじゃなくて, 若干戸惑うも, ジャッジ環境が変わったからかぁと納得.

書く. 提出. AC.


B(+と*のやつ) を聞く.

一瞬真面目にパーザ書くのかと思いきや, スタックつかって頑張る系だった.

(左優先は逆ポーランドみたいな感じでやる. 掛け算優先は, 掛け算のみちゃんとやって, 足し算は無視して, あとで合計取る.)

書く. なぜか struct とか使って, ちゃんとトークナイズしながら入力を取っていて, 一瞬真面目に書こうとした跡がある. 提出. AC.


C(進んだり戻ったりするやつ) を聞く.

被ってる所は一個にして... 的な事を言われて, ぱっと証明といい方針が思いつかなかったので, (考えている暇はもったいないので)D(放物線)を聞く.

D の計算をお願いしつつ, 順位表で operasan が解いていた F(全域木) を読む.

Cを imos 法のようにやると簡単に解ける事に気づいたので, C を書く. 提出. AC.


D を大体実装する. 出力するものを知らなかったので, 聞くと, 速度らしい. 式をお願いしつつ F と平行して実装する.

D は, サンプル 2 だけ答えがあわず, とりあえず clar 投げながら, サンプル 2 の解析をお願いする.


Fを実装し, 投げるも, TLE. 計算量大丈夫なのにーと思いつつ定数倍高速化するも, TLE.

なぜか完全に O(nm * 小さいの) だと思っていたけど, これ O(m^2 * 小さいの) じゃん (完全にアホだった)(大絶望).

候補の辺を, 最初の全域木に使った n 本に制限すればいいだろうと思いつつ, 簡単な実装を考える.

D の 45 度というコーナーケースを教えてもらい, その時の値を計算してもらう.

F の(既に書いた UnionFind を使う)実装を思いつき, 書く. 提出. AC. (実はちょっと修正するだけでよかった気もする. この辺迷走していた.)

D も提出. AC.


E(車), G(括弧), H(ルンバ) も既に聞いていた気がする.


H は, かなりの量の写経しなければならないので, 手が開いた時や煮詰まった時に写経しつつ後回しにする事に.


G は, 解法は割とすぐ解り, 書く. 投げる. RE.

仕込んでいた, いくつかの自明な条件の assert で落ちているらしく, 探しても変な所は見つからない.

E を平行して実装しつつ, デバッグする.

G は, しょうがないので, どの assert で落ちているかを submit debug. 非常につらい.

二分探索の方法を変えてみたり, 色々やるも, やはりバグが取れない.

E は, 提出するも, 提出する物だか提出先だかを間違え, TLE と認識する.

状態を int にエンコードしたりしつつ, G のデバッグ.

E は encode したら何やらダメで, 提出先を間違えた事に気づき, 元の状態まで undo して提出したら, AC した.

G は, デバッグ出力と共に色々削って行ったら特定でき, クソみたいなバグで死んでいた.

update 時の, 見ている node の範囲がおかしくて, segtree の node を二倍用意したら AC した.

何が悪かったかというと, ライブラリのミスで,

void update(int l, int r, ll v, int k=0)

みたいなのを,

void update(int l, int r, ll v, int k=1)

と書いていた(死).


あとは, H をひたすら写経していた所で時間切れ.


解き方が解っているのに解けなかった問題があるのは悔しい.

しかし, 周りのチームも似たような状況だったようだし, 完全に解らなくなるのもまた悔しいだろうし, 7完できただけありがたいと思うべきかもしれない.

*1:超重要な一言を忘れていたので 2014/10/21 00:19 追記

2014-09-16JAG 夏合宿 参加記

[]JAG 夏合宿 2014 参加記 01:29

2日目の途中から参加した.

結果は,

2日目: 一人で参加. AとD の2完で20位.

3日目: @tokoharu_sakura さん, @mikecat_mixc さんと bugnyan で参加. A-D, F-H, K の 8完で6位.

4日目: @nsd_fb さん, @yuusti さんと Tera^nyan で参加. A-F の 6完で6位

でした. 楽しかったです. (小並感)

全体を通して, ワンチャンある問題が解けないという事が多かったように思う.

ワンチャンあると感じた問題が多いという事は, 強くなるチャンスであると信じて, 精進したいです.

あと, チーム戦楽しい. またいろんな人と組んでチーム戦してみたい.

チーム組んでくれた方々, JAGの方々, 某社の方々など, 色々ありがとうございました.


2日目

りんごさんセット.

問題文が簡潔で読みやすかった.

東京へ帰る新幹線中から参加し始め, 昼過ぎにオリセンに到着した感じ.

開始時とかトンネルの中でネット繋がらなくてつらみを味わった.

基本的に, ちゃんと考えるという事を放棄しすぎていた気がする.

G(Snake), 解きたかった. 凸包使おうとまでは行ったけれど, ちゃんとそこで止まって思考すべきだった. (適当に書きすぎ)

H(Distance Sum) は, 大体はやるべき事は解ってたし, 解けてもよかったなぁという気がした. ちなみに, 解説の場合分けは多分要らなくて, 偶奇どちらの場合も, 今の場所から追加された場所までの path 上でにぶたんすればよいハズ.

J(Hyperrectangle) は, 包除原理だろー -> d <= 300 (絶望) という感じだった. なるほど, こういうのもあるのか...


3日目

JAGセット.

リクルート社で行われた.

至れり尽くせりすぎてすごかった. 神社とか言われてた.

@tokoharu_sakura さん, @mikecat_mixc さんと参加した.

みけきゃっとさんが A を解いている間に B を読んで, まぁやれば出来るやつやなと思って詰めずに他のを読みだしたりしてしまって, ICPCルールでのチーム戦を完全に忘れた感じの戦犯だった.

B終わって, みけきゃっとさんが F はフローの問題だと言っていたので, 自分でも読んだら, 最小カット持ってくるだけだったので通した.

後, 色々問題を把握して, D は水の量で三分探索で出来そうだなぁとか, G は nCk と分割数でやればいいよねとか, K は 2近傍の全探索でいけるねとかいう話をした.

I は 1, 2彩色はやるだけで, 3 と 4 の判定は 3 を適当に枝狩り探索じゃないのという話とかもした. (もっと詰めた話をしておけばよかった. みけきゃっとさんには申し訳ない...)

とこはるさんが E の解法を教えてくれて, 合っているっぽかったので書いて提出するも, WA.

結局 WA が取れなくてつらかった. なんでなんだろう...

I と E はチャンスがあったなぁという感じがする.


4日目

阪大, 東工大セット.

@nsd_fb さん, @yuusti さんと参加した.

A, B をやるから好きな問題読んでという事を言われ, 最後に図が見えたので最後から適当に読み, その後共有する.

以下, 読んだり共有した時の感想.

C: 三次元幾何だけど, 点の線分への射影しか要らんのでやれば出来る

D: なんか DP っぽい問題. (入力でかいと指摘されて, 適当なテクで n log に落とす系じゃないのと言うけど, 全然わからん)

E: 実装ゲーっぽいけど無限ループとか大丈夫? (盤面サイズ x プログラム長メモ出来るし余裕でしょと言われる)

F: 文字列マッチやるだけっぽい. (文字列苦手勢としては, おまかせしたい)

G: 2^18 だし, bitDP とかしたけど, 壊すとかあるからどうしようね...

H: なんかこれは頑張れば出来る系の ad-hoc では???

I: これ面白いけどどうにかならんかねぇ... 最小有向全域木みたいな何かとか?

J: これは思いつきゲーっぽいけどやばげだ...

とりあえず, C を書く.

EPS 必要な所(接線)を EPS どっちに付けるんだっけ, 問題文にあったかなぁと思いつつ後で書く事にしたら忘れて提出, WA.

問題文に無かったけどサンプルにあったから書いて提出, WA.

問題文よく見てみたら, l <= 10^16 とかあって絶望.

無意味な long long 制約やめちくりー.

怒りの でふぁいん いんと ろんぐろんぐ してACした.

E, F は書いてもらえる事になって, D, H, I, J を考える.

J はしばらく考えて思いつかないので, 残念だけれど捨てる.

I はしばらく @nsd_fb さんと考えて, 最小有向全域木のアルゴリズム教えてもらったりしたけど, なんか steiner tree っぽい難しさな気がしてきてわからず, 悔し紛れに NP-hard じゃないのとか思いながら捨てる.

H は少し考えて, これ D の方が僕に合ってるなぁと思って, 保留する.

ひたすら D を考える.

メモを見ると, 「monge, 貪欲, データ構造, にぶたん, ダブリング, 平方分割, 分割統治, convex-hull trick」とか, 考慮するリストとしてメモってあった.

終了30分くらい前に, 更新する箇所が少なかったりとかは全然しなさそうだし, 二乗の DP を高速化する系じゃ不可能な気がして来て, 「これ貪欲でしょ」と言い出す.

一回目の選び方を計算して, 「i*P + C_i で貪欲だー」と言い出して, 頭冷やす為にトイレに行く.

帰ってきたら, 入力処理とか書いてくれていた(感動).

この貪欲でサンプル全部通るっぽいので, 書いてみる.

更新式を明示的に書き下さなきゃいけないので, 計算してみると, 貪欲が正しい事が式から出てきて歓喜する.


証明を一応書いておくと, k 回自炊している時, 更に i 番目を自炊にする時, 満足度の変化を考えると,

(i以降の自炊で得られる幸福度が増える) + (iで自炊した時の幸福度) - C_i

= 2 * (i以降の自炊) * P + (Q - i + 2 * (i以前の自炊)) * P - C_i

= 2 * ( (i以前の自炊)+(i以降の自炊) ) * P + P*Q - i*P - C_i

= 2*k*P + P*Q - i*P - C_i

となる. よって, k に関する累積和を考えると, i*P + C_i の和が小さくなる i を k 個選ぶ事になるから, 貪欲でよい.


提出して WA.

accumulate の第三引数に 0LL じゃなくて 0 渡していた(絶望).

気づけてよかった.

修正して提出, AC った. (終了10分前)


なんか, 危うい所で D 解けたけど, 2-3時間くらいこれ考えてたし, 実装重いの全て任せてしまったし, これで D が解けてなかったら完全に戦犯だった.

自分で書いたの 100 行もないし, ありがたやーという感じ.


合宿中も「疲れた」ばかり言ってたけど, コンテスト終わると更に疲れて, 口を開くと「疲れた」が出てきて非常にアレだった. (ごめんなさい)

疲れを取り除くべくがんばって休みます.

2014-07-12ICPC2014 国内予選 参加記

[]ICPC2014 国内予選 参加記 22:52

後輩2人と, チーム Sophinyan として, ACM/ICPC 国内予選に参加しました.

6完/7問で, 7位(チーム順位). 順位表

チーム順位大学順位解いた問題数時間
766/726280

2つ目の出力ファイルのタイムスタンプは次の通り.

ABCDEFG
6'5717'2058'22(1WA)82'36104'58-147'06

なんかこんないい順位になってしまっていいんだっけという感じだった.

アジア地区予選も頑張りたい.


以下, 時系列順の詳細.

見難くてごめんなさい.

僕の記憶容量3バイトくらいしかないので, 問題聞いたタイミングとか違うかも.




事前の打ち合わせとして,

  • とりあえず僕は A を読んで書く.
  • チームメイトには, 基本的に B から先を順に読んでもらう.
  • 幾何は優先度高めに確認して貰う.
  • 各問題について, 「どういう系の問題か」 は早めにみておいて欲しい.

という事を言っていた.


0'00


始まる.

A 読む.

えっまぁはい, これ A 問題なの, A にしてはむずいような.

0 円はありなのか, どっちなんだ. rep 書いたし, とりあえず 0 も含めておくか.

書く. サンプル合わん.

あぁ, やっぱ(当たり前だけど) 0 円は無しなのね.

よく見たら input に書いてあった. こんな所に書くの...

提出, AC.

あれ, なにこれヒントとか書いてあったのか, そんな下に書くなよ...


6'57


B と C を聞く.

C めんどそうだなぁと思いながら B を書く.

石に 0 が使われていないのはよいな. 初期状態全部埋まっているのも嬉しい.

適当に書いたら微妙に間違っていたので, どうせこの辺だろうと思った所を, バグらなさそうな感じに修正したら, サンプル通った.

提出, AC.


17'20


C の方針を立てる.

ヒストグラム的なのを作り, 枠の線分を持ち, 主にそれに円が接するか否かで二分探索すればよさそう.

書く. バグってる.

にぶたんなのに範囲二分してなかった.

修正. 提出. WA.

後で見たら, WA の原因は, 値がでかい所での判定をさぼっている事だった. (初期幅を適切に設定したら判定さぼれるだろーという脳内の判断だった)


死にたいなぁと思いながら, とりあえず D を聞く.

「辞書順の最後はこうやれば解る」

「辞書順の最初もこうやれば出来る」

というような事を聞いて, 確かに出来てるなぁと思う. これが想定解なら, ちょっと面倒そうな気がして, もうちょい進めておいて貰う.

E を聞く.

グラフで, 辺の上を動きながら取っていくような問題だと把握. 最小全域木かなんかごにょごにょする系? (蟻本の徴兵のヤツ思い出していた)

F もこの辺で聞いたかも?


C を思いついた.

どうせヒストグラムの枠を多角形と思った時の頂点の所が問題なので,

こいつらを超える時間の最小値を取ってくればいい.

書く. 提出. AC.


58'22


D を詳しく聞く.

とりあえず, 言われたようにやったら, 辞書順で一番最後のは出来た.

もう少し頑張ったら, 辞書順の最初の方を探索出来るようになった.

微妙に謎実装してたけれど, これ普通にそのまま dfs すればいいだけじゃんと思って綺麗に書きなおす.

これ意外に行けるんじゃね? と思って, 初めの 10 個くらいしか取ってきてなかった制約を外して入力喰わせてみる.

余裕で動いてるっぽいので, 適当に出力を 10 個までにするの書いて提出. AC.


82'36


E の問題をよく聞く.

この辺で G も概要を聞いたかも.

どうやるんだ, うーん, ぱっとわからんなぁと思いつつ, 更に聞いてるとどうやら木らしい.

それならまぁ(葉除いた)最遠点対で出来るね.

n=2 あたりがコーナーケースっぽい気がしたけれど, 3 点以上はあるらしい.

「大体の場所は 3 重だよね??」

「端のほうは 1 重だよね??」

とか確認しながら書く. 提出. AC.


104'58


G を詳しく聞く.

どうやら, 3 つの円盤が重ならない (共有点すら持たない) 制約があるらしい.

とりあえず,

「p か q が少なくとも一つの円に含まれているなら, 「どの円に含まれているか」が一致するかの判定だけでよい」

事を確認する.

あとは, 円の外側だけが問題.

要するに, 円同士が回りで色々くっついて囲ってたりするとやばいよねーという話.

これは, 円の中心を頂点, 交差している円の所に線分があると思った平面グラフで, p と q が同じ平面に含まれるか否かと一致しそう.

「こういうのと一致しそうだよね?」 と確認しつつ, 平面グラフと双対グラフのライブラリをひっぱり出し, ひたすら写経.

サンプル喰わせる. せぐふぉ.

何箇所か cout << __LINE__ << endl; を追加して場所を特定すると, vector の初期化忘れ.

修正してサンプル喰わせる. なんかおかしい.

よく見ると, 頂点の座標設定し忘れていた.

修正. 提出. AC.


147'06


残りは F しかない.

辞書順は判定さえ出来ればよいので, 判定ルーチンがあれば嬉しいという事は, 他の問題を解きながら話しておいた.

後輩たちが, 「こうしたら出来そう」みたいな操作のアイディアを書いてくれていたけれど, 「それで出来なければ必ず無理」というタイプっぽくなくて, どうしよう...

とりあえずサイコロライブラリを写経.

わからんので, とりあえず, ナイーブな dfs を書く.

全然実行終わる気配がないが, コンテストが終わりそう.

実はもう少し頑張っていたら出来たのかもしれないけど, そんなことないのかもしれない.

おわり.

2013-11-25ICPC2013 アジア地区予選 参加記

[]ICPC2013 アジア地区予選 会津大会 参加記 23:09

チーム Sophinyan として, ACM/ICPC アジア地区予選 会津大会に参加.

5完最下位の, 17位(チーム順位). 順位表

チーム順位大学順位国内チーム順位国内大学順位解いた問題数時間
17111375/10703

割と色んな人と喋れて, 楽しかった.

結果的には, 反省点はいくらでもあるけど, 当初の目標(去年のように Honorable Menthion にならず, 順位が欲しい)は達成出来て, 良かったと思う.

来年はもう少し上を目指したい.


例に依って参加記というよりただイベントを時系列順に並べた何かだが, とりあえず, 競技に関係する所だけ書こうと思う.


初日は, バスが遅れて辛みを感じ, CapsLock潰しが出来なくて辛みを感じ, JavaChallengeはそもそも動かし方すら解らず辛みを感じた.

結局JavaChallengeは幅探すらバグってrandで出したけど, 提出ミスってたっぽく不参加に. CapsLock潰しは他チームの方に教えていただいた.


色々すっ飛ばして本番.

CapsLock潰しと.vimrcをちょっと手間取りつつ書いて, A問題を読み始める.

{}_{20}C_{10}dfsだなぁという感じだが, {}_{20}P_{10} なら一瞬で書けると思って, それがどれくらいの大きさか解らず, まぁとりあえず書いてみた.

実は10の12乗とか超えてる感じらしく, まぁサンプル余裕で通らないので, {}_{20}C_{10} を書く事に.

ライブラリでnビットのうちkビットだけ立ったやつを列挙するループを持ってきてたのを思い出して, それ使って書く→AC(13分).


この辺でB, C問題後輩が読んでいてくれて, それを聞く.

Bはまぁシミュレーション一択だなぁと思いつつ書く. ちょっとクソみたいなバグ(次使う用の配列を読んで弄ってた)出したけどAC(38分).


C問題は, ちょっと手でサンプルみつつ確認.

座標に比べて圧倒的に四角形の数が少ないので, まぁ座圧してやる.

なんかこれもクソみたいなバグ(floodfillで隣接が同じ色か確認せずに塗って再帰)出したけどAC(103分)


確かデバッグしながらD問題とE問題を把握したような気がする.

E問題はまぁひと目でダイクストラ余裕でしたという感じなので, 書く.

サンプルの3つ目でくっそ時間かかって, つらみを感じる.

しょうがないので, Hを解く. こっちもサンプルあわずに辛い.

なんかこの辺でJ以外の全ての問題をデバッグ中に把握して, 各問題の評価をしていた.


D: 算数だけど式立てるのヤバそう. 実数にして分数探索する手もあるけどどっちにしろつらい.

E: ダイクストラやるだけで計算量も余裕そうなのになんで遅いのか全くわからなくて辛い.

F: 最近点対みたいな感じなのは解るけど, そもそも最近点対書いた事無いし, 後回しだなぁ.

G: なんかずらしながらsegtreeをアップデートしてく系のDP高速化テクっぽい感. 家でゆっくり時間がある時にやるならいいけどこの状況で解ける気はあんまりしない.

H: よくある点列挙して各点で判定するだけの幾何なのにつらみ. サンプルで死んでるのでまだマシ.

I: なんかDPっぽいけど, じっくり腰を据えてやんないとちゃんと見えなさげ.

J: ひと目で正規表現クロスワードだけど, ある程度解かれるまで読む価値無し.


なんか, 結果的に大体評価はあっていた気がする.

とりあえず, Eの高速化と, Hのデバッグを思いついた事から並列でやった.

下の二つは, 折り重なるようにやっていて, AC時間が9分しか違わなくて, 点数もったいない感がすごい.


Eは, ダイクストラが間違っていないかを何度か見てみるけど, 何度見ても正しい.

とりあえずA^*にしてみるも, 全然速さ変わらん.

Eはstringで持って, 辺を一々作ってるのが遅いのかと思い, 前計算で各頂点をintにエンコードして, グラフを配列で陽に持つ.

それでもクソ遅くてダメげ.

途中で出力してみると, どうやらサンプル出力の半分程度のコストのところまではなんとか行ってて, 双方向ダイクストラにすればよいと思い, 本で終了条件カンニングしつつ書く.

サンプルもなんとか出力出たので投げる→AC(230分).

ちなみに, 原因はおそらく GLIBCXX_DEBUG フラグ. 死にたい.


Hは, サンプルを見ると, 候補の交点が一つも無いパターンで死んでるっぽい.

適当に候補の点を, 適切な線分のn等分点とかで追加してみて, TLEWAを数回出す.

(候補の交点の入れ方的に)交点なけりゃOKという事に気づき, それで提出→WA.

EをACしてから, 順位表を見つつ, Hのバグ取りに性を出すべきか, Dを頑張って倒すべきか迷って, 迷いながら最後に100-2*hogeくらいの矩形に入ってるか判定する所でEPS噛ましてない事に気づき, 修正→AC(239分).


デバッグ中に後輩にDの立式をお願いしてたり, 少しづつ書いたりした気がするけど, あんまりうまいこと行かない.

自分でも立式しようとしていて, 色々方針を転換していてヤバかった.

結局終了間際にサンプルが結構あってるヤツが出来たけど, 重なるパターンとかで明らかに死んでいてアレだった. 辛い.


良かった点:

1. 問題を殆ど読まなくてよかった事.

チームメイトがかなり読んでくれた上に誤読も無く, 僕がちゃんと読んだのはAだけで済んだ.

2. 解けない問題, 諦める問題の選定が割と的確に早く出来た事.

解けない問題を延々と考えて時間を使ったりする余裕は無いので, 最後以外ほぼフルに「結果的に点数に寄与した問題」に時間と頭を使えたのは, 非常に良かった.


良くなかった点:

1. EとHを交互にやっていて, 両方ACが遅くなってしまった事.

思いついた順にやったので仕方ない所はあるが, (点数的な意味での)時間が非常にもったいなかった.

2. Hを適当に投げすぎた事.

EPSでのWAはまぁ仕方ないと思えるが, 他のは適当すぎた.

ちゃんと考えれば解ったことなのに, てきとーに解決しようとするのは非常に良くない.

3. operator書くのサボった事.

D問題, 式がごちゃごちゃするのは明らかだったので, ちゃんと分数クラスにoperatorぶち込んで, ヤバい感じの sub(div(add(a,Q(60,1),... みたいなのを書かないで済むようにするべきだった.

4. 方針を色々思いつかなかった事.

Aは2^n全探索でも普通に間に合うので, 普通にもっと簡単に書けるのに気づかなかった.

Cの多面体定理とかも(選ばなくても)思いつくべき方針の一つだった.


来年に向けて, 精進したい.


追記(@ 12/15 23:15)

来年は皆さん TwitterID/Icon 入りの名札下げてきて下さいお願いします.

2013-07-15

[]ICPC2013 国内予選 参加記 00:56

こんなのを書いていた訳ですが, ただのコード置き場的になっていて, 参加記としての体をなしていないので, もう少しまともに参加記を書こうという感じです.

コードはそっちにあるので, その辺は省略.

参加記と言っても, 自分の記憶にあるイベントを時系列順に並べただけで, あまりまともな文章にはなっていないと思われるので, (読む場合は)適当に読み流すのがよいと思います.


金曜日はそもそも授業が無かった上に, 何時に出ればよいかの感覚が全くもって狂っていたので, 一時間以上前に学校に着いた.

コーチの先生を探しだし, 研究室で雑談をしていた.

サイコロ持ってきて無いという事に気づき, 先生に話した所, 正二十面体と, 十面体のサイコロを貸してくれた. (六面体は無かった)

チームメイトの二人は授業があり, 少し遅れて来る事になっていた.


雑談しているうちに, 5分前とかになっていて, 急にネットに接続できなくなって焦る.

自前のテザリングでもやってみるが, そっちでも繋がらない.

普通に開始時間を過ぎて, 「やべー」とか思っている間に, 元の回線がつながるようになったので, 数十秒遅れで問題を見る.

とりあえず印刷しながら, 画面半分でincludeとmain関数を書き, もう半分で問題を読む.


「答えは150*150を超えない」に気づかず, 「Aにしてはむずいなー」と思いながら書き始めた.

途中で気づき, 更に「対角線の自乗で計算すればintだよ!」という仏のような言葉も見えたので, そうする.


サンプル入れる→合わない.

条件の大小とかでクソみたいな間違えを数カ所していたので, 逐次修正.

A問題 AC (583秒: 9分)


B問題を読む.

「この問題, AOJでやった事ある!!」って感じだったが, まぁてきとーに書くとデバッグ大変そうという感じ.

とりあえずまともにstruct作って書こうと思い, 適当に書く.

サンプル入れる→合わない

チーム番号によるソートをするらしいと解って, それ追加.

入力1を入れると, 落ちる.

問題数のサイズで初期化するべきところを, チーム数で初期化している事に気づき, 修正.

この修正している辺りで, チームメイトの二人が来る.

Bの修正はすぐ終わりそうなので, とりあえずCから読んでもらう.


B問題 AC (1711秒: 28分)


順位表をちらっと見ると, 既にトップは3完とかしていて, うわーと思うが, まぁそれなりの順位.

まだ30分経っていない事に安心する.


とりあえず, 問題のページを最後までスクロールして, チームメイトに読んでもらう or サンプルを詳しく見てもらうような問題を決める.

Eが幾何でFが一瞬では読めない問題, そして1問減ってる事が解る.

とりあえずDとEを読んでもらって, Cを解く事にする.


C問題をぱっと見ると, 「k段階目の有権者はどうなってん?」とか疑問が湧いて, 先に見た二人に聞きながら問題をちゃんと見る.

問題が把握出来て, 解き方も解る.

一瞬stack使ってやり始めそうになったが, 普通に再帰で書きなおす.

参照する場所の間違えとか, 数字列→数の変換でゴミみたいなミスしていて, 手間取るが, 書き上げる.


Cの入力1が通っていえーいと思いながら入力2を投げたらまさかのWA.

ソースどう見ても間違ってないし, 提出ミスの可能性を疑って提出しなおしたら, 普通にAC.

アホみたいなミスして, 時間を失い, ペナルティをもらう.


C AC (3126(+1200)秒: 51(+20)分)


D問題とE問題を聞き, E問題で, 「3つ決めた時の位置と高さ」を立式しておいてもらい, D問題を解く事にする.


D問題で, 迷路をどう持つか一瞬迷うが, 「ある番号の下, 左, 右」を返す関数を作る方針で行く.

この関数は, 適当に出力すればどこがバグってるか解るので, デバッグはしやすかった.

しかし, 途中で, これらの関数はデバッグしたものと思い込み, サンプルに対する出力が間違っている原因を別の所に求めてしまって, アホみたいに時間を使った.


また, setでなくqueueになっていて, 「n段降りると3^nくらいの候補になる」とかいう事になっていて, しかし自分ではsetにしたと思い込んでいて, 「この遅さはなんなんだー」等と言っていた.

まぁデバッグでかなり時間を使ったものの, 無事AC.


D AC (7145秒: 119分)


順位表を見ると, そこそこの順位ではあるものの, Eが簡単そうであったので, Eを解かないと通らないかもしれないとか思い始める.

E問題の立式をしておいてくれたので, 導出を聞きながら実装する.

サンプルを入力するも, 数個だけ答えが合わない.


立式や実装を何度も観察し, 解法について色々話すも, どうにも正しそうに見える.

残り十五分とかになって, 自分の中ではだんだん諦めが入ってくるが, 順位表を見るに, このまま行けば通過出来そうな感じがしてくる.


やはり間違えが見つからず, そのまま時間切れになる.

順位表を見るに, 上位校の重複を数えなくても, 通過っぽいと解る程度の順位で, 去年と違って一安心した.


家に帰って解き直してみると, 立式の途中で, 図に騙される感じのミスがあった事が解った.

これは気づけない…/(^o^)\


今年は, 去年より明らかに練習を積んでいたが, 解いた問題全てでバグらせた.

しかし, バグの解消は多少早くなっている.

「バグらせるのはしょうがないから, デバッグがしやすいようにしよう」という感じでやるのが, (精神的にも)それなりによい戦略の一つであるなぁと思った.

地区予選では, バグを出さずに, 一発ACをしたい.

2013-07-12

[]ICPC2013 国内予選 22:46

23:48 Eを追記.

19位4問229分13765秒
AAC9分583秒
BAC28分1711秒
C1WA, AC51(+20)分3126(+1200)秒
DAC119分7145秒

チーム Sophinyan で出ていました.

Cの1WAは提出ミス.

A 整長方形

出力が150*150以内なので, 全探索する.

#include <iostream>
#include <iomanip>
#include <map>
#include <cmath>
using namespace std;

#define mp make_pair
#define snd second
#define fst first

bool solve(){
    int h, w;
    cin >> h >> w;
    if(!(h|w)) return false;

    pair<int, pair<int, int> > res;
    res.fst = 1000000;
    for(int i = 1; i <= 150; ++i){
        for(int j = i+1; j <= 150; ++j){
            if(i*i + j*j > h*h + w*w
                    || (i*i + j*j == h*h + w*w && i > h)){
                res = min(res, mp(i*i+j*j, mp(i, j)));
            }
        }
    }
    cout << res.snd.fst << " " << res.snd.snd << endl;

    return true;
}

int main(void){
    while(solve());
    return 0;
}

B ICPCの順位付け

適当にやってもバグらせる気しかしなかったので, わりとちゃんと書いた.

適当に書く時間+バグらせる確率*修正にかかる時間 > ちゃんと書く時間.

struct S{
    int team_num;
    vi wa, ac;
    int time;
    pair<int, int> get() const {
        pair<int, int> res(0, time);
        rep(i, wa.size()){
            if(ac[i]){
                ++res.fst;
                res.snd += wa[i] * 20;
            }
        }
        return res;
    }
    bool operator<(const S& o) const {
        pair<int, int> a = get(), b = o.get();
        if(a.fst != b.fst) return a.fst > b.fst;
        if(a.snd != b.snd) return a.snd < b.snd;
        return team_num > o.team_num;
    }
    bool operator==(const S& o){
        pair<int, int> a = get(), b = o.get();
        return a == b;
    }
};
bool solve(){
    int M, T, P, R;
    cin >> M >> T >> P >> R;
    if(!M) return false;
    vector<S> team(T);
    rep(i, T){
        team[i].team_num = i+1;
        team[i].wa.resize(P);
        team[i].ac.resize(P);
        team[i].time = 0;
    }

    rep(i, R){
        int m, t, p, j;
        cin >> m >> t >> p >> j;
        --t; --p;
        if(j == 0){
            team[t].ac[p] = 1;
            team[t].time += m;
        }else{
            team[t].wa[p] += 1;
        }
    }
    //rep(i, T){
    //    pair<int, int> a = team[i].get();
    //    cout << a.fst << ", " << a.snd << endl;
    //}
    sort(team.begin(), team.end());
    rep(i, T){
        if(i != 0){
            if(team[i-1] == team[i]){
                cout << "=";
            }else{
                cout << ",";
            }
        }
        cout << team[i].team_num;
    }
    cout << endl;
    //return false;
    return true;
}

C 階層民主主義

問題の理解にちょっと手間取った.

string s;
ll dfs(int l, int r){
    //cout << l << ", " << r << ": ";
    //cout << s.substr(l, r-l+1) << endl;
    if(s[l] == '[' && s[l+1] == '['){
        vector<ll> a;
        int depth = 0;
        int nl = l+1;
        for(int i = l+1; i < r; ++i){
            if(isdigit(s[i])) continue;
            if(s[i] == '['){
                if(depth == 0){
                    nl = i;
                }
                ++depth;
                continue;
            }
            if(s[i] == ']'){
                --depth;
                if(depth == 0){
                    a.pb(dfs(nl, i));
                }
            }
        }
        sort(all(a));
        ll res = 0;
        for(int i = 0; i < sz(a)/2+1; ++i) res += a[i];
        return res;
    }else{
        ++l;
        ll t = 0;
        while(isdigit(s[l])){
            t *= 10;
            t += s[l] - '0';
            ++l;
        }
        //cout << t << endl;
        return (t+1)/2;
    }
}

bool solve(){
    cin >> s;
    cout << dfs(0, s.size()-1) << endl;
    return true;
}

D 素数洞穴

螺旋の, 下, 左, 右の移動をガチで書いた.

Project Eulerで普通の螺旋は何度か書いた事があったが, バグが酷かった事を思い出して, こんな感じにした.

実際は, 1つ出来たらあとはコピペして修正するだけ.

問題の図を睨みながら, 数列を決定して, 1から30くらいまで出力して図と一致するか確かめる.

今思ったけど, complex<int> をキーにしたmapで持てば, 結構マシそう…

vi sieve(int mx){
    ++mx;
    vi f(mx, true);
    f[0] = f[1] = false;
    for(int p = 2; p < mx; ++p){
        if(f[p]) for(int q = p+p; q < mx; q += p) f[q] = false;
    }
    return f;
}

int sq(int n){
    int m = sqrt(n);
    if((m+1)*(m+1) <= n) ++m;
    if(m*m == n) --m;
    if(m%2 == 0) --m;
    return m+2;
}
int sita(int n){
    if(n == 1) return 8;
    int s = sq(n);
    int t = s-2;
    if(t*t+1 == n) return s*s;
    if(t*t+s-1 == n) return n-1; // 右上
    if(t*t+s+s-2 == n) return n+1; // 左上
    if(t*t+s+s+s-3 == n) return n+s*4+3; // 左下
    if(s*s == n) return n+s*4+3;          // 右下

    if(t*t+s-1 >= n) return n-1; // 右の辺
    if(s*s-s+1 <= n) return n+s*4+3; // 下の辺
    if(t*t+s+s-2 <= n) return n+1; // 左の辺
    return n-4*s+9; // 上の辺
}
int hidari(int n){
    if(n == 1) return 6;
    int s = sq(n);
    int t = s-2;
    if(t*t+1 == n) return n-1;
    if(t*t+s-1 == n) return n+1; // 右上
    if(t*t+s+s-2 == n) return n+s*4+1; // 左上
    if(t*t+s+s+s-3 == n) return n+s*4+1; // 左下
    if(s*s == n) return n-1;          // 右下

    if(t*t+s-1 >= n) return n-s*4+11; // 右の辺
    if(s*s-s+1 <= n) return n-1; // 下の辺
    if(t*t+s+s-2 <= n) return n+s*4+1; // 左の辺
    return n+1; // 上の辺
}
int migi(int n){
    if(n == 1) return 2;
    int s = sq(n);
    int t = s-2;
    //if(t*t+1 == n) return n-1;
    if(t*t+s-1 == n) return n+s*4-3; // 右上
    if(t*t+s+s-2 == n) return n-1; // 左上
    if(t*t+s+s+s-3 == n) return n+1; // 左下
    if(s*s == n) return n+1;          // 右下

    if(t*t+s-1 >= n) return n+s*4-3; // 右の辺
    if(s*s-s+1 <= n) return n+1; // 下の辺
    if(t*t+s+s-2 <= n) return n-s*4+7; // 左の辺
    return n-1; // 上の辺
}

vi pflg;

bool solve(){
    //cout << sita(16) << endl;
    //return false;
    //rep(i, 30) cout << i << ": " << sita(i) << endl;
    //return false;

    int m, n;
    cin >> m >> n;
    if(!(m|n)) return false;
    set<int> q, r;
    vector<pair<int, int> > res(m+1);
    q.insert(n);
    res[n].fst = pflg[n];
    res[n].snd = pflg[n] ? n : 0;
    while(!q.empty()){
        foreach(it, q){
            int t = *it;
            //if(pflg[t]) cout << t << endl;
            //cout << t << endl;
            int s;
            s = sita(t);
            //cout << " -> " << s << endl;
            if(s <= m){
                if(pflg[s]) res[s] = max(res[s], mp(res[t].fst+1, s));
                else        res[s] = max(res[s], res[t]);
                r.insert(s);
            }
            s = migi(sita(t));
            //cout << " -> " << s << endl;
            if(s <= m){
                if(pflg[s]) res[s] = max(res[s], mp(res[t].fst+1, s));
                else        res[s] = max(res[s], res[t]);
                r.insert(s);
            }
            s = hidari(sita(t));
            //cout << " -> " << s << endl;
            if(s <= m){
                if(pflg[s]) res[s] = max(res[s], mp(res[t].fst+1, s));
                else        res[s] = max(res[s], res[t]);
                r.insert(s);
            }
        }
        swap(q, r);
        r.clear();
    }
    pair<int, int> tmp = *max_element(all(res));
    cout << tmp.fst << " " << tmp.snd << endl;
    return true;
}

E つながれた風船

本番が終わってから, ねじれの位置であることを考慮していなかった事に気づいた.

書くと, こんな感じ. (サンプルは通っている)

typedef long double R;
typedef complex<R> P;
#define X real()
#define Y imag()
const R EPS = 1E-10;
const R INF = 1E100;

typedef pair<P, P> L;

struct C{
    P o;
    R r;
    C(){}
    C(P a, R b): o(a), r(b){ }
};
R dot(P a, P b){ return real(conj(a) * b); }
P vec(L l){ return l.snd - l.fst; }

P hLP(L l, P p){
    return l.fst + dot(p - l.fst, vec(l)) / norm(vec(l)) * vec(l);
}

R dPP(P a, P b){ return abs(a - b); }
pair<P, P> pS1S1(C a, C b){
    R d = dPP(a.o, b.o);
    R rc = (d*d + a.r*a.r - b.r*b.r) / (2*d);
    R rs = sqrt(a.r*a.r - rc*rc);
    P dir = (b.o - a.o) / d;
    return mp(a.o + dir*P(rc, rs), a.o + dir*P(rc, -rs));
}

C f2(C a, C b){
    pair<P, P> x = pS1S1(a, b);
    C res;
    res.o = (x.fst + x.snd) / R(2);
    res.r = dPP(x.fst, x.snd) / R(2);
    return res;
}
C f3(C a, C b, C bb){
    b = f2(b, bb);
    P v = (bb.o-b.o) * P(0, 1);
    C c;
    c.o = hLP(L(b.o, b.o+v), a.o);
    c.r = sqrt(a.r * a.r - dPP(a.o, c.o)*dPP(a.o, c.o));
    return f2(b, c);
}
R d3(C a){
    return sqrt(norm(a.o) + a.r * a.r);
}

bool solve(){
    int n; cin >> n;
    if(!n) return false;
    vector<C> in(n);
    rep(i, n) cin >> in[i].o.X >> in[i].o.Y >> in[i].r;
    vector<C> candidate;
    rep(i, n) candidate.pb(in[i]);
    rep(i, n) rep(j, i) candidate.pb(f2(in[i], in[j]));
    rep(i, n) rep(j, i) rep(k, j) candidate.pb(f3(in[i], in[j], in[k]));
    R res = 0;
    repsz(_, candidate){
        C c = candidate[_];
        bool f = true;
        rep(i, n){
            P v = in[i].o - c.o;
            if(d3(C(v, c.r)) > in[i].r+EPS) f = false;
        }
        if(f) res = max(res, c.r);
    }
    cout << res << endl;

    return true;
}

2012-07-07ICPC2012国内予選

[]ICPC2012国内予選 18:38

ICPC国内予選に, misawa2012として出た. 締め切り数時間前に登録するというアレっぷりであった.

http://www.cs.titech.ac.jp/icpc2012/domestic-contest-result.html

http://imoz.jp/icpc/2012-domestic.html

38位だったっぽくて, ギリギリ次行けるっぽい. 公式の発表はまだっぽいけれど. とりあえず, 忘れないうちに書いておこうと.

A→B→C→E(解けてない)の順に取りかかった. 問題はここに. 結局問題文通りにやればよい問題しか解けてないのである.


A問題

基本的にやるだけな問題であるが, どう解くかがキーであると思う. 方針に依って, バグ混入のしやすさや, タイピング量が違うだろうなぁと.

良かった点:
O(1)を書こうとせずに, ちゃんと自明なぶん回し方向を目指した.

反省点:
3年飛ばしなどやる必要無い.
こんだけのを書くのにどんだけバグらせたのか.
月日を0ベースにするのか1ベースにするのかの決断が遅すぎる. 曖昧に書き始めないで, 意識するべき.
llにするべきか, 確かめずにintにしていた. サンプル入力で最大ケースが出ていて, intで良いことをちゃんと確かめるか, llにするべきだった.

#include <iostream>

using namespace std;

int N;

void pre(){
    N = 5 * 39 * 2 + 20 * 10;
    return;
}

int solve(int y, int m, int d){
    int res = 0;
    while(y+3 < 1000){
        res += N;
        y += 3;
    }
    while(y < 1000){
        while(m <= 10){
            while(d <= 19 + (m%2)){
                ++res;
                ++d;
            }
            if(y%3 == 0 && m%2 == 0) ++res;
            d = 1;
            ++m;
        }
        m = 1;
        ++y;
    }
    return res;
}
int main(void){
    pre();
    int n;
    cin >> n;
    for(int i=0; i<n; ++i){
        int y, m, d;
        cin >> y >> m >> d;
        cout << solve(y, m, d) << endl;
    }
}

B問題

これも基本的にはやるだけ. stringでやるかとかで差が出るかもしれない. 出力する物を見誤って, 1WAした.

良かった点:
全部llにした. 入力的に大丈夫であっても, 安心感が違う.
関数に分けた点. デバッグがしやすい.
出力の±1とかの定数誤差をちゃんと考えずに, サンプルで修正した. 良くも悪くもあるが, この問題ではこれで良い.

反省点:
サンプル出力は目diffではなく, ちゃんとdiffを取れ.
使う変数名は統一しろ. 今回なら, どの関数でも桁数はdを使うとかするべき.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

typedef vector<int> vi;
typedef long long ll;


#define rep(i, n) for(int i=0; i<(n); ++i)

#define pb push_back
#define all(v) v.begin(), v.end()

vi f(ll n, ll k){
    vi res;
    rep(i, k){
        res.pb(n%10);
        n/=10;
    }
    return res;
}

ll next(ll x, ll n){
    vi hoge = f(x, n);
    sort(all(hoge));
    ll small = 0, large = 0;
    rep(i, n){
        small *= 10;
        large *= 10;
        large += hoge[hoge.size()-i-1];
        small += hoge[i];
    }
    return large - small;
}

int main(void){
    ll n, k;
    while(true){
        map<ll, ll> x;
        cin >> n >> k;
        if(!(n|k)) break;
        ll res = 0;
        while(!x.count(n)){
            x[n] = res;
            ++res;
            n = next(n, k);
        }
        cout << x[n] << " " << n << " " << -x[n]+res << endl;
    }
}

C問題

サイコロライブラリゲー. すぱげそーす様様である. サイコロが作れれば, 後はルール通りに転がしていけば良い.

良かった点:
スパゲソースちゃんと印刷していった.

反省点:
tとfからダイスを作る時, 乱択で適当にぶんまわせば出来るだろ的発想は良かったが, 他の所でバグらせて使わなかった. むしろ全パターンをsetとかで持っておけば楽だったハズである.
ちゃんとライブラリ使った事が無かった. 使えるようにしておかないといけない.
0ベースと1ベースの違いでバグらせすぎ.
foreachが死んでる.
ネスト深くなり, 行数も伸び, 対応する括弧が画面に収まらないようなループや場合分けを作るべきではない. 関数分けしろ. これのせいでかなり時間を食った. 関数分けする時間<<バグフィックスする時間*バグ出す確率

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

typedef vector<int> vi;
typedef long long ll;


#define rep(i, n) for(int i=0; i<(n); ++i)
#define foreach(it, v) for(typeof(v)::iterator it = (v).begin(); it != (v).end(); ++it)
#define mp make_pair

#define pb push_back
#define all(v) v.begin(), v.end()
typedef pair<int, int> pii;

enum FACE{
    TOP, BOTTOM, FRONT, BACK, LEFT, RIGHT
};
template<class T>
class dice{
    public:
        dice(){
            id[TOP] = 0;
            id[FRONT] = 2;
            id[LEFT] = 1;
            id[RIGHT] = 4;
            id[BACK] = 3;
            id[BOTTOM] = 5;
        }
        T& operator[](FACE f){ return var[id[f]];}
        const T& operator==(const dice<T> &b) const{
            const dice<T> &a = *this;
            return a[TOP] == b[TOP] && a[BOTTOM] == b[BOTTOM] && a[FRONT] == b[FRONT] && a[BACK] == b[BACK] && a[LEFT] == b[LEFT] && a[RIGHT] == b[RIGHT];
        }
        void roll_x(){ roll(TOP, BACK, BOTTOM, FRONT);}
        void roll_x2(){ roll(TOP, FRONT, BOTTOM, BACK);}
        void roll_y(){ roll(TOP, LEFT, BOTTOM, RIGHT);}
        void roll_y2(){ roll(TOP, RIGHT, BOTTOM, LEFT);}
        void roll_z(){ roll(FRONT, RIGHT, BACK, LEFT);}

        vector<dice> all_rolles(){
            vector<dice> ret;
            for(int k=0; k<6; (k&1?roll_y():roll_x()), ++k)
                for(int i=0; i<4; roll_z(), ++i)
                    ret.push_back(*this);
            return ret;
        }
        void roll(FACE a, FACE b, FACE c, FACE d){
            T tmp = id[a];
            id[a] = id[b];
            id[b] = id[c];
            id[c] = id[d];
            id[d] = tmp;
        }
        T var[6];
        int id[6];
};


dice<int> get_dice(int t, int f){
    dice<int> res;
    if(res.id[TOP] != t){
        if(res.id[BOTTOM] == t) res.roll_x();
        while(res.id[FRONT] != t) res.roll_z();
        res.roll_x2();
    }
    while(res.id[FRONT] != f) res.roll_z();
    return res;
}

int main(void){
    ll n;
    while(true){
        cin >> n;
        map<pii, int> height;
        map<pii, int> top;
        if(!n) break;
        rep(dicessss, n){
            //cout << "dice #" << dicessss << endl;
            int t, f;
            dice<int> d;
            int x = 0, y = 0;
            cin >> t >> f;
            --t;
            --f;

            d = get_dice(t, f);

            //height[mp(0,  0)] = 0;
            while(true){
                FACE sokumen[] = {FRONT, BACK, LEFT, RIGHT};
                int dx[4] = {1, -1, 0, 0};
                int dy[4] = {0, 0, 1, -1};
                int mx = -1;
                FACE to;
                rep(i, 4){

                    if(!height.count(mp(x+dx[i], y+dy[i])))
                        height[mp(x+dx[i], y+dy[i])] = 0;
                    if(d.id[sokumen[i]] > mx && height[mp(x+dx[i], y+dy[i])] < height[mp(x,y)]){
                        to = sokumen[i];
                        mx = d.id[sokumen[i]];
                    }
                }
                if(mx <= 2) break;
                if(to == FRONT){
                    //cout << "FRONT" << endl;
                    d.roll_x();
                    x += 1;
                }
                if(to == BACK){
                    //cout << "BACK" << endl;
                    d.roll_x2();
                    x -= 1;
                }
                if(to == LEFT){
                    //cout << "LEFT" << endl;
                    d.roll_y2();
                    y += 1;
                }
                if(to == RIGHT){
                    //cout << "RIGHT" << endl;
                    d.roll_y();
                    y -= 1;
                }
            }
            //cout << x << ", " << y << ": "<< d.id[TOP] << endl;
            height[mp(x,y)]++;
            top[mp(x,y)] = d.id[TOP];
        }
        int res[6] = {0};
        for(map<pii, int>::iterator it = top.begin(); it != top.end(); ++it){
            res[it->second]++;
            // cout << it->first << ", " << it2->first << ": " << it2->second << endl;
        }
        rep(i, 5){
            cout << res[i] << " ";
        }
        cout << res[5] << endl;
    }
}