WA_TLE’s diary

競プロたのしい!

PCK2018よせん解説

解説を!!!するぞ!!! 難易度よそう 1?2?3<<4<<6<5,7,8<9,11<10<<<<<<(エアーズロック3個分)<<<<12

1~3本当にみてない。まあ適当にやって。

ではひどいので、相方が解説を書いてくれました。ありがとう!🙂http://kubokubokun.hatenablog.com/entry/2018/09/20/151529

4 ボトルを買うやつ

if文を頑張るのだが、工夫すると単純でバグりにくい。
変数名確認、aが1Lの値段、,bが500mLの値段、xミリリットル必要 だよね、解法はこうなる
x= (x+499)/500; //500で割って繰り上げしている
a=min(a,b *2); //これでa一本よりb二本が安いなら自動的にそうしている
if(x%2==0){cout<<a * (x/2) <<endl;}//端数がない
else{cout<<a*(x/2)+b<<endl;}//B端数がある

5 でぅーどにー数

解は ,ある自然数zに対し、zのn乗の形になるので、zを全探索。するとO( 108 のn乗根 * 桁和を求めるlog ) なので、2<=nの条件により高速に解ける

6 ぼぞそーと

ソート済みの配列といくつ一致しているか持っておいて、それがnになったときがこたえ。

7 ワープ装置

星に入るのか装置に入るのかでinとoutがこんがりませんか?
各文字cについて、それまでcに入るのが何通り?でdp。典型。

8 たくしー

条件を整理すると、こうなる
乗せる客を選ぶ。ただし各i 1<=i<=nに対して、i番目以下の乗り場の合計には、i人以下しか載せられない。
この条件に変形したら、優先キューで低い人を自明においだすだけ。

9 直線状の点

これなぜか苦労した。点を固定して、同じ傾きを通る点がほかにK-1個ありますか?を既約分数とunordered_mapで確認した。
n<=3000で、O(n2)でunordered_map,こわくないですか?こわいね(一応5秒ぐらいあったはず).

10 ダンジョン2

ダンジョン2、JOIにも全く同じ問題名がある。問題になりすぎでは?
とりあえず通った場所は部分木、辺を通った回数は、それがスタートとゴールの間のパスなら1度、else 2度
それを変形をして、スコア=Σ(各部屋のスコア-2) + スタートtoゴールのパスの長さ +2にする。

解法 木dpをする。dp[a]=aの部分木でスタートとゴールが木の子の中にない
ep[a]=スタートゴールのパスの片方だけが子に含まれる場合の、dp[a]に対するスコアのボーナス
fp[a]=スタートゴールのパスの両方が子に含まれる場合の、dp[a]に対するスコアのボーナス
さいしょの提出ではfpがなくて、WAした。 おばか。(当社比)

11 円盤

操作がセグ木に乗ります。ではあまりにひどいので解説します。
まず見ると、flipした状態では通常に比べて操作が反対向きになる。
よって、struct sousa{bool flip;long long int rota;};を考える、flipはそのままの意味、rotaはその数だけ回転するということ。
ただし、回転させてからflipをすることにする。
すると、sousa L,R,X;があって、XにはLをしてからR を乗せるとする。すると
X.flip= L.flip ^ R.flip;
if(L.flip){X.rota= L.rota+R.rota;}else{X.rota=L.rota-R.rota;}
とすると、操作の合成ができる。これをセグ木に乗せて、出てきたものを適当に円盤の場所に対応させて完成。

12

PCKにおいて、予選最後にHL分解がくるの、去年もだった。
実装が重すぎて50分ではとてもとけない。さよなら~

PCK2018よせん参加記

パソコン甲子園に、相方@kubo_programer と一緒に出場しました。
結果は11完2WAでたぶん一位、解凍後もたぶん一位でしょう、解説をしましゅ。

予選開始。7,8,9,10の印刷をする、相方が1から順にとく
123相方がとく。僕は問題をみていない。
このあいだに78の考察終了、10が半分ぐらい
78AC,
4相方がとく、少しデバッグしたけどWAだった、交代この間に9の考察完了
9をとく、不安だったけどAC この間に相方が4のデバッグ終了,5愚直を紙に書いてくれた。
4デバッグAC、5をみるとTLEしそうなので、少しヒントだす
10をぼくがとく、WAする 5,6,11,12が残ってて時間がのこり半分?だったので、相方にパソコンを譲らずに、printfデバッグした。(チーム戦とは?)そしたら
ぼくのdpが少し足りないことに気づいて、実装&AC
5早い解を相方が実装、AC
6,相方ができるか微妙だったので、僕がやった、AC
11をがんばった、AC 12できなかった、むずかしすぎる

終了,11完2WA🎖

IOI2018の参加記になるもの

前日の壮行会 壮行会というものの、おおきなイベントではなかった。NTTの人以外スポンサーもいなかった。

晩御飯も、普通にお弁当だった。

なんかIOIの諸注意とか説明とかがあった。コンテスト前日は不正を防ぐためネット禁止らしい。きびしい。

そのあと、いろんなIOI過去問の解説があった。去年はここで解説していたものの類題がでたらしい。だから重要なのだが、ぼくはすでにAC済みの解説だったため、違う問題の実装をずっとしていた。結局バグらせて、解けなかった。

friction penは日本にしかないらしくて、それを外国の選手へのお土産にするために、8人に30本ずつもらった。

IOIのTシャツのサイズが、小さいのしかなくて困ったりした。まあMサイズなのでなんとかなるけど。

ペンとTシャツでかばんが大変なことになった。持ち運びが非常につらい。

1にちめ

だいたいが昼食と説明と自由時間だった。

特筆すべき事項はとくになかったが、海外選手と少しはなした。

2にちめ

朝ごはんをたべた、おいしい

ごはん(白飯)の存在に気が付かなかったので、炭水化物ぬきで、昼食まで力がでなかった、反省

平木さんが寝坊していた、3日目と5日めはそれぞれが互いに起こすことにした。

記者会見があった。テレビカメラに取材されるのは初めてで、とてもわくわくした。

あと茨城県知事との会談(?)があった、193さんが所属している、N高を作った人だそうだ。193さんとたくさん話していた。

僕は高専生なので、ドワンゴの基準だと「中高生」ではありません というジョーク(文句?)をいった。 参考: http://dwango.co.jp/saiyo/dwacon2018/ 荷物をまとめた後、開会式があった。

「見ることすなわち支配すること」という有名な格言があるが、(去年の👑高谷さんの5日目?の感想を参照) しかし僕の場合、IAのライブを見ることによって、逆に心を支配されてしまった。やはり僕は師匠みたいになれない。

そのあと実行委員や佳子さまのコメントがあったあと、各国の紹介があった。なんかてきとうにした。

昼ごはんをたべたあと、佳子様への 謁見があった。

さすがにこれはとても緊張した。見ての通りぼくは敬語が全く分からないので、失礼のないようにふるまうのがとくに大変だった。

佳子様に、「IOIの前日で緊張しますか?」と聞かれたが、正直に言って今の方が緊張している。

あまりにも緊張しすぎてつま先が動かなくなったため、終わったあと、空いているスペースを走った。

精神力を使い果たしたところで、practiceがあった。40分ぐらい謎の遅延をしていた、実質📊CodeForces この時に本番で必要なものを持ち込むのだが、まさかマウスが準備されていないとは思わなかったため、宿舎に置いてきてしまった。でもパッドでの操作がなんとかできるため、なんとかした。

US配列のキーボードもあまりなれなかった。記号が大変。いろいろ全然ちがう。

双子がpracticeでとても強くて、Japanチームこの調子で大丈夫ですか?と煽っていた。ぼくはこのときは「まあpracticeだし、Japan2がJapanを超えることはないだろう」と思っていた、まさか...

ご飯をたべた、普通

なんかネットから隔離された、ネットできないのきつい。

free timeではセグウェイに乗った、実質segment うぇ~い(意味不明)

あと、海外選手と会話をした。

明日にそなえて10時ごろに寝た。

3にちめ 起床

12:00に目が覚めた、寝た。

3にちめ 起床

2時だった。寝た。

3にちめ 起床

目が覚めたら4:40だった。寝た。

3にちめ 起床

こんどこそまともな時間(6:30)に起きた。

バスに乗って、会場に向かった。

不正なものを持ち込んでいないかのチェックと、トイレに時間がかかり、40分遅延した。📊CodeForeces!(フラグ) バナナと水が支給された。コンテスト終わるの14:40だし、大変だからね。

途中でパック入りのエネルギー補給ゼリーも支給された。ここからは問題のいろいろを書く。

問題の解法のネタバレを含みます。

コンテストDay1開始 まず問題を見た。いろいろ考えた。

僕は先に並列に考察をしてから、いきなり💯満点を実装するスタイルなので、実装し始めは遅い。

まずComboがわかったので、解いた。自明なので説明パス。

つぎに🐺人狼🐺を考えて、解けた。

僕の方針は、人状態で行ける場所を、新しい番号付けで区間になるように、新しい番号をつける。

そして、🐺狼🐺に変身してから逆にたどるのは、新しい番号をもってマージテクした。計算量はO(nlog2n)ぐらい。

そして余った2時間半、seatsの💯満点💯を考えた、順位表を知っている現在から考えるとこれはbad choiceで、部分点をやるべきだった。

のこり1時間40分で、まず部分点のうち、17点分の解法を実装したが、しょうもないところでバグらせてしまって、ACしたのは終了40分前だった。のこりの40分で、20点分の!実装を!!できませんでした~~~🍗

コンテスト終了 なんかコドフォ世界7位のBenqさんが圧倒的な強さを見せていた。やっぱり📊こーどふぉーせず!

僕は11位で、メダル圏内で安心した。

でもほぼ同点みたいな人が多すぎて、実質てきにはなにも決まっていない。

平木くんと双子も強くて、Day1終了時点で、japan1と2の転倒数が10という異常事態だった。春合宿とはいったい何だったのか?

忘れずにマウスを預けた。これでDay2ではマウスを使えます。

ちょくだいさんとやっと会えた。🐺人狼🐺の解説をした。

解析の時間中に、双子がデバッグをして精進していた。ぷろ!

晩御飯を食べた後、双子といろいろ話した。

comboは、文字列の長さを4Nではなく3Nにしても、解ける。しかも、クエリ回数をN*0.714+定数 ぐらいまで減らせることが分かった。

海外選手もroomに入ってきて、combo N*0.714の解説をした。

僕が英語下手すぎて、たまに if answer is K plus iti, next char is X.みたいな日本語が出てしまったが、何とか意味は伝わった様子。良かった。

しかし、リスニングはかなり苦手で、双子に何言ってるかところどころ訪ねた。僕の英語力がなさすぎる

ぼくは来年団長として、アゼルバイジャンに行きたいとすこし思っていたが、この英語力だと誤訳をして、

日本選手「なにやってんだよ!団長!団長!!!」 ぼく「う、うわああああああ」 ♪フリージア

になりかねないので、諦めた。

4にちめ

あさ、雷がなった。こわかった><

JAXAにいった。カメラマンがフラッシュをたいて、それ雷だと思い込んで、WA_TLEさんが怖がっていた。

地学のところと、サイエンスsquareに行った。楽しかった。

江戸の映画の撮影セットにも行ったが、それはぼくたちにとってはあまりおもしろくなかった。ごめんね。

とくに書くことがないなあ。

5にちめ

コンテストに向かった。ほぼすべてネタバレです。

まず問題を見た。いろいろ考えた。

僕は先に並列に考察をしてから、いきなり💯満点を実装するスタイルなので、実装し始めは遅い。

まずdollがわかったので、解いた。自明なので説明パス。

つぎにhaiway、解けた。と思っていた。

実装して提出すると、51点が返ってきた。そして、自分の愚かさに気づいた。これは一般には成立しない。

仕方がないので、meetingを考察した。

JOI2017春ralway tripに似ているので、ダブリングを疑った。

しかし、ダブリングの前計算がうまくいかないことに気づいた。Convex fullを持たせればワンチャンあるが、N=750000とかでO(nlog2n)は通らないと思った。

ダブリングはできないけど、60点なら通るので、実装をした。

しかし、なぜか不要な部分で二乗をしてしまっていて、17点しか取れなかった。残り25分。

何とかバグを見つけて、残り1分半のところ(提出は2分半前)で60点まで伸ばた。ものすごくうれしくて挙動不審になっていた。

コンテスト終了

まず順位表を確認すると6位だった、情報オリンピックの地球特別選手団に滑り込んだことが分かった。。(は?)(DEGwerさんの文を参照)

金メダルが取れてとてもうれしかった。

6にちめ

この日はエクスカーションに参加した.

大洗市までかなり距離があったため、バスの中で眠った。

午前1は神社にいった。コンテスト終了後に神様に金メダルのお礼を言った。お賽銭の金額は、2日間の合計得点円にした。

午前2はイルカショーであった。解説がすべて日本語であったため,何をやっているのか完全に理解できた。(高谷選手 day4)

お昼にお弁当を食べたが、僕はあまりおなかがすかない人間なので、半分ぐらいしか食べられなかった。

しかし、次の予定は公園なので、そこでたべることにした。

公園はとても広くて、十分に疲れた。また、昼ご飯を食べていたら、チームが二分割されてしまった。

公園と言いながら、さびれた遊園地も存在して、ジェットコースターや観覧車があった.(要追加料金)乗らなかった。
あと、無料のアスレチックがあった。途中で先のチームもここの先で合流できることに気づいて安心した。これがかなりあれで、障害物のある長いチューブの中を進んでいくのだが、そもそも僕たちには小さすぎる、障害物が半分ぐらい壊れている、途中で脱出するための滑り台まで壊れている。

仕上げに、なんか4階建てのタワーが遊具としてあった。KMcodeさんに「上には何があると思いますか?」と聞かれ、特に何もないと思って、

「遊園地のマスコットキャラクター」(そういうところにはマスコットがあることが多い)と答えたのだが、頂上には本当になにもなかった。絵すらなかった。

虚無な実装をしたうえに、📊This contest will be unrated.になったような気持ちになった。

帰りのバスの中でも寝た。睡眠不足は自明だ。

7にちめ

3日分の日記を書いていたら、日付をまたいだ。おやすみ~🐑

2度寝したら、9時だった。(1WA)

朝ごはんも食べずにバスに向かったが、参加者IDを忘れてしまって、部屋に取りに帰った。(2WA)

さらに9:20分発のバスに乗る予定が、間違って9:40発のバスに乗ってしまった。(3WA)

その結果、僕が国際会議場に着いた時には、楽しみにしていたIAのライブ映像鑑賞会が半分以上終わってしまっていた。

おそらくこれは、僕のIOIの中で、最大の失敗といえるだろう、いや、それどころか、3つの原因を分割してカウントすると、僕のIOIの失敗top3に全部入るだろう。
((心の中の👼天使の声)それはcontestantとして、正しい態度か?2時間半あって17点のseatsを反省しろ!)(👿悪魔:でも結局メダルの色変わんないし、seats100とらないとAWにはならなくない?)

あと、だれとは言わないけど、マスコットを投げ上げてたら天井に載ってしまった人がいた。🍎結局取れたけど、会場スタッフに怒られてたらしい。

さよならパーティがあった。ぼくはおみやげのペンを忘れたけど、名刺と折り紙とふせんのセットを60個用意していた。母が気合を入れて折り紙を折っていたが、どう考えても多い。
でも、根性でグループに話しかける->渡す->たまに写真をとるを繰り返したら、何とか配り終えた。ペンは後述
あとは、ボランティアスタッフの競プロerと雑談をしていた。

翌日のチェックアウトが早いので、早く寝た。

8にちめ

AtKatazuker rating 50の灰色かたずけerなので、部屋が大変なことになっていた。
とりあえず全てをかばんやスーツケースに詰め込んで、チェックアウトをした。
チェックアウトの列が形成されていたので、空きホワイトボードに、This is present for you.take free !とかいろいろ書いて、ペンを置いたら、お土産を渡せた。

バスに乗り込んだが、Kmcodeくんが時間を勘違いしていて、いなかった。
つくばのホテルのロビーでKmcodeくんの到着を待って、それから解散した。
僕は解散した後、つくばで親戚にあったりしたが、その詳細はIOIでは書かない。よって日記はこれで終わり。

夏季セミの合宿

1日目 本を選ぶ段階
gotoloopさんが、「型システムは一直線に実装できる」と言ってたので、ぼくは型システムの本を選んだ。
不人気だった。もやし先輩がじゃんけんにまけて、こっちに来てくれたのでうれしかった
いろいろよんだり、構文解析の実装をした。
宿泊棟?についた。階段がたがたツリーハウスみたいな感じだった。面白いけど、足がこわれそう
ご飯は全体的においしいけど、特に書くことがない。
ボドゲがとても面白かった。全体的に夏季セミで一番楽しいのはボドゲだと思う。

2日目
実装をした。この段階で形無しラムダ演算ができるようになっていたはず。
機械学習の講演がとても面白かった。
ボドゲが本当に面白い。

3日目
実装をした。int型をつけたり、永続化したりした。
この地点で、発表の方針を固めた。競プロ用の動的型付け関数型言語のインタプリンタつくるぞ!

4日目
量子コンピューターや新概念コンピューティングの講演があった。面白かった。
ついでに新概念1の問題を、bit数 20*n3 があればCMOSで解けることをはなした。とても興味を持ってくれた。これはてなブログに書こうとしてそのまま半年たったやつだ...
実装をした。組み込み配列型を作ったり、入出力ができるようになった。
競プロができるようになっているので、そのままABC106(双子回)にチャレンジした。
結果は3完だった。D問題は言語そのものにバグがあって、サンプルで苦しんでいた。
終了後にサンプルは解いたが、n<=500,m<=100000,Q<=100000でO(n2+m+Q)がTLEした。関数型インタプリンタだし、配列のアクセスがlogだし、仕方ないとも思う。
双子による非公式解説放送があった。D問題で少しだけ良い方法を提案した。(本人が通せてないのに!?) 結果的にぼくも動画デビューを果たした。
もやし先輩が公式の方に乗り込んで宣伝していた。あとで少しだけ怒られてた。
この地点でスライド0枚。4時ごろまで作業をした。

5日目
スライドを発表した。とてもたのしかった。
異世界に転生したら手続き型言語が通じなかった - Speaker Deck

E869120さんのスライドの声量がすごかった。圧倒された。
さいごに少しだけワードバスケット というゲームをして、帰った。
帰りになんにんかとカラオケにいった。新しいボドゲもした。
ぼくのカラオケが下手すぎることに気づいた。まず音程が全く取れてない。さよなら~🐥
飛行機があるので早めに帰った。飛行機にはギリギリまにあった。

MM100 かいほう

13位。1552->1777(+225) highest! 1777なので実質うま(伝われ)(ei1333パロディ) (ei語の機械翻訳を適当に調整したものです)(普通逆でしょ) 私は sumirated anneling によって解決しました。しかし、それは温度が固定されます。

私は空の最初のポイントを選択します。

その四角形に他のカラーポイントない、2番目のポイントをリストアップします。 !!!2番目の点は、消去された点かもしれません。!!! 2点目が消された点場合、私はポイントのペアをキャンセルします。 私はペアをキャンセルした場合、私はペアが消去された必要がある他のペアをキャンセルする必要があります。 私はあまりにも多くのペアをキャンセルする必要がある場合、私はステップを実行しません。

このアルゴリズムはアニーリングの1段階です。 私のアルゴリズムは多点開始アニーリング法です。

「No.647 明太子 」 を無駄にセグ木を使って早くする解説

タイトル名が雑でごめんなさい。 解説の書き方が良くわかりません。(今まで参加記しか書いてこなかった)

問題: No.647 明太子 - yukicoder

僕の愚直解法: #234780 No.647 明太子 - yukicoder

僕のセグ木解法: #235796 No.647 明太子 - yukicoder

想定解は,O(NM)ですが、セグ木を用いるとO( (n+m) log(n+m) )になります。 まず、入力を受け取って、辛さを座圧します。 そして、人と明太子を並べて、値段(と予算)が高い順にソートします。 このとき、それがおなじなら人のほうが先に来るようにします。(同額ならば買うため) そして、辛さを†セグ木†で持ちます。(BITでもいけるけど、ぼくはBITの使い方がわかりません) すると、人が来た時に、要求する辛さを持っておいて、明太子が来た時に、それ以下の辛さを要求する人の人数がその明太子の購入される数になります。 よって、座圧とセグ木に必要な、O( (n+m)log(n+m) )で解けます。 ちなみに、もとの制約が小さい&いろいろさぼったので、愚直と比べて2倍しか早くなりませんでした。 最速コードはほかの人がBITをつかっていました。(僕はbit演算が苦手なのでセグ木を使い、2倍遅い)

まとめ セグ木たのしい!!