Hewlaの競プロ記

競プロ記です。

Colorful Subsequence - AtCoder Grand Contest 031 A

AGC031-A, 200点でした。
問題リンク

解説

重要な点として、

  • 部分列は全て異なる文字からならねばならない
  • 文字列として同一でも、異なる位置から取り出された部分列は区別して数える

ということがあります。
僕は問題文の勘違いもあってかなり迷走しましたが、結局、

  • 各アルファベットは1回しか現れられない
  • 異なる位置にある同じアルファベットを選んだ文字列同士は区別して数えられる

ので、
例えば'a'がS中にk回現れたとすると、'a'については

  • 部分列に一つも含まれない
  • 部分列にi番目の'a'が含まれる(1 \leqq i \leqq k)

ので、'a'の選び方はk+1パターンあるわけです。

各アルファベットについて、(その個数+1の積)-1が答えになります。
(最後に-1する理由ですが、この方法だと全てのアルファベットが一つも部分列に含まれない場合、つまりからの文字列となる場合を1つだけ含むからです。)

An Ordinary Game - AtCoder Regular Contest 064 D -

ARC064-D、500点。解き心地の良い問題でした。

問題リンク

考察の流れ

わからないのでとりあえず手を動かしてみます。
話をすっ飛ばして、手を動かした結果わかったことをここに書きます。

  • 文字列の両端の文字は消すことができないので、ゲーム開始前とゲーム終了時の文字列で両端の文字は変わりません。
  • 終了時の文字列は必ず1種類または2種類の文字から構成されています。(それ以上含むと必ずまだ消せる文字があることは実験するとなんとなくわかると思います)(証明は3種類目の文字周辺の状態を全て列挙することでできると思います)

この二つのことから

  • sの両端の文字が同じ → 終了時の文字列の長さは奇数 (abab...aba のようになります)
  • sの両端の文字が異なる → 終了時の文字列の長さは偶数 (abab..ab のようになります)

ということが言えます。
これを用いると文字列の長さの減りの偶奇がわかるので、最終状態に至るまでの操作回数の偶奇がわかります。
偶数回の操作をして最終状態に至れば青木君の、奇数回ならば高橋君の勝利となるので、要するに「sの両端の文字」「最初のsの文字数」からどちらが勝つか判定できるわけです。

僕の場合は真面目に頭を使って計算するよりも、入出力例と自分で作ったサンプルケースに前述の考察を当てはめて適当に考える方が早いし楽だったのでそうしました。あんまりよくないかも

結果です。
f:id:hewla:20190306222747p:plain
こういうのってどれぐらい簡潔に書くか、どれぐらい親切に書くかちょっと悩みますよね

ソースコード

bool found[26];
long cnt;
std::string s;

int main(){
    std::cin >> s;
    long same = (s[0] == s[s.length() - 1]);
    long even = s.length() % 2;
    if((same + even) % 2){
        printf("First\n");
    }else{
        printf("Second\n");
    }
    return 0;
}
  

感想

こういう感じの問題はわからなかったらとりあえず手を動かすことにしています。
どちらかというと、サンプルを眺めたり手を動かしたりしながら全てのケースに共通する法則を探してる感じがします。

ところで、2人が別に最適な戦略を取らなくても、どうやっても最終的に勝つ人が決まっているのって面白くないですか。

参加記 「みんなのプロコン 2019」

悪くはなかったけど良くもなかった

A - Anti-Adjacency

adjacent /ədʒéɪs(ə)nt/ (形) 隣接した
A問題最難問かと思ったけど良く読んだらそんなことはなかった 端から1つ飛ばしに選んでいけばいいですね
Submission #4204200 - Yahoo Programming Contest 2019

B - Path

オイラーが証明したやつだーって思いました。木構造っていう制約が付いているので構造は2パターンしかなくて、一本道かウニみたいになってるかのどちらかです。for文の中身をうっかりミスってWAを産みました。5分は大きかったなあ
Submission #4206209 - Yahoo Programming Contest 2019

C - When I hit my pocket...

ポケットを叩くとビスケットがひとつってやつですね。これ砕けるからやろってずっと思ってました。Cookie Clickerにも通ずるところがありそうですが、これってもしかして共通の文脈があるんですかね
O(1)なので解いてる時の感覚は完全に200点とか100点をやってる時のそれでした。でもやっぱり簡単ではなかったですね。100とか200にこれがあったらびっくりする
Submission #4208905 - Yahoo Programming Contest 2019

D - Ears

すぬけ君にひどいことしないで
何気に「数直線上を連続的に散歩」とかも面白いですよね。
情報をうまく吸い出して簡略化していく部分はうまくできたと思います。途中「偶数回でもいいのは両端の1つだけ」だと思ってた時間もありましたが、しばらくして気づけました。
問題はその後で、DPに気付けなかったのが本当に良くなかったです。「DPをやるとうまくいく場合の感覚」みたいな定跡力が完全に抜け落ちていました。
解説ACです。
Submission #4218697 - Yahoo Programming Contest 2019

まとめ

Hewlaさんの「みんなのプロコン 2019」での成績:647位
レーティング:1605→1612 (+7) :)
Highestを更新しました! https://atcoder.jp/users/Hewla/history/share/yahoo-procon2019-qual?lang=ja
f:id:hewla:20190210002656p:plain
前回の日経コンでしれっと青になっていました。そして水色落ち回避、微増です。自分の実力を鑑みると絶対水色落ちすると思ってたのでこの結果は喜ぶべきなんだと思うのですが、Bの1WAとかDのDPを落とすとか悔しいポイントがたくさんあるのであんまり嬉しくないです。だってD通してたら黄色パフォもありえたわけですから...
次回はいつになるかわかりませんが、頑張ります。

青になるまでやったこと記事は受験がひと段落した時にもしまだ青だったら執筆しようと思います。

When I hit my pocket... - AtCoder 「みんなのプロコン 2019」 C

400点。慎重にやります。
問題リンク

解説

ポッケを永遠に叩いていても1枚ずつしか増えませんが、A枚のビスケットを1円にして1円でB枚のビスケットを買ってくれば2回の操作でB-A枚増やすことができます。どっちがお得かな、というふうに考えたらいいと思います。あとは場合分け。

まず、ビスケットを一枚も換金しない/できない場合について。

  • A-1 >= K (ビスケットを換金できない)
  • B-A <= 2 (ビスケットを換金するよりポッケを叩いたほうがいい)

の場合に答えが

  • K+1

になります。

A枚のビスケットをB枚に変えるためには2回の操作が必要です。K回目の操作でうっかりビスケットをお金に変えてしまうと損なので、所持枚数がA枚に到達した時点での残り操作回数 K - (A - 1) の偶奇による場合分けが必要です。

  • 偶数の時 A + (K-A+1) / 2 * (B-A)
  • 奇数の時 A + (K-A) / 2 * (B-A) + 1

補足説明をすると、
偶数の時 A枚集めた後、クッキーを(K-A+1)/2回 (B-A)枚ずつ増やす
奇数の時 A枚集めた後、クッキーを(K-A)/2回 (B-A)枚ずつ増やし、一回ポッケを叩く
という立式です。

Cookie Clickerって意外と時間溶けるんですよね

Restore the Tree - AtCoder 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 D

500点です。
問題リンク

結局何を求めればいいのかの考察はすぐ終わりましたが、それをどう実装するのかでそれなりに詰まりました。

解説

 「子孫へ有向辺を引く」とあります。このことから、新しい辺を引くことによって、根からその頂点への最短距離は短くなった、ということが言えます。つまり、各頂点への最長経路で通る辺が元の木というわけです。

 これを実装します。トポロジカルソートを用いた解法がわかりやすくてよいと聞きましたが、今回は自分が採用したBFS(幅優先探索)を用いた解法を解説します。トポロジカルソートは名前しか知りませんでした。

 最長経路の探索はよくわかりませんが、最短経路ならできます。辺に重みがないのでBFSをしてやればよいですね。そこで、BFSをして、見つかった最短経路の辺を消していくことを考えます。
 頂点によっては親が複数いるわけですが、本来親は1つだけなので、この親のうち一番頂点から遠いものから伸びている辺だけ残し、残りの辺を消して仕舞えばいいです。

 BFSの実装方針です。BFSなので、根からの距離が短い経路から順にわかっていきます。根からBFSを行ってある親からある頂点に到達した時、

  • その頂点の親が他にあれば、今通ってきた親を「その頂点の親リスト」から消す。BFSのqueueへのpushは行わない
  • 他に親がなければ今通ってきた親は真の親である。その頂点をBFSのqueueにpushする

 「pushを行わない」という部分は重要で、これを行わなければ同じ頂点からの探索を何度も繰り返すことになり無駄が増えます。僕はこれで計算量が爆発することを全く考えずTLEを出しました。また、最長経路を見つけたいので、最後にその頂点を訪れた時だけpushします。この点でも普通のBFSとは異なります。

Different Strokes - AtCoder 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 C

400点
問題リンク

考察の流れ

 2人分の得点について考えるのは面倒なので、得点を1種類のみにしてやりたいです。最終的に出力するのは「高橋くんの点数 - 青木さんの点数」なので、この点数についてずっと考えてやると良さそうです。

 こういう問題は、僕の場合はまず高橋くんの料理の選び方から考えていきます。
 高橋くんが料理iを選ぶと何が起こるでしょうか。高橋くんはa_i点得ますが、同時に青木さんはb_i点を失うというふうに考えてみます。高橋くんは、a_i + b_iが大きい料理から順にとっていくと良さそうな気がします。高橋くんが料理iを選ぶと、高橋くんと青木さんの点数の差はa_i + b_i大きくなるというわけです。すると、青木さんが料理を選ぶルールも同様で、この点数が大きい順にとっていきます。こうすることで、aとbの2種類あった点数が1種類に収まりました。
 このように考えるならば、初めは青木さんが全ての料理を持っていて、それから1ターンおきに高橋くんが料理を奪っていく、というふうに考えるとよさそうです。高橋くんはa_i + b_iが大きい料理から順にとっていきますが、同時に青木さんも同じルールで自分の料理を選んでいくので、高橋くんは実際には奇数番目にa_i + b_iが大きい料理を選ぶことができます。
 
 もちろん逆でも構いません。高橋くんが全ての料理を独り占めしていて、それを青木さんが奪っていくタイプのプログラムでもいいと思います。僕はこちらでやりました。

Double Landscape -AtCoder KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019 D-

500点です。
問題リンクを貼っておきます。
D - Double Landscape

簡潔な解説は公式のものがわかりやすいので、ここには冗長な思考過程を書いていこうと思います。

考察の流れ

テストケースがややこしいやつと貧弱なやつしかないので、手元で手頃なやつを生成します。
f:id:hewla:20190113235812j:plain
とりあえず手元で考えてみようということで、こんな図を描きました。
丸で囲まれた数字は、そのマスにこの数字が入ることが確定していることを表します。
細長い丸とその脇に書かれた小さい数字は、この数字の入るマスの候補はこの範囲だということを示しています。

もしかして、この細長い丸はお互いに重複することがないのではないか?と考えます。
ここで落ち着いて、細長い丸を描くときのルールを考えてみます。
上側に並んでいる数字をa[i]、左側に並んでいる数字をb[j]とすると、f:id:hewla:20190114000927j:plain
(i, j)のマスは
a[i] < b[j]の場合は縦に細長い丸に、
a[i] > b[j]の場合は横の細長い丸に入る可能性があるようです。

すると、a[i] < b[j]とa[i] > b[j]は同時に成立しないので、一つのマスは縦横の丸に重複して含まれることがありません。これでだいぶ考えるのが楽になりました。重複していると、その重複しているマスに数字が入る場合/入らない場合についてそれぞれ考えなければいけないので、ややこしくなってしまう気がします。
また、わかりやすいように上と横に並んでいる数字をソートしても答えは変わらないようです。

f:id:hewla:20190114001402j:plain
細長い丸は見にくいので細長い棒になりました。
わかりやすくなってきました。

ややこしかった入出力例4もExcelに突っ込んで図を描いてもらいましょう。
ちょっとだけ線の引き方のルールが変わっちゃてますが気にしないでください。先ほどは位置が確定した行/列には空白のマスがありましたが今回は気にしていません。
f:id:hewla:20190114001723p:plain
こうなると線の引かれ方のルールもかなりわかりやすいですね。
先ほど式で表したルールを考えるとこのようになるのは当然なのですが、僕は図にしないとやっぱりピンとこないなと思いました。

この図を見ながら考えます。
グリッドを1からN*Mの数字で重複がないように埋めていくわけですが、この数字は3つのグループに分けることができます。

  1. 縦横どちらにも数字が載っているので、入るマスが決まるもの
  2. 縦横のどちらかに数字が載っているので、入る行/列が決まるもの
  3. 縦横のどちらにも数字が載っていないので、各行/列の最大値を超えない範囲でどこにも入れるもの

です。

大きい数字は入るマスが決まりやすそうなので、大きい数字から順番に考えていきます。
答えを格納する変数ansを1で初期化して用意しておきます。

182や179などはグループ1に属します。これらは位置が確定しているので、ansの値は変わりません。

177はグループ2です。入る行が確定しています。
f:id:hewla:20190114002705p:plain
この写真で青く囲った部分です。この場合はansに5をかけます。

174はこの図にはいません。グループ3です。ということは、各行/列の最大値を超えない範囲ではどこにでも入れます。
f:id:hewla:20190114002938p:plain
この青く囲った範囲に入ることができます。
この場合はansに7*8を掛ければいいと思いそうになりますが、そうではありません。
この範囲にはすでに175から182が入っているからです。
これらの数字を入れた上で174が入れるマスはいくつあるか、ということを考えなければならないので、ansには7*8 - (182 - 175 + 1)を掛けます。

これで、各数字についてどういう操作をすれば答えが求まるかを考えることができました。

実装について

簡単に述べます。僕の実装はO(NM(logN + logM))です。解説にはO(NM)とあったので改善できるのだと思いますが僕にはわかりませんでしたorz

  • ある数字が上/左に存在しているかどうかを素早く確認できる
  • ある数字以上の数字のうち、最小のものが何番目かを素早く確認できる

という特性を備えたデータ構造が望ましいような気がします。
僕はstd::set<pair<int, int> >を使いました。firstには並んでいる数字の値、secondにはその数字が何番目のものなのかを保管しておきます。
その上でlower_boundを使うと上記の操作が行えます。

僕のレベルではこれが精一杯でした
僕は#define int longをしているので、このコードをそのまま貼り付けるとintのせいで通らないことがありえます。

lower_boundがend()を返す場合についての処理が抜けていて、1WAを生んでしまいました。setを扱うのは僕には難しいです。慣れたいですね。

誤りの指摘や質問等あれば僕のTwitterやコメントまでよろしくお願いします。