Hatena::ブログ(Diary)

merom686の日記 このページをアンテナに追加 RSSフィード

2018-07-21

ABC103

A - Task Scheduling Problem

Aが極端に難しい。ただまあ難しい問題だと思って解けば解ける。コストが差の絶対値ということは、Aが小さい順にやっていけばいいのだ。ABCのAでこういうのいつも迷うんだけど、最近はn=3としてソートしてる。差を出力して、WA!?確かに、A問題でそこまで難しくしないだろうという甘えで考察が雑だったかもしれない。しかし、わからない。いざとなれば全探索があるけど。順位表を見てみる。かなりWAが多いが、AC取ってる人もいる。じゃあ俺のミスか。ただ、いつもならサンプルを含んでいたはずのテストケースで全てWA(サンプルは自動で確認しているので合ってるはず)。何かおかしい。Clarが来てない(beta版は開かなくても新たな質問の数が表示される)のを確認してからTwitterを見るが特に何もアナウンスはない(ここでTwitterを見させる普段のAtCoderがどうなのかという気はした)。同じものを提出すればACになるのではという考えも浮かぶが、まあここは後回しで。時間が経てば何かわかるかもしれない。この時点で5分が経過していた。

B - String Rotation

最初、回転という言葉からstd::reverseのような動作を想像した(180度回転)。しかし操作の説明を読むと違う。ABCのBは全探索という格言を思い出し、std::rotateで全探索した。

C - Modulo Summation

A mod BのBを変化させるのかと思ったらAを変化させるのかあ。Nが3000、aが10万。aの最小公倍数は大きすぎてダメ。O(max(a))みたいな全探索が利くのかなあ。いやあ、B問題じゃないんだから。ウンコがしたくなってきた。まさかこんなに難しいとは。max(a)のとこで最大にしようとして、いやダメだとか考えてて。ふと気づく。mが-1なら?天才かよ。いやあ、解けたから言うわけではないが、この問題は良い。これは気持ちいい(やっぱり解けたからじゃねえか)。具体的なmが64bit整数に収まらないほど巨大になるのが素晴らしい。ちょっと色々な探索方法を考えすぎた。力で押し切ろうというのはABCに対する甘えだ。11が12-1だと気づかなかったね。言われてみれば当たり前でこのブログを書くのも恥ずかしいくらいだが、短時間で解くからこその感動。

D - Islands War

短い問題文が怖い。そう、本当に怖いのは長い問題文じゃなくて(Cで精神をやられている)。UnionFindとかが浮かぶが、どうも逆っぽい。連結になっていてはいけないという条件なので考えにくい。逆に橋を足していくか?いやそれもダメ。色々な足し方があるので貪欲に足していってもたぶんダメ。なんか双対問題を考えれば。全然わからんけど。そもそも普通のグラフの問題と違って横一列なんだよね。状況がつかみにくい。紙の上で色々実験してみる。いくつかの状況を見たが、どちらで切ってもいいというケースが出てくるのが厄介だ。ここまでかなりの時間を使っている。

ということで、bでソートする(そして左から見ていく)ことを思いついた。あーこっちの典型かー。この段階では、まだ思考は混乱している。とりあえず構造体を用意し、ソートまで書く。これは0-indexedに直さなくてもいけそうだと思い、自分にしては珍しく直さなかった。さて、aはソートしなくてもいいことを確認する。ソートするのが無難ではあるけど、どっち向きのソートかわかんないし、書くのもめんどいし。とにかく、このアイデアの骨子はその組(a,b)の間に少なくとも一つある切断のうちの一つをb-1とbの間にして損をしないということ。それをベースに、何と何を比較すればいいか、本当にそれでいいのかを確認しながらコードを書いていく。b-1とbの間で切ることをbと表現した。書き上がってサンプルが合ったので提出。

D問題のジャッジを待つ間に、A問題の提出を持ってきて考え直す。DはAC。AもACに変わっていた。0WAで全完。それはめでたいが、順位には微妙に不満が。この前のABCがハチャメチャによかったからね。今回はトラブルもあってそれは大いに不満だが、何よりC問題を瞬殺できなかったのが一番の課題だ(Dはまあこのくらいは仕方ないという感じ)。

2018-07-14

AGC026

苦手かどうかはともかく長い時間のコンテストはあまり好きじゃない。時間を余らせるイメージしかない。しかし、重い600点2問を時間をかけて通したので結果的に時間は使えた。

A - Colorful Slimes 2

よく覚えてないけど、直前と同じ色が現れたら適当な(次のやつと異なる)色にすればいい。解説を見たあとなのでね。思い出せない。最初、直前の色を更新するのを忘れてサンプルが通らなかった。

けっこう速く解けたので、1完のときの保険ができたと思った。

B - rng_10s

これはきつい。とにかく場合分けの嵐をやった。限られた条件下の話にどんどんしていく。4つも変数があって本当に厳しい。ソースにコメントをガンガン書いてどうにかして進んでいく。「初めて在庫がC本以下になるとき」とか明らかに簡単なのにかなり手こずった。さて、DがBより大きいときそれでも死んでしまうゾーンというのはどこか。まあそれは計算できる。問題はそこに到達可能か。ここで、DとBの最大公約数きざみでしか値が現れないことに気づいた。そして、DとBが互いに素なら簡単じゃないかと思った。AやCは関係ない値だが、まあうまくやれそうではある。最大公約数きざみで全部の値が現れそうだと思って、そこはちゃんと詰めてなかったけど、提出してAC。このACは大きい。AGC024みたいなことがあるのでわからないけど、悪くない結果は保証されたかなという感じ。

C - String Coloring

ちょっとあからさますぎて、半分全列挙に気づくのに時間がかかった。気づいてから解けるまでもけっこうかかった。右側の候補として、赤青2つの文字列でソートして一致する範囲を見ればいいのだが、その方針がなかなか見えない。わかってしまえば実装するだけ。時間制限が3秒なのはそういうことだろう(文字列をソート・二分探索するので少し遅い)。実装が重かった。書き上げてからも、混乱しているので左側の情報しかつかってなくてはまったり。

D,E,F

まずDを読んで全くわからないのでEへ。Eは簡単そう。700点くらいの見た目をしている。少し考えて解けないのでFへ。まあ解けると思ってないので全部の問題文を読んだ。

30分近く残してCまで解けたことのメリットはここで、普段は読む機会のない問題文を読むことができる。今回は解説放送も最後まで見てみた。問題文を読んであるのでわからないなりに楽しめる。ただしFは全くわからなかった。りんごさんの解説を聞ける幸せ。

2018-07-08

SoundHound Inc. Programming Contest 2018 -Masters Tournament-

4完。なんでE解けないかなあ。レーティングは微増。コンテスト後のやる気のなさがすごい。

A - F

簡単なAは久しぶりな気がした。そこそこ面倒ではあるけど。Fって15のことか。

B - Acrostic

これもやるだけ。なんだ簡単回か〜?

C - Ordinary Beauty

と思わせてこれ。こういうの得意ではあるはずなんだけど、手こずってしまった。左から順に考えていくと、dがnに近い大きさでa[i]がn/2くらいのときa[i+1]との差はどうやってもdにならない。その範囲をきっちり求めるのが大変だった。いや明らかに簡単だけど大変だった。そしてDPみたくやっていこうとソースを書く。mがでかいので間に合わないが、途中までやればあとは変化しないだろうからいけるだろうと。だいぶ経ってから気づいたけど、dが小さいときも、両側に相手がある範囲というのがあって。それも計算した。んで書いてみるとどうもおかしい。方針がおかしいのではないか。なんか独立にやってもいいのでは。実際単純に足したらサンプル通った。本当に独立でいいのか頭の中で考え直してから提出。AC

今になって振り返ると、全然理解してなかった。ていうか何やってたんだ俺は。正直、昨日は解説見ても全然ピンときてなかったし。本当に解説の通りとしか言いようがないんだけどね、わかんなかったね、昨日は。

D - Saving Snuuk

問題文が長いのでビビるけど、両替は1回だけ。年数が出てくるが、移動に年数はかからず、使える両替所の数はnから1まで変化する(端っこはn-1や0でない)。両替する場所を決めてしまえば、両側からダイクストラ法をやるだけの典型。しかし、両替所は閉鎖されるしn年ぶんの答えを得る必要があるし、そこが大変そう。

どうせ使う両替所は1つなんだから、各両替所についてそこを使った場合のスヌークの最大額を求めればいいのでは(ダイクストラをやっておけばO(1))。なんか最近やった問題のイメージが思い浮かぶ(なんだっけ)。値を更新していく。i年後のiが小さくなるほど状況は有利になるのだから、未来から順に良い両替所を更新していけばいい。

E - + Graph

最初は難しそうに思うが、例えばグラフが木だとして、1か所決めれば他も全部決まってしまう。木でなくとも二部グラフなら、ある頂点の数を1大きくすれば、違う側のは1小さく、同じ側のは1大きくなる。つまり二部グラフなら、適当に1つの頂点の数を決めて、それぞれの側の最大値だか最小値だかを見れば使える数の範囲がわかるはず。さて、二部グラフでない場合も0通りとは限らない。これが厄介そうだ。+1と-1が同時に襲ってくるから、あるとしても1通りだろう。解が見つかったとして、そこからある頂点を+Aすると、どこかでバッティングするときにA*2の差となって現れる。ならば、食い違ったときにその差の絶対値の半分だけずらして、初期値が1ならそれ以上小さいのはないので大きいほうへずらして、それでOKか調べればいい。と思ったけどWAだった。あんだけ複雑に書けばWAが出るのが自然と思ったが、根本的に解けてない可能性もある。1時間あったしこれは通したかったね。

(追記)ようやくAC。偶閉路のチェックをしていなかった。テストケースのoddLoop.txtとoddLoop_0.txtでWAになっていたのだが、本当に奇閉路を含んでいるの?二部グラフだったらREになるような提出をしたらREになっていた。

2018-07-03

ARC100

100だけど今回は特にお祭り感なし。30分早い開始は非常に珍しく、調子が狂う。

C - Linear Approximation

A_iからiを引いてしまえば昨日のB問題みたいになる。あー、B問題やっときゃよかったかと一瞬思ったが、これはたぶん単に真ん中(より大きいやつとより小さいやつの個数が同じなら少し動かしても変わらない)でよい。奇数個と偶数個の例でn/2でいいことを確認。極値のとこが平らじゃないこともあるのでしっかり選ぶ。ソートしてその値を取得。当時は中央値という言葉は頭になかったと思う。nth_elementのほうがたぶん速いがまあソートでいいでしょ。

D - Equal Cut

入力がCと同じなのが良い。なるべく均等に4つに分ける。4つって多いなあ。問題文をながめながら何か降ってくるのを待ったが何もない。順番を変えることはできないんだな。とりあえず2個に分けることを考えてみる。ちょうど真ん中くらいで切りたい。累積和を持っておけば、その区間の和はわかるし、その半分を超えたところが二分探索でわかる。超えたところか、その直前のどちらかが答え。じゃあ3つだったら?3つを2つと1つに分けて、その切る位置を変化させていく。1つのほうは狭義単調減少、2つのほうの最小値は広義単調増加。グラフを描くと三分探索で行ける気も(注:今考えると何言ってんだかわからない)。仮に三分探索で行けるなら、残りの分け方をN通り試してO(N(logN)^2)で解けるが。しかし平らなところがあるので三分探索ダメそうな気もする。うーん。

真ん中で分けたら?2つと2つに分ける位置をN通り試す。2つに分けるのは二分探索でできたはず。ていうかこの形ならしゃくとりでlog外せるじゃんと気づいた。なんか話がうますぎる。でも真ん中の境目を先に決めるのは問題ないし、左の2つを均等に分けることは最大値を小さくするし最小値を大きくするのでデメリットがない。これでいいっぽい。じゃあ実装するだけだ。右側と左側があるので関数を作ってreverseで2回実行する。もうしゃくとりに苦手意識はほとんどないが、今回の実装は重い。幅2から幅NまでのN-1個からなるvectorを返す。それもintのvectorじゃダメで差の絶対値と最大値と最小値、あ、差の絶対値は要らないか、それを返すためにarray<int, 2>のvectorにする(intはllにする必要があり1WA)。足してみて行き過ぎだったら戻して決定という処理がややこしい。幅2から幅Nまでを配列にどう格納するのが自然かもわからない。色々なことがあって、自分の能力で余裕を持って処理できず、ミスが出る。最小値の更新を忘れていてサンプルが通らずけっこう悩んだ。

2018-06-23

ARC099

2完。虐殺回だったね。僕は虐殺回わりと好きだけど、今回は自分の力のなさ・不甲斐なさを見せつけられてへこんだ。

C - Minimization

ちょっと考えると、全部1にするしかないというのがわかる。なんかNがKの倍数でN/K個に区切られてて区間を1個ずつ1で埋めていくイメージ。数に重複はないからN-1個の数を1に変える必要がある。1回の操作で1にできるのはK-1個まで(あ、K個ではなかったね)。なので答えはN-1/K-1を切り上げたやつ。んー、割り切れないときも有利にしか働かない気がするし、Kが2のコーナーケースも大丈夫そうだしまあいいかと提出。AC。3分台でかなりいいタイムだが、ちょっと俺の考察が軽い。今回はたまたまACだったが、細部をきちんと詰める必要があると思った。

D - Snuke Numbers

大体どんな問題かはすぐわかった。しかし具体的にどこなのかはさっぱりイメージできない。なんかグラフを描いて上か下に曲線(張った糸みたいな)を当てて糸と点が接しているところみたいなパターン。今考えると、NとN/S(N)をプロットしたんじゃそのパターンにはならんね(本当に?)。NとS(N)なら?いやわかんねえよ。まあまあその話はおいといて。

15分くらい考察して全然進まず難しすぎると思い実験に着手。1000くらいまで見てみると、けっこうわかりやすく規則性がある。少なくとも1の位が増えているときは、S(N)も同じだけ増えてNのほうが大きいのでN/S(N)は増え続ける減り続けるどっちだか忘れたよもう。ほんと認識しづらい問題だ。まあどっちかだとわかればいいのだ。で、まあそういう法則性があってもおかしくない。解説に難しい証明が書いてあるのが目に浮かぶ。きっとみんな実験してどんどんAC取ってるよ。俺も提出しよ。WA。

証明してないから100%俺が悪いですね。Nが100万までN/S(N)を計算して、逆から辿ってすぬけ数らしきものを出力してみる。ああ、普通に間違ってた。なんで行けるところまで実験しない。1024で終わらしたときはすぬけ数でないのも目視で確認してたからね。しかし100万以下のすぬけ数候補を表示させなかったのは意味わからんな。早くEをやりたいなあ。とか言ってね、もうね、早く楽になりたいんですよ。新たな実験結果を元に形だけの考察をして、考察は進まず、法則性に従ってコードを書き直し提出。WA。コードを軽くデバッグしてみたが、Sを求める関数がintだった。目視で確認する前提だったから意識してintにした記憶があった。そこを直して提出、AC。

なんか、500は通過点みたいに思ってたんだよね。そういうこともあるだろうけど、少なくとも今回は難しかった。しっかりした問題だった。それを適当に提出してWAをもらい、適当に提出してACをとった。あとからすごい自己嫌悪が襲ってきた。

E - Independence

DのACを確認してEの問題文をざっと読んで、そこから45分くらいは残っていた。連結成分は1つと仮定して、それを2つに分けたとき間にある辺を多くしたい、みたいなのを考えてた。太字で「直接」と書いてあるのに気づいたのは残り20分になったとき。なんじゃそりゃ。これは同じくらいのサイズに分けたいってことか。辺の有無を逆にするとか。いや調べるべき組み合わせが多すぎて無理でしょーとなって終わった。なんか色々問題外だった。

Highest更新した。こんなに嬉しくないHighest更新は初めてだ。