Hatena::ブログ(Diary)

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

2018-08-05

ABC104

Only回と思って油断してたらこの難易度。厳しいけど、ここんとこratedコンテストがないのでいい訓練になる。

A - Rated for Me

今回は、順位表の「A」のところにマウスカーソルを置いて時間になったら中クリックする作戦で行ったが、問題一覧へのリンクが出てきて阻止され(それはそう)、問題一覧へ行くのにも少し時間がかかった(さらにそこからA問題を開く)。やはりいつも通り、予めA問題のURLを開いておき、時間になったらF5がいい。

素直なA問題。簡単なわりに1分じゃ終わらない実装量だが、こういうきれいな処理なら気持ちよく書ける。

B - AcCepted

コンテスト中に"WA"の字を見せるのやめろ。

クソむずい。やるだけなんだろうが、問題の設定に必然性がないので、なかなか状況を飲み込めなくてコーディングに入れない。さて、問題を読めたうえでも難しい点があって、3つの条件から「S全体に'C'は1つだけ」が言えるかすぐには確信が持てなかった。'A'と'C'を小文字に置き換えるなどすれば3つめの条件も明快になると思っていたが、さすがにそこまではせず、わりとじっくり時間をかけてAC。大文字と小文字では小文字のほうが大きいという小さな罠があった(ちゃんとそれを疑えるだけの知識はあった)。

C - All Green

Dが10以下と気づくのに3分くらいかかった。制約を見てなかったというよりは、問題を読むのにそのくらい時間がかかった。「AtCoderの問題なら10000点問題とか無茶苦茶なのも出てくるだろう」という思い込みによりD<=10の制約に気づかない、みたいなのはありそう。さて、100じゃなくて10だというのなら、2^10通りを全探索で簡単だ。ここは何も考えず、ビットが立っていないところではコンプリートボーナスを必ず回避するようにする。点数と問題数の2つがあってややこしいが、点数が高いほうが有利なので配点の高い順に貪欲に取っていく。Gに達したら終わり。問題数を記録する。境界が怖いのでGを100で割るようなことはしなかった。intに収まるか不安でllを使いかけたが、どうせ早解きできる流れじゃないし、ちゃんと考えてintにした。

ここで方針が見えてからこれだけ時間を食うのは、自分の実装力に危機感を覚える。

D - We Love ABC

難しい。時間が経つだけなので、とりあえず?がない場合を解いてみる(この問題はちゃんとサブセットになっている)。左から見ていってまずAを見つけて次にBを、ってその時点でTLEやんけ。3つなので、AとCで挟むイメージで。いやそれもダメ。各Bに注目して左のAの数と右のCの数の積だ!

さて?の扱い。3^Q通りあるのがけっこう怖い。あるBを基準にして、Bというか、ある位置がBになるとき左右のAとCと?の個数がわかればよさそう。まず?同士でAとCのペアを作ることを考える。左に?が3個あったとしてAの個数は0,1,1,1,2,2,2,3が考えられる。んで右に?が2個なら0,1,1,2でその積たちは長方形タイルで考えると普通に和の積でいい。?とCで作るペアもできそう。具体的には難しいが、なんとか考える。あ、でもこれ残りの?が色々なのでダメですね。3^Qどこ行ったと思って気づいた。

「1時間かかるかも」から「1時間では終わらない」「ひょっとして解けない」まで考え始める。B問題やC問題でもっとスピードを出していればとか考え始める。パッと解けないのは悔しいがこういう問題を1時間とか考えられるのは嬉しい。嬉しいは変だな。悔しいけどいいことだ。

さっきの考察の雰囲気(細かい積の和が、和の積で求まる)でもそうだけど、期待値的な考え方で行けそうな気がずっとしてた。もう解けないのでその方向でなりふり構わずに行く。?の1/3がAになるのでmod 10^9+7で3の逆数を求め掛ける。?の個数が3の倍数じゃなくでもいいのかよと思うが、3^(?の個数)は3の倍数なので延べ通り数で言えばきっちり1/3になってるというか。雰囲気的にいけそうなやつを書くと行けた。?をBにしたときは、そこを固定したので3^(Q-1)通りの中でやることに注意。最後は掛け算の途中でmodとるの忘れてサンプルが通らなかったりした(苦戦したときのいつもの)。コーディングスタイルが昨日のコンテストに引きずられてる(p['A']で左にあるAの個数を取得してた)。

思ったより問題の懐が深いということがあるので、もっと恐怖心を持つべきだと思った。

そしてブログの投稿時刻もばっこりTLEしていく(いつもはABC終了直後)。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/merom686/20180805/1533480831