Hatena::Grouptopcoder

Hiro180の日記

2018-12-04Writerをした時の話

この記事は Competitive Programming (1) Advent Calendar 2018 4日目の記事として書かれたものです。

はじめに

f:id:Hiro180:20181204205856p:image

と言っていましたが、予定を変更 (という名のテーマ決めの失敗) して、2016年に書こうと思っていたテーマで書くことにします。

テーマは「Writerをした時の話 (TopCoder SRM 694)」です。

経緯

元々一番好きな競技プログラミングのコンテストはSRMだったので、18歳になったら1回writerやってみたいなぁとずっと思っていて、2016年の春に18歳になった時から問題案を考え初めました。

そして6月の頭に6問(5問)完成して、7/10に行われたSRM 694のwriterをすることに決定しました。準備はJavaで想定解を書かないといけないなどかなり大変でした。

結果はこんな感じでした。

今振り返ってみると、Div1はHardがかなり簡単で、全完が20人近く出るのも当然だなという感じがします。(こういうセットはHard早解きゲーで順位がついてしまうので微妙ですね...) Div2も上位陣は3問とも見た瞬間に解いているような点数を出していて、もう少し捻りがあっても良かったかもしれません。

前置きはこんな感じで、以下各問題にコメントや背景を書いていこうと思います。 (自力で解きたい人はあとがきまで飛んでください)






















問題の詳細

MakingPairs(Div2 Easy)

概要:

同じ数字が書かれたカードを2枚組み合わせてペアにできるとき、最大でペアはいくつできるか


コメント:

流石にやるだけだと思います。このスロットに捻った問題を置く必要はないし、変なストーリーを入れて読解に時間を掛けさせるのも本質ではないので、こんな感じの出題をしました。


DistinguishableSet(Div2 Med, Div1 Med)

概要:

N人にM問のアンケートに回答してもらった時、M問の部分集合であり、N人のその集合に対する回答が全て異なるようなものはいくつあるか

(Div2版はN<=50, M<=10で、Div1版はN<=1000, M<=20)


コメント:

もし問題の部分集合2^M個すべてに対して、回答がN人みな違うかチェックしていいなら簡単です。それがDiv2 Medです。

Div1 Medでそれをやるとどう実装しても通らないはずで、もし通ったら定数倍最適化の†天才†です。

ここで余事象の発想で、「ある2人がいて、回答が一致する」(<=>「全て異なる」)ような集合をカウントすることにすれば、

「N人のうち2人の組み合わせを取って、その2人の回答が一致する問題の集合にフラグを立て、最後に各集合からその部分集合にフラグを伝搬する」

という解法にたどりつけると思います。実装は無なので完全なる一発ゲーです。

このセットでは一番気に入っている問題で、「アキネーターってどう実装されてるのかな?」って疑問を持った時に出来ました。


UpDownNess(Div2 Hard)

概要:

長さNの順列で、P[i] < P[j] > P[k]なる(i,j,k)の組がK個あるようなものは何通り?


コメント:

DPは左から順に見るもの」みたいな固定観念があると全く解けません。(少なくとも今までどの数字を使ったのか?を覚えていないといけないため)

「順列の問題は小さい順/大きい順 に挿入して考えるとよい」っていう典型発想があれば瞬殺です。

完全に教育的問題なので、このスロットに置きましたが、普通にガンガン通されてびっくりしました。


TrySail(Div1 Easy)

概要:

非負整数の集合を3つに分け(空集合はダメ)、各々の集合に含まれる整数のxorを取り、その総和を最大化してください


コメント:

dp[i][a][b][c][mask] = (i番目まで見て、各々のxorがここまでa,b,cで、3つの集合が空集合かどうかはmaskにエンコードされている という状況はあり得るか)

というのがノータイムで出てくると思います。

これだと落ちるんですが、冷静に考えるとi,a,bからcは一意に定まるので、一つオーダーが落ちてこれで通ります。

実は、空集合はダメ、と言っているんですが冷静に考えると (a xor b) <= a+b なので、これは無視しても大丈夫です。(無視すると上の落ちる解が通ってしまったようです)(悲しいね)

流石に競技プログラミングが下手すぎると思う......


SRMDiv0Easy(Div1 Hard)

概要:

初めすべて0の配列に区間加算クエリを何回か行います。加算した値は[L_i,R_i]のどれかであることが分かっています。

このとき、最終的に得られた配列は全要素が等しかった。こういうことがあり得るか、あり得るならその値として考えられるものの最大値を求めよ


コメント:

パッと見めっちゃ難しそうじゃないですか?僕はそう思います(てへぺろ)

配列の差分を取るとフロー(最小流量制約つき最大流)になるので、蟻本に小さく書かれているアルゴリズムを実装すると通ります。

この問題は、「なんか数列の差分を取ってうまく解ける問題作れないかな~」って考えていたら区間加算クエリがフローに対応することに気づいて出来ました。正直トプランの方々には秒で見抜かれていた気がします。






















あとがき

多くの人にとって、役に立ったり参考になる記事ではないと思いますが、競技プログラミングの1つの側面として興味を持って頂けたら幸いです。

来年はアルゴリズムの話ができるよう早めに準備をします。

2017-12-31

2017年まとめ & 2018年目標 23:40

今年を凄く簡単にまとめたいと思います。


1月~3月

基本的に2月末までは受験勉強をした。

センターと2次はどちらも大きなやらかしはなく無事に終わり、東京大学理科3類に入学した。

APMOを受験し、10位で3回目の入賞をした。

3月には情報オリンピックの春合宿でチューターをさせてもらった。

長らく大学受験のせいで心の底から呑気に過ごせる時間がなかったのでこの時期は楽しかった。


4月~8月前半

入学する。何をしようか考え、とりあえず色々やろうということで、

  • 東大特進のスタッフ
  • ボート
  • 水泳

を始めた。

最初のうちは授業もぼちぼち受けていたが意味を感じられなくなったので次第に行かなくなる。(は?)

5月の頭に、地元で行われたプログラミングの大会の副賞でアメリカ(西海岸)に連れて行ってもらう。

7月にはICPCの国内予選があり、Isplpl (僕、yokozuna57、namonakiaccount)で出場して3位を取った。

そして、7月中旬 ~ 8月上旬の間には東医体の新人戦に向けて週6でボートを漕いでいた。

(試験勉強で2h睡眠 -> テスト6時間 -> 夕方3乗艇の日は本当に死ぬかと思った)

結果は4位でしたが、真面目にスポーツに打ち込むこととはどういうことかが分かり、良かったです。


8月後半~12月

東医体が終わったところで大きくやることを変え、

  • 競プロ
  • 研究室

を始めた(再開した)。

競プロはAtCoderの問題がたくさん残っていたのでそれをひたすら埋め、研究室では病理画像をDeep Learningで分析するやつをやることになりました。

競プロは真面目にやったこともあり、すぐRedCoderに戻れ、さらにコドフェスで9位を取ったり、ICPCアジアでSeoul NUに勝って2位を取れたりしました。(最高)

研究室では今コンテストに向けて方針を考えたりコードを書いたりしているところです。


2018年の目標

以上のことを踏まえ、以下のように目標を据えます:

  • SRM, CF レート 2700
  • AtCoder レート 3200
  • 国内予選かアジア地区どちらかで優勝する
  • 研究室でまともな結果を残す
  • Deep Learning系で何かいいインターンを探してやる
  • 生活リズムをまともにして授業に出る

基本的にやるべきことは最低限に、やりたいことをやりたいだけやっていこうと思います。


来年も1年がんばるぞい!

2017-12-17

ICPC アジア地区予選 つくば大会 2017 03:11

12/16 (1日目)

7:30に起きてつくばに向かう。自分らしからず(?)かなり余裕を持ってつく。

JAXAの見学をして、namonakiaccountを待って、会場入りしてプラクティスをする。


人生で一度も触れたことがないのである程度覚悟はしていたが、あまりに英字キーボードが打ちづらすぎるのでチーム内でアメリカへの殺意を生やした。


懇親会でひたすらめしを食って、適当にチーム紹介をして、yokozunaとホテルに向かう。

ホテルでは大浴場の風呂がプールになっていること以外トラブルはなく、生活リズム破滅太郎にも拘わらず日付が変わる前に入眠成功した。

(ちなみに日付が変わる前に入眠したのと翌日忙しかったのとあり人生3回目のデレステログイン忘れ太郎をした)


12/17 (2日目)

8:00に起きて会場に向かう。今日は自分らしく余裕が全くない会場入りだったが、namonakiがTLEしたので全チーム内最下位の会場入りをした。コンテスト順位と会場入り順位の差で天下を取れるレベル。

まもなくコンテストが始まる。


まずnamonakiがテンプレをうち、自分がAをやる。しかし何故かバグらせ(は???????)、namonakiと交代する。

書き直したらなぜかサンプルがあったので出して、Aを通す。(マジでごめんなさい)

まもなくnamonakiがBを通し、自分がCを通す。

DEFGHIJKについては、yokozunaがEを書き始め、FとKは簡単そう、Dは明らかにやばそう、Gはできそう、HIJはよくわからない、という感じになる。

Eが通り、namonakiがGを書き始める。

yokozunaとIを考え、結構解かれてるしギャグなのかなーって言っていたら本当にギャグでキレる。

WAが出たので一旦交代し、yokozunaがIを、自分がFを書いて通す。Gもすぐにバグが見つかり通る。

ここで残りが難しいDHJKになり、取りあえず書けるDをnamonakiが書き始めて残りをyokozunaと考える。

Hはかなり理解不能、Jはやばい(まぁ誤読してたからなんですけど)、Kは解法が分かっているので実装の仕方を考える。

実はKはlcaを考えるだけで良い(それはそうすぎる)ことが分かるので、途中でnamonakiからパソコンを奪ってKを通す。

Jを捨て、Hに全力投入すると、なんか正しそう、かつO(N^3)のDPが生えるので、yokozunaと2人で実装したりデバッグしたりして残り5分で通る。

かなりテンションが上がってハイタッチをする。チーム戦....最高やな!


コンテスト終了し、おそらく2位か3位だけど見える範囲にいたmolamolaの最後の提出への反応が芳しくなかったのでこれは???という気持ちになる。

そして、この直後ホールで統計情報が明かされてしまい9完:1チームで2位が分かってしまう。ウケる。

Jはチームで揃って誤読してた(大反省)、Dは幾何力的に仕方なし、Hはなんで通ったの?って感じだった。


最後に企業ブースが乱立する中での懇親会になりひたすらめしを食い (こいついっつもひたすら飯食ってんな)、適当に交流する。

PFNのブースでiwiさん、wataさんに熱烈な企業紹介をしてもらい、さらに蟻本にサインを書いていただいた。やったぜ。


つくば->駒場->前橋と移動して帰宅。このチームはこれで最後な可能性があるけど結構バランス良かったし良いチームでした。

来年は交流力と英語力と実装力と頭を備えて参加できるよう頑張ります~~~

KOMABA FESTIVAL & CODE FESTIVAL 2017 02:26

ICPCアジア地区予選の前にこちらを書きます (1ヶ月前なんですけどね)


11/23 (駒場祭0日目)

夕方に東京に行き、大学同期4人で飯を食い、翌日早くに用事がある1人を家に泊める。

夜中に起きて、デレマス4th SSA 1日目のBDの鑑賞会をしてブチ上がる。(Radio Happyは最高)(HoMoは3rdの方が好きかなぁ)


11/24 (駒場祭1日目)

昼から高校同期と食堂で喋ったり駒場祭を周って楽しんだりする。

夕方にいつもの勢で家でまったりした後、渋谷のサイゼでいつもの会をやって無限に騒ぐ。最高。


11/25 (コドフェス1日目)

朝遅く起きて秋葉原に行く。結構すぐにコンテストが始まる。


ABを爆速で通したあと、CとDで無限にバグを生やして人生終了する。

Cはすぐに直るが、Dは嘘解法を無限に投げてしまい嫌な気持ちになる。

いったん辞めてEFGを一通り読むと、Gが一瞬で分かったので書いて通す。

Fは昔このような概念を見たことがあったので、何となくやることは分かるが細部がわからんなぁ、となって飛ばす。

Eも昔こんな感じの問題を出したことがあるのでそんな感じで解けるな、と確信したが、細かい部分が詰まらず実装に入れなかった。

EとFを並列して細部を詰めていくと、Fが分かって通し、するとすぐにEが分かったので頑張って実装して通る。

ここでDに戻ると、貪欲の後にdpをしないといけないことに気づき (は?)、dpを書いて通す。

凍結前で10位だったのでこれは1桁順位ワンチャンか??みたいな気持ちになる。


ほどなくコンテストが終わり、結果発表があり全体9位国内2位でした。明らかに出来すぎ。

(HIJはほとんど思考できませんでしたが、どの問題も、強いて言うならIがめっちゃ好きです。)


コンテスト後はそこらに生えているおいしいめしを食べ、解説を聞いたりいつもの勢で絵ウルフをしたりする。

国内3位以内に入ったのでDEGwerさんとhogloidさんとエキシビションに出て、1時間頭を抱える担当をしました。

海外チーム(tourist, Um_nik, ksun)(敬称略)が全完していて流石に天才すぎた。


ホテルに向かい、即座に寝落ちする。


11/26 (コドフェス2日目)

朝早く起きたがゆっくりしすぎてタクシーを捕まえて会場に向かうことになった。


朝はトーナメントがあり、1-16位グループにぶち込まれてかなり困惑したが、早解きなので意外と戦えた。(R2で嘘解法に粘着して落ちた)


rngさんのクイズ大会がかなり面白かった。


最後にチームリレーがあり、Shikさん、Reynaさん、ポテチ、reewさん、dnkさん、beetさん、btkさん、hamkoさん、suibakaさんと同じチームになる。

H担当になり、解法で大嘘をつき、終了間際にShikさんに冷静に解法を教えてもらうたのしいたのしいちーむせんでした。(死)


こんな感じです。(1ヶ月前なのでかなり記憶が曖昧)

駒場祭もそれにかこつけて普段会えない仲良い人と遊べたし、コドフェスは純粋に楽しかっただけではなくコンテスト本番でめっちゃいい成績だったのですごく満足でした。リクルートさん是非とも来年もよろしくお願いします。

2017-10-29

Codeforces Round #443 Div1 01:46

参加してないんですが、ACDEをupsolvingしました。最近のこどふぉらしからず(?)(B以外)どれも結構面白かったので書きます。









A

問題概要

N(<=5*10^5)回、0以上1023以下の値をAND,XOR,ORする。これと等価な操作を5回以内の0以上1023以下の値をAND,XOR,ORすることで作れ。



解法

はじめのi番目のbit(0<=i<10)が0,1だった時、操作を終えた時どうなっているかを見る。

0,1 -> 0,0となっているものは0とのANDで、0,1 -> 1,0となっているものは1とのXORで、0,1 -> 1,1となっているものは1とのORで作れるので実は必ず3回で出来る。O(N)







C

問題概要

N(<=5*10^4)人の人にK(<=10)種類のパラメーターが定まっている。

「ある2人があるパラメーターの値で競い、小さい方が敗北し、消える」

という操作を繰り返す時、1....i番目(1<=i<=N)の人に対して最後の1人になり得る人の数を求めよ。



解法

人i -> 人j iff 人iは人jに勝るパラメーターがある

として有向グラフを作る。

このとき、このグラフをSCCすると任意の2人に対し双方向、あるいは一方向の辺が貼られているのでクリークになり、

かつ全順序が定まっていることが分かる。

よって、一人ずつ追加していくと

どこかに挿入される or 連続した部分列と新規の人が一つの強連結成分になる

が起こるので、setで持って列を管理すると解ける。 O(NK log NK)





D

問題概要

K(<=12)匹の生き物が居て、N(<=10^5)種類のパラメーターが定まっている。

Q(<=10^5)個のクエリが来るので処理してください。クエリは以下の3種類:

  1. ある2匹の生き物から全部のパラメーターが2匹の対応するパラメーターのmaxになる生き物を作る
  2. ある2匹の生き物から全部のパラメーターが2匹の対応するパラメーターのminになる生き物を作る
  3. ある生き物のあるパラメーターの値を出力する



解法

2乗を1/64パワーでゴリ押す解法をしたくなるが我慢して考えると、これを思い出す。

2分探索をすることを考えると、値がmid以上 -> 1 otherwise -> 0と変換して、同じ操作をし0か1を見る、ということをすればよいとわかる。

ここで、考えられる0と1のパターンは2^K通りしかないので、2^K通りすべてに対してクエリの順番に操作を行っておくと解ける。O(2^K * Q)






E

問題概要

長さN(<=10^5)の数列aが与えられる。Q(<=10^5)個のクエリに答えよ。クエリの形式は以下の通り:

L,R(1<=L<=R<=N)が与えられるのでa[L..R]に対し

「隣接する2要素を選び(x,yとする)、削除してx+2yをその場所に追加する」

ということを要素が1つになるまで繰り返すとき、最後の値の最大値をmod 10^9+7で求めよ。



解法

2^b_i * a_iの形の値の和になることは明らかで、b_iの条件を考えると

  1. b_L = 0
  2. 1<=b_i<=b_(i-1)+1(L<i<=R)</li>

となりそうなことが手を動かすとわかる(未証明)ので、

以下この問題を解く。

b_iをb_(i-1)+1にしない時のことを考えると、明らかに1にするしかないことが分かる。(中途半端な値を取るメリットはないため)

よって、b_iは0,1,2,...,x,1,2,...,y,1,2,...z,...のような階段を繰り返す感じが最適とわかる。

どこで区切るべきかを考えると、

後ろから見たときに負になったところで切るべきで、逆に負になったところで切らないのは最適ではないことが分かるから、

c_i = a_1 + 2 * a_2 + ....+ 2^(i-1) * a_i

とすると、Xが右端の階段は

c_Wはc_Xよりも大きく、かつそのようなWの中で一番右の値(Yとする)が左端になることが分かる。(ないときはL)

よって、c_iをソートし、ダブリングをすると解ける。 O((N+Q) log N)くらい?

2017-09-15

みんなのプロコン本選 E - 瞬間移動装置 02:09

本番ぶりに考察したら割とすんなり思いついた、良問です

問題概要

N(<=10^5)頂点のクリークからM(<=10^5)本の辺を取り除いたグラフにおいて、頂点cから頂点dに行く時の最短経路をQ(<=10^5)組求めよ。











解法

本質は、次数がN/2以上の頂点同士を選んだ場合答は1か2であることに気づくことです。(そそ)

そして、次数がN/2未満 <=> 補グラフでの次数がN/2より大 よりそのような頂点は高々2*M/(N/2) = 4*M/Nしかなく、

4*M/N <= 2*Nが成り立つのでNの値で場合分けするとそのような頂点は高々1000個くらいしかないことがわかる。

ということは次数がN/2未満の頂点からO(N+M)でBFSして答を前計算してやれば良いとわかる。

BFSのやり方は、バケツソートのような感じで距離が0,1,2....の順に見ていき

「距離Dの頂点全てに対し取り除かれた辺でつながっている頂点に+1した後、未処理の頂点をすべて舐めて今までの加算回数(=距離D以下の頂点の個数)と頂点の値が等しくないなら距離D+1として決定する」

という処理を行えばよい。(未処理の頂点をすべて舐めて良いのは、距離D+1にならない頂点を見る回数は合計で高々O(M)回、距離D+1になる頂点を見る回数は合計で高々O(N)回なので)

以上を実装すると、計算量O(sqrt(M) * (N+M))で通る。