裏紙

ほぼ競プロ、たまに日記

CF 631 E - Product Sum

問題

Problem - E - Codeforces

問題概要

長さnの1-indexedな配列aがある。この数列に対して一度だけ、数列のある要素を選び、その要素を数列内の好きな位置に移動するという操作をすることができる。

このとき、 c = \sum_{i=1}^n i \cdot a_iの取りうる最大値を求めよ。

  •  2 \le n \le 200000
  •  | a_i | \le 1000000

イデア

何も動かさなかったときのcの値をc'として、動かしたときの差分\Delta cについて考える。 以下、2つの場合について考える。

ある要素を右に動かす場合

l番目の要素を、r番目の要素となるように動かすとする(l \lt r)。 このとき、操作前と操作後でindexはこのようになる。

f:id:imulan:20190503233303p:plain

よって、index1からiまでのaの和をsum_iとすると、

 \Delta c  = l \cdot a_{l+1} + (l+1) \cdot a_{l+2}  + \ldots + (r-1) \cdot a_r + r \cdot a_l  - (l \cdot a_l + (l+1) \cdot a_{l+1} + \ldots + r \cdot a_r )

 =  (r-l) \cdot a_l - a{l+1} - a_{l+2} - \ldots - a_r

 = (r-l) \cdot a_l - (sum_r - sum_l)

 =  r \cdot a_l - sum_r + sum_l - l \cdot a_l

となり、これはCHTを利用し、lを減らしていきながら探索することでO(nlogn)で探索することができる(傾きには単調性がある方向で追加している)。

ある要素を左に動かす場合

r番目の要素を、l番目の要素となるように動かすとする(l \lt r)。

これも同様に計算すると、\Delta c = l \cdot a_r - sum_{l-1} + sum_{r-1} - r \cdot a_rとなり、今度はrを基準にすることで同様に探索ができる。

実装(C++)

続きを読む

ICPC 2019 World Finals に参加しました

2019年 3/30 ~ 4/6 に、ポルトガルポルトで行われた 2019 ICPC World Finals に早稲田大学チームの選手として参加しました。 簡潔に書きます。 日記 + 多少のコンテストの感想です。

3/30

朝11時に日本発、オランダ経由でポルトガルに行く。 乗り継ぎのタイミングで、同じ飛行機に中国のチームとかITMOとかがいて来たなーという感じがする。 ITMOの人たちがお揃いの大学のパーカーを着ていて、かっこいいって思った。 (日本の大学のパーカーもかっこよければね、、)

向こうのホテルに到着したのは現地時間で23時ぐらいだったけど、時差ボケとか関係なく疲れ切っていたので即寝た。

3/31

この日は、公式イベントとしてはディナーだけだったので夕方までは市街地を観光した。

World Finalsのロゴにも入ってるタワーにも登った。 市内を一望出来たけど、上があまりにも狭くて、通路・階段での行き交いも一苦労だった。

川沿いからの眺めが綺麗で、日曜というのもあって賑わっていた。

4/1

Registrationの日でした。

Registrationは午後からだったので、午前中はスポンサーセッションを聞いたり、ちょっとだけQuestをした。 JetBrainsのセッションではKotlinはいいぞみたいな話を学部生が受けるプログラミングの授業のサンプルを見せられながら聞いていた。 正直Javaをちゃんと書いたことが無いので、どれくらい良いものなのか分からなかったけど、色々記述量が減りそうな工夫が見えて、いいんだろうなあと思った。

Registrationでは、Tシャツをもらった後に、チーム写真の撮影をした。 僕たちの直前で筑波の人たちが撮影していて、あの情報量が多すぎる光景を生で見た(?)。

あと、インタビューを受けなきゃいけなくて、誰か一人が犠牲にならなければいけなかったんだけど、自分が犠牲になった。 かなり詰まりながらの返答になってしまったけど、ちょっと使われていた。

4/2

ICPC ChallengeとOpening Ceremonyの日でした。

ICPC Challengeは、マラソン、3時間、PCはチームで1台、チームメンバー誰もマラソン経験が無いのでハチャメチャになって破滅した。

Opening Ceremonyは、とても広いホールに人がぎっしりで、スタッフがたくさんいるんだなあということを実感した。 選手だけで133チーム×3人も集まるわけだから、それだけ大規模なんだよな、、

4/3

Dress Rehearsalの日でした。 直接会場に移動するのではなく、一回全チームの受付を済ませてから、列になって会場に向かうのはなんか世界大会っぽい感じがした。

ラクティスでは、まずポルトガル配列のキーボードをusにremapして、対応する記号のシールを貼る作業から始めた。 キーボード、別に対して高そうな買い物でもないしなんでusを揃えなかったんだろうと思っている。 普段からずっとusキーボードを使っているので、バックスラッシュを押そうとしてEnterキーを押しちゃうやつをプラクティスでも本番でも何回もやってしまった。

キーボードに多少でも慣れる意味もこめて、1人1問は実装した。 ちなみに、エディタは3人ともCLionを使った。 起動してそのままデフォルトで使っても不便が無いので、初手の環境構築タイムが無いので、来年も使えるなら使ってみると良いです。

熱心にQuestをやっていたチームメイトが、コーチとかスタッフとかでガチでQuestをやってるやつらに勝ち目がないと悟ってこれ以上やるのを諦めてた。

4/4

World Final本番の日でした。

結果はこんな感じ: f:id:imulan:20190407194600p:plain

序盤はA~D、E~H、I~Kに分けてとりあえず問題を読み、それぞれA、E、Jが行けそうだとなったのでそれぞれ実装を詰めたりしながら進めて、3つ全部WAになった(ええ...)。

この時点で1時間経過してたので、もうペナルティを気にせず完数を伸ばすことだけを考えることにした。Jは嘘だったらしいので、Aに2人で考察を詰めてもらう。その次にDも詰めてもらう。

自分は開始から3時間、Eと格闘し続けていた。個人的に問題文が読みにくくて、解釈にとても時間がかかって、ただ最終的にこれは実装軽い問題だったなあってなった(大反省)。

そこからは、Hをryo_issyと方針を詰めて実装を任せて、yamadとGを考えて、SuffixArrayの構築っぽいことをしたいなーというお気持ちを伝えたら解法を出してくれた。木のダブリングパートの実装を詰めておいた。

凍結後にこの2問とも通って5完になった。最終的に順位がついてよかったです。

自分がEにあそこまでハマったりしなければ、B、Jも出来たかもという感じがして完全に力出し切れた、という感じのコンテストとは個人的になりませんでした。 しかし、コンテストが終わった後はそもそもここに来れた事自体が奇跡みたいなものなのと、これでICPCのコンテスト本当に終わりだなと言う気持ちの方が強かったです。

Closing Ceremonyでは、yesnoを見ながら、最上位勢の異常さを改めて感じました(金メダルの4チームは本当に異次元すぎる)。 東大3位おめでとうございます。 凍結前1位だったのを見て、コンテスト中ながらに興奮したのを思い出します。

4/5

帰国日。

前日のClosingが21:30に終わって、そこからご飯を食べてからホテルに戻ってきたのが23:00で、この日は5:00に出発だったのでちょっとしか寝れなかった。 その分飛行機で寝ればいいかと思ってたけど、合計で3時間くらいしか寝られなかった。

おわりに

上にも書きましたが、自分はこれでICPC現役引退となります。 B3の春から始めた競プロで、B3(3人集められずにICPC出れない)、B4(国内予選落ち)、M1(つくば大会12位)ときて、学生のうちに世界大会に出場できるなんて夢にも思いませんでした。

実際、ここ1年ぐらいの自分の競プロのモチベーションはICPCに支えられていましたし、それに加えて文字通りの生きがいになっていました。 本当にチームメイトやコーチはもちろん、応援してくださった皆さん、研究室の先生や生徒にも感謝しかありません。

明日から労働が待っているので、新しいことの連続でこれからどうなっていくか分かりませんが、これからも義務感を感じない程度には競プロに関わっていたいなと思います。 最後まで読んでいただき、ありがとうございました。