ABC342

6完。最後の10分で2問通してるのは、(レーティングの意味で)効率はいいけど、たまに失敗して破滅する。まあ、早解きできた人にはGを考える時間も与えられて羨ましいね。

A - Yay!

150点だけど簡単じゃんと思ったら、けっこう大変だった。文字数をカウントして1のものを探す(Sの長さは3以上なので一つしかない)。位置を知る必要があると気づき、同時に位置も(文字毎に)記録する(知りたいのは文字数が1のものなのでこれでOK)。なんか簡単な方法がありそうだけど、ないのか。

B - Which is ahead?

各人が前から何番目に並んでいるかを求めておく。

C - Many Replacement

各英小文字がどこへ移るかを求めればいい。

D - Square Pair

ソートしていい。0はどうにでもなる。合わせて平方数になるのがどういうときか考えたけど、平方数で割れるだけ割った残りが同じっていういつもの条件だ。素因数分解した状態で考えていたので、残った素因数のvectorをmapに突っ込むとか思ってしまったが、それらを掛けた数でいい()。mapでカウントしたら、a[i]も書き換えてしまって、各a[i]について相手が何個あるかを足していく。0は別に数えておく。順序違いや自分自身とのペアはカウントしない設定だが、全部数えてNを引いて2で割ることにする。0は全員とペアになれる。そうでないとき、自分と同じのと0が相手になる。

順序違いや自分自身や0の扱いが難しくてサンプルがなかなか通らなかった。0は当然平方数と思っていたけど、「各素因数が偶数個入ってる」という特徴付けで平方数を捉えると、全部無限でほんとに平方数かってなるし、「何と掛けても平方数ってそんなことある?」ってなる。

ABC254が類題だった。当時はmapじゃなくてソートとランレングスで数えてた。同じ悩み方してて草。

(追記)解説にあったエラトステネスの篩みたいな方法でできた。「平方数で割れるだけ割った残り」になりえるものを見つけたら、それに2以上の平方数を掛けてできたものは平方数で割れるだけ割ったらそれになる。また、mapでカウントだけしておけば、入力を受け取りながら簡単に処理できた。

E - Last Train

最終時刻の意味がよくわからなかったけど、ちゃんと最も遅い出発時刻の意味だった。ダイクストラやるだけに見えるが、等差数列みたいだったり後ろからだったり、ひねりがたくさんあってきつそう。逆から見てスタート時刻は10^18+10^9で、2^60にそこそこ近いけど余裕を持って小さい。時刻2^60から始めて、大小逆のダイクストラみたいにやっていく。辺のコストが動的に(?)決まるやつ(遅く来たほうが得するみたいなのがなければOK?)。等差数列は怖いけど、落ち着いてやればそこまででもない。移動時間Cと基準時刻Lを引いて、これが0未満なら間に合わない。そうでないときDで割ってK-1とのminをとる。これで何番目の電車を使うかわかったので出発時刻もわかる。

なぜかサンプルが合わず、飛ばした。Fを通して戻ってきて、サンプル3で正解よりも良い(遅く出発して間に合う)回答になっている。ダイクストラということでなんか手癖が発動し無向辺になっていた(有向辺のダイクストラも普通にあるけど出題頻度が低いというそれだけの理由で)。慎重に、未来から過去への辺だけを残し、AC。

F - Black Jack

ディーラーのほうは戦略が固定なので求めてしまえる。yの各値について、通過する(そこで終わる場合も含む)確率を求める。幅Dの区間に足す必要があるが、いもす法みたいにしてできる。最終的な値の確率は、L以上の通過確率がそのまま使える。自分のほうは、各値で終わったときの勝率がわかればいいかと思ったが、実装しながら詰めていくと、その時点での勝率を後ろから求めていくことができて、x=0の時点の勝率(答え)もそのまま求まる。ディーラーの確率を累積和とって、xからNまでが負けだからその区間の和を求める。自分の勝率も累積和を作りながらやって、そこで操作をやめるかサイコロを振るか勝率が高いほうを選ぶ。

サンプルがなかなか合わなかった。いもす法が普通に間違っていた、ディーラーのL未満を0にするのを忘れた、区間和をDで割るのを忘れていた、区間加算するときもDで割ってなかった。

(追記)ディーラーのほう、配り終えたら自分を0にすれば、全体の確率の和が1のままできるしL未満は0になるじゃん。vectorも2本使ってたけど1本でできる。勝率は、区間和ではあるけどyがNより大きいところは使わないので、y=Nになる確率から順に足していくだけでいい。自分の勝率も累積和にして、最後だけ和をとらずに抜ければいい。

G - Retroactive Range Chmax

読んだだけ。

(追記)解説を読んで考えて書く。要素の追加と削除ができて最大値がわかるデータ構造が要る。とりあえずmultisetでやった。「区間更新クエリが可換」というのが重要なんだね。言われてみれば、セグ木の区間クエリで見る場所のmultisetに出し入れすればできそうだ。双対セグ木は未経験だったが、意外と実装は軽かった。提出して2045msでAC。次にmapでやってみたところ、1512msと速くなった。メモリ使用量はほぼ同じ。意外だった。で、以前実装した優先度を変更できるpriority_queueを試そうと思ったが、ちょっと用途が違う感じ。なので、解説にある「消せる priority_queue」を素直に実装した。310msとけっこう速くなる。今回は(multisetなどの)インスタンスの個数が多い(N*2程度)のでやや特殊なケースかもしれない。

ARC172

3完。一生青パフォしか取れない。つまんなすぎる。

A - Chocolate

「ルジンの問題」(名前は知らなかったので今ググった)みたいなやばいのも存在するので怖い。ただ2冪ということでそんなに変なことは起こらなそうでもある。とりあえずサイズ毎にカウントしておく。左上から貪欲に取っていくというのはどうか。しかし貪欲といっても右に行くか下に行くかがあるし、小さいのを取ったら長方形がどんどん増える。1個チョコを取って3個の長方形に分割されたとして、長方形をまたぐような取り方が必要になることはおそらくないと思うが。

AとBを交互に考えて途中から順位表も見ながら。全く解ける気がしない。

横だけ見て、4+4+4+2+1みたいに分割できる。縦にも同じことをすれば?もう少し考えて、HとWのビットが立っているところを全探索。例えばHで8、Wで2のビットが立っていたら、8*2の長方形が取れるが、2*2が4個として使う。これで、1から2^29までのチョコに分割できた。あとはこれを大きいほうから貪欲に使っていく。余ったものは4つに割って一つ小さいチョコにする。小さいチョコを使えるのは小さいのだけだから、小さいほうからというのもありそうで、両方が正しい方法であるイメージができず困ったが、大きいほうからのを書いてACした。

レーティングのことを考えると、未証明の貪欲をいかに素早く何も考えずに通すかというゲームになり、クソゲーが過ぎる。

B - AtCoder Language

Kが小さい順に考えていくが、なんかやばそう。K=4くらいで頭が限界になる。かなり色々考えて法則性が全然見えない。同じ文字2つが両端じゃないといけないK=2と、K=3の様子が、まとめて処理できる気がしない。

左からK-1文字選んだら、そこより右は全部違う文字でないといけない。ここから更に進んで、左右から合計K-1文字選んだら、その間は全部違う文字でないといけない。これは必要条件だけど、十分条件にもなってたりしませんか?つまり、連続するN-(K-1)文字をどこから取っても全部違う文字、これは1個ずつ掛け算していけば求まる。例外は思いつかなかったし、サンプルは通ったし、ACもした。ゴミ。俺は何もできなかった。

C - Election

開票結果の列が同じでも得票数の差の変動は違うこともあるわけじゃん。難しそう。とりあえず差のグラフを描いてみて、隣り合う2つの異なる票が入れ替わったときの様子を見る。あれ、これって端からN-1回入れ替えることで全部列挙できてるね。ということで、累積和(得票数の差)を用意して端から実際に入れ替えていく。開票結果の列が変わったとき、それは新しい列だ。0票のときとN票のときの差は順番によらず一定。それ以外のN-1個は、それぞれ変化したなら変化した場所が異なるので同じ文字列は現れない(たぶん)。比較するとき、負0正の3通りに直してから比較しないとサンプル通らないね。あっさりACした。

D - Distance Ranking

順位表見てEへ。問題はざっと読んだけど2次元だと思ってた。終了後少し考えたが、次元をどう使うんだ。今気づいたけど、次元を使い切るには1個ずつ追加して毎回新しい次元を使うことになるんだな。しかし格子点しか使えないから、ななめも必要な可能性もあるか。距離の条件がイメージしづらい。こういうのコンテスト中にやりたいんだよなあ。

(追記)解説のヒントを見たが、Nが3より大きいときどうすればいいかわからず。そもそも点がN個だとN-1次元しか張れないんだな。この立方体の正三角形見えないのもひどい。解説の微調整のところを見て自分でもやってみると、なるほど。急に昔の話をするが、高校の物理の実験で、振り子の長さを測ったとき、振り子の先端の玉には大きさがあるので重心にものさし(何使ったんだろ)をあてがうことはできない。そこで横にずらして測ったが、真横ならほとんど誤差が出ないことはわかっていた。このN次元空間では、微小な距離だけ動くとき、相手がいる方向に動けばそのまま相手との距離に寄与するが、それと垂直な方向へ動けば距離はほとんど変わらない。実際計算してみてもそういうのは全部2次の項になる。実装自体は単純だが、ステップ数があるし理解に時間かかったし、思いつくのが今の実力じゃ無理だし全部思いついたとしてコンテスト中に書けたかあやしい。

E - Last 9 Digits

2分くらいかけてチェックしたところ、被りがなかった(つまり条件を満たすnは常に存在して10^9未満)。なんだその性質。フェルマーの小定理でググってみたけど数が大きくてあんま役に立たない。ワンチャン、t=t^tを繰り返して短時間で見つかったりしないかなとか思ったけどダメそう。けっこう手は動かせたが、何かできたかというと。

(追記)3^3=27 mod 100というところから、103^103=27 mod 100とかも言えると嬉しいが、オイラーの定理を使ってもφ(100)=40だから100で戻ってくるとは言えない(実際には100で戻ってくる)。この40の計算も自分ではやってないし。そこでまた全探索してみる。これも2分くらいかかるけど10^2から10^9まで全部確認できた(10^1のときは例えば3^10=59049なので10乗ではダメ)。あとは下から1桁ずつ決めていく。最初の2桁は全探索。解説の、Pythonで数十分というのを見て思ったけど、今回のケースは実行速度10倍の違いが致命的だったんだな。自分はコンテスト中に2分くらいかけて全探索したが、これが20分だったらコンテスト中には試せない(10^8まででいい?いやー10^1は例外だったじゃんか)。

(追記)カーマイケル関数というのでわかるらしい。WolframAlphaにCarmichaelLambda[10]と入れると4が返る。100なら20。

ソシャゲ その2

(書きかけで何週間か放置してしまったので内容が古い)

プロセカのワールドリンクとユメステの0.5周年でかなりやったので、ちょっと音ゲー飽きてきたな。ブルアカの3周年もある。

ユメステ

前回のユメフェス(3か月前)のときは天井分の石を持っていなかったが、今回は貯めておけた。叶羽のアリス服があまりにもかわいいが、これを必ず入手できる安心感は良い。ただ、ユメステ(のアクターガチャ)はPUを自引きするかどうかが大きい(引ければ完凸、引けなければ無凸)。今回は運良く自引きできた。また、貯めておいたチケットで復刻限定のマクベス(超強いポスター)も引けた。

リズムゲームは、OLIVERが順調に上達しているのは嬉しいけど、STELLAもけっこう上手くなっている。もう(プロセカを1年半やった上で)半年やっているわけで、まだ伸びるのは意外。ノーツの速さは、ずっと11.0でやっていたが、段階的に12.0まで上げて、慣れてきたのでそこで11.0に戻した(プロセカでやって感触が良かったのでまたやってる)(しばらくやって遅すぎるのでまた変更して11.5で落ち着いていい感じ)。遅いほうが視点が下がって反射神経もいらなくなるので自分に合っていると思う。一旦速いのに慣れる意味は、ノーツ密度が高くて認識できない配置に適応するためと思っていたが、まあ色々複合的になってそう。

ブルアカ

もうとっくに恒常キャラの半分以上を受け入れているため、限定ガチャを重視する立ち回りに変えている。以前は好きなキャラであれば恒常ガチャも引いていたが、好きなキャラは大体引いたし掘れる石も減ってきたしね。自分が今このゲームで重視しているのは、生徒数を増やすことと、絆ランクをカンストさせないこと。1年前の初期メンバーが続々と絆ランク20になっており、星5にできる/なってるのはそのほんの一部なので、どうしようもないところではある。

好きなキャラを挙げると、宇沢レイサ・モモイ・コハル。宇沢レイサはブルアカ始める前から知っていた。中学生みたいでかわいい。モモイは総力戦コインで固有2にした(数日前に固有3にした)ので強いというのもあり、自分は強いキャラを好きになる傾向があるので。以前はミドリが気になっていたのに、いつの間にかすごい勢いでモモイを好きになっていった。コハルはノーマルロビーにやられた。(チョーカーにまぎれて)線があるの気づいてなくて、2.5周年のときびっくりしちゃった。

誕生日に石がもらえるのを誕生日の2日後に知って、残念がりながらとりあえず生年月日の情報を入れたら、次ログインしたときもらえてた。こういうとこでしっかり好感度上げてくるよな。来年は誕生日ボイス聴くぞー。

ところでブルアカの一番の運要素って戦術対抗戦の組分けじゃない?自分は前期の戦術対抗戦で50位くらいを維持してたんだけど、今期は500位ボーダーを行き来している(自分は生徒レベル80前後なのに周りは87の星5ばかり)。新規は新規同士で割り振られるってことかな(そうじゃないこともあるらしいです)。それにしても半年とか同じ組でやるわけで運要素があまりにも強い。毎日石がもらえてその量が変わるのがやばすぎるし、コインもAPに変換できるのでこれも大きい。まあ、ガチャで天井までにPUが来るか来ないかに比べればどうでもいい差か。

そのための広橋。今回のイベント(陽ひらく彼女たちの小夜曲)で歌が入ったときはARIAのアリスを想起せざるを得なかった。

実は贈り物を渡したことが一度もない。製造はしてる。

プロセカ

(これは最新の)

シャニソン

覗き込んできてちょっとお腹出たんじゃないですかのにちかがかわいすぎる。

ABC341

6完。後半の問題は面白かったけど、結果については何も感想がないです。

A - Print 341

"10"をN回出力して最後に"1\n"を出力する。

問題名見てなかったけど、341を2進法で表すとサンプル1なんだね。

B - Foreign Exchange

問題文の長さ、入力の多さ、操作の順番によらないという考察、どれも難しくて150点じゃないだろ。順番に全部交換していく。答えが大きくなりそうと思って64bit整数で書き始めたが、Nが2*10^5なのでさすがにやばいと思い問題文を確認すると、交換して単位数が増えることはない制約だった。64bitで書いてしまったので何も考えず仕上げてそのまま提出したが、結局64bitは必要だったんだな。

C - Takahashi Gets Lost

全探索とはいえ重すぎる。こう書くと全探索が簡単みたいだな。全探索を書くのは難しいことが多いけど今回はそんなに難しくない。宇宙船が不時着するのは海だと思ったら陸だった。string("RDLU").find(t[i])で文字を数に変換。スタート地点が違えば違う場所に着くので、単に条件を満たす場所をカウントする。陸から始めて動きをシミュレーション、海に当たらず最後まで行けたら。

D - Only one of two

答えがどのくらい大きくなるかよくわかんなかったけどそこそこの頻度で現れそうだし10^18くらいには収まるんかな。実際の提出では2^62にしていた。二分探索する。i以下の正整数のうちNの倍数はfloor(i/N)個。包除すればいい。i以下の条件を満たす正整数が初めてK個になるところが答え。サンプル合わなくて、N*Mじゃなくてlcm(N, M)を使う必要があった(ひどい)。まだ合わなくて、サンプル1でなぜか6をカウントしていて、「ちょうど一方のみ 」ではなく「少なくとも片方」になっていた。手癖で書いてしまい気づけない。

E - Alternating String

A問題と似ている。奇数番目の文字を反転(0なら1に、1なら0に)して、全て同じ文字なのを良い文字列と呼ぶことにする。遅延セグ木を使わずにできるか考えたが思いつかないので遅延セグ木で書く。区間反転区間和取得。反転したら和は、その区間の長さから引いたものに置き換える。

解説を見て、まさか010101のまま処理できるとは。確かに、クエリ1で影響が出るのは2箇所しかないってなんとなく気づいてはいたんだよな。これを軽視していたという事実があまりにも重い。

(追記)BITで解き直したけど、これは添え字合わせが大変なので、思いついたとしてタイムやペナの確率が改善したかは微妙。

F - Breakdown

「有限回の操作の後には」のところ、1回も有限回だから1回の操作で必ずコマがなくなるのか?と。そういう読み方もできるよなと思った(しないけど)(今考えると1回じゃなくて0回のがいい)。

W_iを頂点の重みと呼ぶことにして、重みの和が小さいところへばらまくわけね。重みとコマの数の積の総和という量を考えると、(非負整数であり)操作で必ず減るので(しかも0になるのはコマが0個になったときのみなので)、確かに有限回の操作でコマがなくなるなと。重みが小さいところへしかコマを渡せないので、そういう辺だけ残すとDAGになる。DPできそう。ただ、どうやってコマを置く頂点の集合を選ぶのか。さっきの量がなるべく減らないようにとか思ったけど、あいまい。ある頂点にコマが1個だけあるとしてそこから何回操作できるかでDPすればよさそうだと思ったので実装。小さいほうからやるんだね。自分より重みが小さい頂点がない頂点は簡単。辺が5000しかないので、重み(これも5000)の回数のループを出てる辺の数だけやっても間に合う。なんとナップサックだ。重みがちょうどjのときの最大回数でやったけど、重みがj以下のときの最大回数でよかったよなあと。ナップサックの更新は重みが大きいほうからやればin-placeでできる。

(追記)書き忘れたけど、「重みとコマの数の積の総和」が最初64bit整数に余裕で収まるし、1回の操作で1以上減るから、操作回数もそんなに大きくならない。あと、最初常に0を出力していたが、渡す相手がいなくても(いても)1回は操作できることを忘れていた。「重みがj以下のときの最大回数」で書き直し、ナップサックのDPテーブルを全部1で初期化。

G - Highest Ratio

二分探索に見えるので、とりあえず計算量は無視して二分探索を書く。これをまとめてやったりできないかなあと考える。並列二分探索とか知らないのがけっこうマイナスに働く。それなりに時間はあったが、結局何もできなかった。

(追記)色々見てAC。計算量大丈夫かと思ったらスタックのやつね。累積和をプロットすると、kから「k+1からNまでのどれか」へ線を引いて傾き最大にする問題になる(全く思いつかなかったな)。kを考えているとき、k+1と「k+1からの傾き最大になる相手」の間(端を含まず)のことは考えなくていい。傾きがより大きいものはないし、その傾きが小さいなら相手はk+1で決まりだし、そうでないならk+1よりも1遠くから見ているのでより遠いほうがその傾きをたくさんもらえてよい。スタックを使わなくても単に相手を持つだけでスタックみたいになる(飛ばされたやつはもう現れることがないのでO(N))。傾きの比較は整数で簡単にできる(これが64bit整数に収まるようにするためにAが小さかったんだね)。まだちゃんとは理解できてないが、こうやってコードを書いて提出して少しずつ慣れていくしかない。