ABC173

けっこうしんどい回だった。E以外の5完。

A - Payment

答え自体はすぐ思いつくけど、「それで絶対に漏れがないか」になかなか確信が持てない。実装もちょっと長くなってしまった。

B - Judge Status Summary

長さ256の配列を用意して、先頭の文字番目をインクリメントして数えた。しかし、出力でも"AC"とかの文字列が必要なのを忘れていた。結局string[4]を用意するなら、最初からそうすればよかったか。でも連想配列はさすがに(通るだろうけど)重いし、提出したコードより簡単にはならんかな。そんなに迷った記憶はないけど、それなりには時間かかってる。

C - H and V

全探索。2^(H+W)という形は見慣れないのでそこが面白さ。まあ素早く正確に実装するのはきつい。

D - Chat in a Circle

大きい順に使うとよさそうだけど、難しい。21:26くらいまで考えてEへ。

最初に考えていた、大きい順に貪欲に取っていくみたいのを実装しようとする。どうやって?最初の2個を置いたら、次の2個、次の4個、次の8個ときれいに置いていけそう。貪欲といっても色々な置き方があるので不安だが、こういう置き方だとわかればまあいけそうではある。r += a[i / 2]; だけになって、思ったよりずっと短いコードになった。ということで未証明AC(何千人も解いてるのでこれで通らないとは考えにくい)。「A_kの寄与は2回まで」というのは思いつきたかったね。

E - Multiplication 4

簡単そうだけど負の数があるから難しいのね。困難はなさそうだが場合分けが組合せ爆発して頭がウニになってきたので、落ち着いて21:46くらいにFへ。

残り40分。これだけあればACできると思い考え続けるが、もうとにかく気をつけるべき要素が多くて自分のプログラミング力では足りない。残り15分くらいになって、無理そうだと思いDへ。

残り10分。ACしてないのはE問題だけ。普通にやったら絶対無理なので、正確さは度外視して無理やり最後まで書き切ってみたが、サンプル通らず。時間に合わせて書き切る技術があるのは良い。最終的な方針は、「0を選ばざるをえない」「0を選ぶ権利がある」「積を正にできる」「それ以外(答えは負になる)」などで場合分け。答えの符号を固定したら、絶対値が大きい(小さい)順にとって、負の数の個数が合わなかったら正の数と負の数を交換する(最大で2通り考えればよさそうだが自信がないし、それでいいとして実装がクソ重い)。modとってるので大小比較がめんどい。doubleに変換してlogを足してくのも考えたが、さすがに落とせそう。

F - Intervals on Tree

けっこう解いてる人が多いので「全完回か?」と思い始める。愚直にやるとN^3くらいかかりそう。Nを2つ落とすのはきつい。とりあえず適当な木を描いて連結成分が生まれて消える様子を見る。ここで、関数fが単に頂点数であれば簡単に解けることに気づく。これ、各辺について何回カウントされるかわかれば、1回につき連結成分が1個減るからもうそれ答えなんじゃ?一つの辺に注目するみたいの、一昨日のyukicoderでできなかったんだよね。グラフを構築する必要もなく、短いコードでAC。DよりもEよりも簡単だった。

ABC172

相性の問題か、あまり面白くなかった。調子は良かったと思う。

A - Calc

書くだけで工夫の余地もなさそうなので不安になる。(1 + (1 + a) * a) * a のような書き方をする方針も考えたものの、普通に書いたほうが速くて確実だと判断してそのまま書いた。これだけ考えて27秒なの、ABCのAって感じだ。Aで色々考えるの好き。

B - Minor Change

編集距離の亜種に見えてビビるが、違うところを数えればよい。なぜか、一致するところを数えてNから引くような方針を選んでしまい、それなのに条件は s[i] != t[i] のままなのでサンプルが合わず、結局普通に書き直す。Bまでは考察も実装も軽かった。

C - Tsundoku

∩の形みたいのを思い浮かべ左を上に右を下にあるいはその逆にうにょうにょさせる。しゃくとり法で解ける。考察は簡単だが、実装はかなりめんどくさそう。ここでトイレに(時間を損しないためDを読んでから)。戻ってきて、ゴリゴリとしゃくとりを書く。時間はそれなり。1発ACなのはさすがの実装力ですね(?)。

D - Sum of Divisors

全然わからん。10^7というのはlogが付くとギリギリになる。しかし実行時間制限が3秒なのでそれも許されるのか?しばらく考えるとそもそも埋め込みできることにも気づく。どう解いてほしい問題なのか(という情報に頼るのはよくないと思ってはいるが)全然わからず、結局、約数がわかるタイプの篩を使いO(N*log(N))(この方法もっと計算量小さかったりするのかな)。手元で実行時間を確認できるので、一応安心して提出できる。

(解法ツイートとかを見て)約数に関するこういう感覚、最近全然だなあ。一時期普通に使えてたし今でもできるはずだが、なんかできないことが多い。

E - NEQ

なんか問題文が読めなくて、読むのに5分以上かかった。2番目の条件、あんまり意味のない「かつ」で誤読しがち。A_iは相異、B_iも相異ということで、字面のイメージとは逆に1番目の条件が厄介だった。Aは1,2,3,4,5みたいので固定して考えてもよくて、ただの順列かよと思うものの、Bで同じ位置に同じ数が来ちゃだめなので、うまくカウントできない。なんか同じ位置に来ないシャッフルとかあったよねと検索かけるがいまいち思ったものが出てこない(攪乱順列がキーワードだった)。ちょうど1個一致したときの通り数をNとMが1小さい問題に帰着できるみたいな方針を考えたが、2乗は間に合わないし高速化もできない。1番目の条件が本当に厄介で、何をやっても同じように阻まれる。

かなり経って、適当に包除とかも試してみたら当たりだった。よくわからんけど適用すると通る。これはつまらない。以前と違って包除原理を形式的に(?)使うことはできるようになったので、それはいいことだけど。昨日のyukicoderのNo.1100 Boxesみたいな魅力がない。理解してない部分を突かれて嫌な気持ちになっちゃったのかな(だとしたら完全に逆恨み)。

F - Unfair Nim

時間ないけど、設定自体は単純。Nimでググって、ニムでググるほうがいいと気づいて、必勝法を思い出す(理解はしてない)。要するにa[0]とa[1]を除いた総xorとa[0]^a[1]が等しくなればよくて、a[0]+a[1]は一定なので問題はa[0]&a[1]になる(A+B=(A^B)+(A&B)*2)。制約が10^12なので全探索はできない。さすがに短時間ではワンチャンなかった。

ABC171

Fが数え上げ(昨日全く解けなくてトラウマ)でちょっと詰まって不穏になったけど結局解けて、全体として面白かった。

A - αlphabet

A問題でまさかの誤読(大文字を小文字に、小文字を大文字にするんだと思い込んでいた)。文字コードは'A'のほうが'a'より小さいと、わかってはいたが、やはり大文字のほうが小さいという状況は混乱を生んだ。if (c < 'a') c += 'a' - 'A'; などと書いていたが、符号とか順番とか、サンプルが通らないとどこも間違ってる気がして。特に最初は大文字小文字変換としても間違っていたので泥沼にはまった。3分以上かかってしまい、この時間のかかり方はyukicoderのAみたいだなと思った。

B - Mix Juice

ソートして小さいほうからK個足せばいい。既出な気がして、誤読してないか不安だった。

C - One Quadrillion and One Dalmatians

クソムズC。天才なのでそれなりのスピードで書けた。まず、何文字の名前になるか調べる。K文字の名前は26^K個あるので、便宜上0番の名前を空文字列(26^0=1で1通り)として、K=0から順に26^Kを足していって番号を超えたらループを抜けて超える手前の数を引く。これで桁数がわかったので、あとは26進法に直すだけ。

D - Replacing

PASTっぽいけど簡単で面白い(わりと瞬殺だった)(最終的な和だけ求めればいいと誤読していたが短時間で修正できた)。まずstd::mapを使うことが浮かんだが、10^5までなのでvectorでいい。各数が何個あるかカウントしておけば p[c] += p[b]; p[b] = 0; のように移し替えることができる。

E - Red Scarf

Aで少しロスしたもののCDをいい感じに解いたので順位が上がっているかと思ったらそうでもなかった。問題の見た目からしても、このEめちゃくちゃ簡単なのでは?まず、全体のxor(Tとする)がわかっていれば T ^ a_i を出力するだけ。「何でもいいのでは?」と思いTを適当に設定して出力してみる(出力に10^18以下などの制約がないので際限なく大きい答えは存在しなさそうであることに注意)。しかしよく考えるとT=0にしたうえで出力したそれらのxorが0になるとは考えにくい(あぶなかった)。そういえば制約にNは偶数とあった。a全体のxorは、全体のxorをN回から1個ずつ抜けてるのでなるほどここが奇数になる仕組みか。つまり、Tはa全体のxor。これは瞬殺したかったなあ。

F - Strivore

それなりに解かれているのでこれもそこまで難しくなさそう。Sの長さをNとして、長さN+Kの文字列(部分列としてSを含む)を作る。最初、N+K文字の中からN個を選ぶだけかと思ったが、元から含まれる文字を追加したときに重複してカウントしてしまう。O(N^2)のDPを高速化するような方向でも考えたがダメっぽい(昨日の恐怖が呼び起こされる(それがなければもう少し早く解けたんじゃ?))。で、しばらく経って、条件を満たす文字列を、左から貪欲に部分列をとっていくことでダブりなく分類できると気づいた。あとは、その部分列以外のところの埋め方を数えるだけ。貪欲にとったので、次に来るSの文字以外の25通りが基本で、最後だけ何でもありの26通りになる。その最後の部分の長さが0からKまでについて何通りあるか足せばいい。Sの最後の文字の位置がわかっているので、あとはそれより左の領域で残りのN-1文字がどこにくるかをコンビネーションで数えるだけだ。実装が軽かったので思ったより早解きできた(22時までには解きたいなあとか思っていたが10分前に通せた)。

AGC046

つまらなかった。こんなの解けて何になるんだという気持ちになった。みんな解けてるのに自分は解けなくてすごく嫌な気持ちになった。なんか最近のAGC、(結果はそれなりにいいこともあるけど)毎回つまらないんだが俺の頭がおかしくなったのか。

A - Takahashikun, The Strider

瞬殺できるはずの問題を瞬殺できないのが悲しい。わからないので実験してみると、正360角形とか星形とかになる。これではわかりにくいので矢印を全部原点から生やすと、いい感じに散らばるやつ。作れる最小の角度はXと360の最小公倍数だ。全部揃ったときに戻ってくるので360割るそれ。こういうの好き。好きなものは瞬殺したいが7分かかってしまった。

シミュレーションできることはすぐ気づいたけどさすがにそれをやったらAGCに出てる意味がないので頑張って考えた。7分ならその実装もできたかな。誤差怖いけど。

B - Extension

全然わからんので碁石を使って考える。下から見てD-B個、左から見てC-A個みたいな雰囲気はわかってくる。だいぶ経って、「重なる」ものを引けばいいと気づく(重なるというのは下から伸ばした棒と左から伸ばした棒が重なるみたいな)。左下から順にそこで初めて重なるものを数えればいいかと思ったけど無理そうで、無理になった。この時点で1時間くらい。Cへ。

C - Shift

操作がけっこう想像しづらい(要するにrotateだけど0と1しかないしね)。頑張って考えると、1でさえあればより左の好きな位置に挿入できるっぽい。実験すると操作も意外と可換っぽい。先頭の連続する1は削除してもよくて、0はセパレータと捉える、回数は1の個数まででよさそう。

ただ数え方がわからない。減るやつと変わらないやつと増えるやつに分かれる、全体の和は0、累積が一度でもマイナスになってはいけない、減るのは元の個数まで。いやKも指定されてるし無理では。だいぶ経って、真ん中で分けてそこを通過する個数を固定するのを思いつく(分割統治)。300だし。DPも考えたけど、DPというよりは注目すべき量を見つけることが大事なのかなと思った。