AtCoder Beginner Contest 155に参加しました
ABC155のコンテストサイト
atcoder.jp
A問題
問題
数が3つ与えられるので、「ある2つが同じで残り1つがそれらと違う」かどうかを判定する問題。
人間の目で見られれば簡単なのだが、プログラムを組むとなるとちょっと面倒。
10秒ほど方針を悩んだ結果、この条件は3つの数が2種類であることと同値であるという天才的発想に至り、3つの数をsetにぶち込んで無事AC。
B問題
問題
N個の数が与えられて、それら全てが「偶数ならば、3または5で割り切れる」を満たしているか判定する問題。
コードは、N個の数を順番に見ていって条件が満たされなかったらそこで打ち切る方針で書くので、この命題の否定を考える必要がある。
元の命題は「全ての数について『奇数 または 3の倍数 または 5の倍数』」なので、否定は「ある数について『偶数 かつ 3の倍数でない かつ 5の倍数でない』」となる。
C問題
問題
文字列の集合S(|S|≦200000)が与えられて、この集合の最頻値を(複数個あるなら辞書順で)求める問題。
文字列の個数についての問題なので、とりあえずmap<string, int>に突っ込んでおく。
提出したコードでは出現回数の最大値とその最大値回出現する文字列を同時に求めているが、先に最大値だけ求めて後から文字列を求めるのでもいいと思う。
D問題
問題
N(≦200000)要素の数列Aが与えられる。この数列の要素の全ペアN(N-1)/2個のそれぞれの積のうち、K番目に小さいものを求める問題。 過去のARCで既出
個人的に大詐称問題、実装難易度も考察難易度も500相当かそれ以上はあると思う。
解法のベースは二分探索で、「ペアの積のうちx以下のものがK個以上であるような最小のx」が求められれば良い。
ペアの積のうちx以下のものは、
⑴ xが0以上の時、「ペアの積が0のもの」「ペアの積が負のもの」は全部数えて、「ペアの積が正のもの」は一個を決めればもう一個の範囲が決まるからにぶたん。
⑵ xが0未満の時、「ペアの積が負のもの」だけ数えればよく、これはさっきと同じように一個を決めればもう一個の範囲が決まるからにぶたん。
にぶたん in にぶたんで計算量にlogが2個かかって怖かったけど、612msで通った。流石C++、爆速。
しゃくとりとか使えばlogが1個落ちるのかもしれないけど、これでも通ったしACは正義ってことで。
E問題
問題
10の累乗円玉のみが使える世界でN(≦101000000)円の商品を買いたい時、支払いに使う小銭とお釣りに使う小銭の合計枚数を最小化する問題。 yukicoderで既出
Nがすっごい大きいので、まず桁DPかなっていうインスピレーションが浮かんだ。
払う金額と貰う金額を計算しながら桁DPをしていくのがよさそうなのだが、ここでセオリー通り桁DPを上の桁から計算していくと繰り下がり計算が面倒になってしまう。
繰り下がりといえば筆算、ということで普段筆算する通りに桁DPを下の桁から計算していくことにすると、上手く行く。
普段の桁DPでは「今見ている数がNより小さいか」というis_lessのような引数を持つが、今回も同じようにis_lessを使えばよい。(提出したコード中ではis_lessの代わりに「今見ている数がN以上か」というis_largeを使っているが)
絶対500点ではないと思う。公式解説が天才だった。脱帽。
このDPは現在の桁(1000000通り)、is_less(2通り)、繰り下がり中かどうか(2通り)の3つの引数持っていて、遷移が0-9の10通りあるので、1000000*2*2*10=4*107通り。
うっひゃーギリギリ、と思ったが、爆速C++さんは206msで通してしまった。余裕しかなかった。
F問題
問題
数直線上にN(≦100000)個の爆弾があり、それぞれがオン/オフのどちらかである。M(≦200000)個のコードがあり、各コードは切られると数直線上のある区間内の爆弾のオンオフを反転する。爆弾を全てオフにできるか反転し、できるならコードの切り方を求めなさい、という問題。 有志コンで既出
とりあえず最大109の座標は扱いづらいので爆弾は位置でソート、コードは座圧して爆弾の区間にする。
区間を反転する問題も扱いづらいので、隣接する爆弾のオンオフのXORを考えると、区間内の爆弾を反転させるという操作はこのXORを2個反転させるということに置き換えられる。
よって、問題は次のように言い換えられる。
・長さN+1のbit列と、1≦x<y≦N+1を満たす整数のペア(x, y)がM個与えられる。
・ペア(x, y)を一つ選び、x番目のbitとy番目のbitを反転させる操作を何回でも行える。
・bit列を0のみにすることができるか。
ここで唐突だが、i番目のbitを頂点iに、(x, y)のペアを頂点xと頂点yを結ぶ辺に対応させ、N+1頂点M辺の(無向)グラフを作る。
頂点iはi番目のbitが1なら黒に、0なら白に塗る。
この時、ある辺の両端の頂点に対応するbitを反転させる操作は、両端の頂点の色を反転させる操作だといえる。(この操作を以降は「辺を反転させる」と呼ぶ。)
ここで、辺を反転させても黒頂点の個数の偶奇は変わらない。なので、黒頂点の個数が奇数であるようなこのグラフの連結成分があった場合、その連結成分内の黒頂点はずっと奇数個のまま。
この場合は即OUTで、-1を出力して解散。
全ての連結成分内の黒頂点の個数が偶数個の場合、連結成分内の辺を上手く反転してあげると連結成分内の全ての頂点の色が白くなる。具体的には、次の手順のように反転する辺を選ぶ。
1. 連結成分の適当な全域木を取る。
2. この木の適当な頂点を根とする。
3. この根付き木の各辺について、根から見てその辺より奥にある黒頂点の個数が奇数ならこの辺を反転し、偶数なら反転しない。
ちなみに未証明で提出したが、提出したらACが返ってきた。ACは証明。
最後に
後半3問がかなり詐称してた気がする。
あと、DもEもFも全部問題傾向がバラバラで面白いセットだった。実装のD、知識応用のE、考察重ねのF。
コンテストの成績は4位だった。これで順位表1ページ目スタンプが1つ埋まり、残りが3, 11, 13, 16, 18, 20位になった。
JJMO'20 予選 時刻表
当時書き残していた時刻の情報をただ書きます。
JJMO'20予選の解答のネタバレを含みます。
12:00くらい：会場についた。暇だったので過去問解いてた。
12:20くらい：同級生がちらほら集まり始めた。過去問解きながら駄弁ってた。
12:40：注意事項が読まれ始めたり、受験票の確認や問題・解答・計算用紙の配布があった。
12:50：試験前の全ての準備が終わり、会場が静寂に包まれた。ここから10分は暇だったのでTrain Fareを脳内で解いてたら5分くらいで解けちゃって残りの5分は本当に暇だった。
13:00：試験開始。まずは問1, 2, 3に取り組んだ。
13:??：問1が解けた。AB=6, AC=6xとおいて式変形し、答えは3/5となった。
13:??：問2が解けた。(b-a+1)(b+a)=4040を解いて、答えは(a, b)=(31, 70)となった。
13:20：問3が解けた。答えは4桁の11の倍数の個数で、⌊10000/11⌋-⌊1000/11⌋=819個となった。
13:32：問6が解けた。121マスあるQを市松に塗って求まる上限の27個が構成可能。
14:17：問8が解けた。場合分けでゴリゴリ列挙して(l, m, n)=(16, 16, 42), (24, 24, 38), (2, 42, 44)となった。
14:40：問7が解けた。Xが各行各列に丁度1個なので4!=24通りとなった。
14:59：問4が解けた。atan(1/2)+atan(1/3)=45°を使って答えは169/20となった。
14:59：既に解いた問題の見直しを始めた。
15:09：問3のアホすぎるミスを見つけて修正。4, 3, 2桁がそれぞれ90, 8, 9個で計107個となった。
15:23：問6を修正。Qのマスの個数を121→117マスに修正したが、何故か答えだけは合っていた。
15:28：見直し終了。
15:49：9が解けた。ダイヤx3つのパターンが16個、外周をぐるっと回るパターンが6個で計22個。
15:49：残りの問題が解けそうに無いので再度軽く見直し。
16:00：試験終了。1-4、6-9の8問が解けた。
後日：8完だという通知が来た。どうやら間違いはなかったらしい。
yukicoder yukicoder April Fool Contest 2019 O - ほぼ直角二等辺三角形 解説2
問題 → https://yukicoder.me/problems/no/3054
https://259-momone.hatenablog.com/entry/2019/04/02/002241 とは違う解法で解いたので書き残しておきます
問題
a²+(a+1)²=c² を変形して (2a+1)²+1=2c²
A=2a+1 とかで置くと A²+1=2c²
2=(A²+1)/c²
√2=√(A²+1)/c≒A/c
√2を2つの整数 (ただしAは奇数) で A/c と近似すればできそう
wikipediaで√2の項目を見ると「連分数展開を途中で止めると近似できる」と書いてある
有限回の連分数展開は再帰をするとできるので、1回だけ展開したのから60回くらいまで展開したのまでとりあえず計算した
出てきた分数が A²+1=2c²を満たすか確認→展開1回の値3/2以外は全部満たした！！！(未証明)
見た感じ1桁から18桁まで揃ってそうだし、cがX桁のものを出力するようにして投げたら通った
JOI2018本選 参加しました
※これは本選問題の考察がどうのこうのについての記事です。本選中の宿泊などの生活については一切触れません。そういった部分は参加記もどきにまとめました。
本選の結果はまだ分かりません。ボーダーも分かりません。なので少し怖いです。
問題
1問目
以前自分がyukicoderで作った集合に分けようという問題と解法がほとんど同じなのでスッと6-7分くらいで満点で解けました。
2問目
重さの最大値と最小値を決めたらその範囲の重さの美術品は選べることに気づくまで数分かかりました。累積和をパッと思いつき、開始30分くらいでO(N^2)を実装して50点を得ました。
開始2時間くらいで最小値を固定して最大値を動かす探索を高速にやればいけそう、と思ったのでセグ木を使って実装したら10点しか取れませんでした。で、開始から3時間55分くらいでバグの理由に気づき、修正して提出したら100点取れました。ギリギリセーフ。
(最小値を左から右ではなく右から左に動かせばこの問題の満点解法にセグ木は必要ない)
3問目
小課題1(愚直全探索)をbitを使って全列挙しました。TLEしました。意味がわからない
4問目
小課題2(経路復元Dijkstra)を解こうとして案の定バグりました。
Dijkstraでバグるのはいつも通り()
5問目
問題は見たけどプログラムには全く触れませんでした。今見たら、愚直にやれば小課題1と小課題2(計12点)は通りそうでした。
高速ゼータ変換とか知らないし
結果
1問目と2問目を満点AC、2完200点でした。
ボーダーは(200, 300]の範囲だと思うので、落ちるのが確定しました。
JOI2018本選 参加記もどき
※この記事は記事を書くのが下手な人が書いたものであり、上手くまとめられていません。長いです。
※この記事を書いた人はどうやら日記のような雰囲気で書いたようです。
家からつくば駅までの経路
経路の途中で秋葉原を通りました。秋葉原では競プロerのグループ(6人位？)と合流できましたが、数分後にはぐれました。合流した方々には申し訳ありませんでした。
つくば駅からつくばカピオ(会場)までの経路
駅の出口を出た後は地図を見ながら進めばいいですね。簡単。
つくばカピオには15:00くらいに着きました。
(5分ぐらい真反対に行ったのは内緒)
つくばカピオに着いてからプラクティス(練習)まで
私と同じく予選を通過した同学校のsicasannに会えました。
16:00くらいまで本を読んで待ちました。以上
プラクティス
入り口の近くでりんごのぬいぐるみを机に置いたガチプロ双子2人を見かけました。
16:00-18:00まではプラクティスでした。プラクティスがコンテスト形式だということを知りませんでした。4問目のIOIOIと5問目のダーツもつっかからずにACできました。
(ターミナルの使い方が分からずに手を上げてスタッフを呼んでコンパイルの仕方を聞いた)
講演
JOI講演ですね。cisco社erからのコンピューターアタック防止云々の講演がありました。
夕食会
19:00から90分はバイキング形式の夕食でした。長いように見えて意外と短いです。一人30秒の自己紹介があるからというのもあります。いなり寿司とパセリをたくさんもらいました。(いなり寿司は12個、パセリは10個くらい)
自己紹介緊張した〜
宿泊会場にバスで移動
バスでの移動自体は10分くらいで終わった感覚でした。バス内でパソコンを開いて競プロをしようとしていたらいつの間にかバスが目的地に着いていて、急いでパソコンをしましました。
「みんなのプロコン 2018」
バスが宿泊施設に着いたら20:57、シングルルーム(通称独房)はWi-Fiが繋がらないのでWi-Fiが繋がるロビーをみんプロerが占領。私も参加しましたが、Wi-Fiを使っている人が多すぎてA問題を解くのに10分掛かりました。
私は22:30に撤退しました。500点問題のCが解けなくてア
2日目、起床AC
5:15に起きました。出かける時間の6:30まで暇だったのでパソコンを使おうとしたらWi-Fiが使える時間帯が7:00からだったので素直にWi-Fiなしでも出来る(オンライン提出はできない)競プロやりました。
2日目、朝食AC
鮭定食うまい
2日目、バスAC
宿泊施設からバスでつくばカピオに戻ります。バスの中で頑張ってLCAを使った木内の頂点の距離を求めるプログラムを完成させました。
いざ、本選！
本選の前に水ペットボトル(500ml)をもらって水分補給しました。
で、本選前に質問票だのメモリ制限だのの説明が色々あり、競技が始まりました。
ここでは本選競技の具体的な話はしません。
そういう話はこっちにあります。
色々あって、競技が終わりました。
はい。
昼食
レストランの中で弁当を食べました。食べている途中で、各問題で得た点数とその合計点数が書かれた紙をもらいました。
解説
プレゼン形式の解説でした。当然ながらはいプロを連発しました。
帰ります
駅の地上の建物内で、プロの方々3人と一緒にたこ焼き(奢ってもらった)を食べながら、雑談とか雑談とかあと雑談とかいろいろしました。
歩くサンタクロース 解説
この記事は 解説 Advent Calendar 2017 - Adventar の8日目の記事です。
https://adventar.org/calendars/2398
問題概要
格子上にN個の地点があり、その全てを1回ずつ訪れなければいけない。
訪れるのにかかる時間は現在地と目的地のマンハッタン距離である。
開始地点は格子点であればどこでもよい。
各地点を訪れる時は開始地点から往復しなければならない。
ただし最後に訪れる地点のみは片道でよい。
開始地点を上手く決めて各地点に訪れる移動距離の和を最小化したい。
N <= 10^5
各地点のx, y <= 10^9
解説
(X, Y)を開始地点としたときの移動距離の和をS1、(X+1, Y)を開始地点としたときの移動距離の和をS2とすると、それぞれの距離の和はマンハッタンで求めるので、
S1 + [x座標がX以下の地点の数] - [x座標がXより大きい地点の数] = S2
が成り立つ。同じように(X, Y+1)を開始地点としたときの移動距離の和をS3とすると、
S1 + [y座標がY以下の地点の数] - [y座標がYより大きい地点の数] = S3
も成り立つ。
Nが奇数の場合
結論から言うと、開始地点を(全地点のx座標の中央値, 全地点のy座標の中央値)にすると移動距離の和が最小になる。
何故最小になるのか
この地点を(A, B)とし、この時の移動距離の和をSとする。この時、開始地点を(A+1, B)にした時の移動距離の和をS'とすると、
S + [x座標がA以下の地点の数] - [x座標がAより大きい地点の数] = S'
となる。ここで、Aは全地点のx座標の中央値なので、[x座標がA以下の地点の数]は(N-1)/2+1以上になり、[x座標がAより大きい地点の数]は(N-1)/2以下になる。よって、
S + [(N-1)/2+1以上] - [(N-1)/2以下] = S'
S + [1以上] = S'
となる。これは、開始地点を「全地点のx座標の中央値」からx方向に+1した地点から始めると、「全地点のx座標の中央値」から始めた時と比べて移動距離の和が大きくなる、ということを表している。同じように(A-1, B), (A, B+1), (A, B-1)から始めた場合も移動距離の和は大きくなる。つまり、(A, B)から始めると移動距離の和が最小になる。
Nが偶数の場合
奇数の時と同じように(全地点のx座標の中央値, 全地点のy座標の中央値)を開始地点にすれば良い。
良くない。
全地点のx座標は偶数個あるので、真ん中は2つある。xとyでそれぞれ2個ずつあるので、開始地点の候補は2*2で4個出来てしまう。
ここでどうすればよいか。
開始地点の候補は4個しか無いので、4箇所それぞれの移動距離の和を求めて、その中から最小値を選べば良い。
移動距離の和を求める
基本的には開始地点と各地点を往復しなければならないが、最終地点のみ片道で良い。
どの地点を最終地点にすれば良いか。
開始地点から最も遠い点を最終地点にすれば、最小の「移動距離の和」が求められる。
計算量は、ソートする時にかかるO(NlogN)である。
CODE FESTIVAL 2017 Final 参加記録＋解説もどき
本戦は行けなかったけどRatedなので参加。
AGCを2倍に拡張したみたいな感じ。
早解き3完出来たから良しとしよう。
cf17-final-open.contest.atcoder.jp
A問題 (300点)
KとIの間、IとHの間には文字が一切なく、Kより前、HとBの間、BとRの間、Rの後にはAが高々1個有るかどうかを判定すれば良い。
B問題 (400点)
2文字以上の回文を含むということは、次のいずれかを含むということである。
oo(ただしoはa, b, cのいずれか)
oxo(ただしoはa, b, cのいずれか、xはa, b, cのいずれか)
1文字目がaの時、2文字目にaを持ってくると「aa」という回文が含まれるのでbかcにする。ここでは、仮にbにしたとする。3文字目にaを持ってくると「aba」という回文が含まれ、bを持ってくると「bb」という回文が含まれるので、cしか持ってくることが出来ない。このまま繋げていくと、
a → ab → abc → abca → abcab → abcabc → abcabca .....
となる。つまり、文字列Sの中に含まれるa, b, cの個数を数え、3つの文字の中ででてきた回数が最多のものと最少のものの差が1以下になれば良い。
C問題 (500点)
愚直に再帰をすると、全ての参加者の都市に対して時差が+の場合と-の場合を計算しなければならないので、最悪O(2^N)になり、N<=50なので間に合わない。
しかし、N>=24の時、高橋君の都市も含めてN+1個、つまり25個以上の都市になるが、1時間刻みの時差は高橋君の都市を基準として+0時間から+23時間までの24通りしか無いため、鳩の巣原理により時差がどうであろうと2つの都市の時刻が同じペアが最低1組は存在し、よってどのように時差が+か-かを決めてもsは0になってしまう。
つまり、N>=24の時は必ずsの最大値は0になるので、N<=23のときだけ全ての参加者の都市に対して時差が+の場合と-の場合を計算すれば良いので、最悪O(2^23 ≒ 0.08 * 10^8)で済ませることが出来る。実際は全ての場合について判定するのにO(N)だけかかるため、最悪計算量はN=23の場合のO(2^23 * 23)となる。私は1316ms(実行時間制限は2000ms)で通したが、もっと早く出来るだろう。
D問題~ (700点~)
無理。
