ABC257参加記

競技プログラミング

お久しぶりです。

リアルの方も落ち着いたので、abc257に参加しました。

A問題

(問題URL) :

atcoder.jp

ポイント

  • 何番目の文字が書かれたボールが取られるかを考える
  • 整数の切り上げ
  • アスキーコード表

まず、入出力例から、何番目の文字が書かれたボールが取られるかを考えてみましょう。

例1

2 12

これは、入力例2と同じものです。これによって得られる文字列はAABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZになるので、答えはFとなります。

これを数字を使って考えてみると、単純にXをNで割った商は12 / 2で６になります。これはAを1番目とすると、ちょうど6個後がFになります。

例2

2 13

これによって得られる文字列は例1と同じく、AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZになり、答えはGとなります。

これを数字を使って考えてみると、はAを1番目とすると、ちょうど7個後がGになりるので、XをNで割った商が7になればいいのですが、実際は13 / 2で６になります。これより、XをNで割った商を切り上げれば良さそうです。 A/Bの切り上げは(A+B-1)/Bでできるため、XをNで割った商の切り上げは(X+N-1)/Nで求めることができます。

次にAを1番目としたときに、ちょうどN個後のアルファベットを取得する方法ですが、C++では、英大文字はアスキーコード上で連続しています。(参考: https://e-words.jp/p/r-ascii.html)

そのため、'A'-1+Nとすることで、次にAを1番目としたときに、ちょうどN個後のアルファベットを取得することができます。

(提出URL) : https://atcoder.jp/contests/abc257/submissions/32715222

B問題

(問題URL) :

atcoder.jp

ポイント

  • ユニークな値を格納するデータ構造

この問題では、各クエリごとに現在いるマスの一つ右に他のコマがあるかどうかを調べ、なかったときには移動する必要があります。

幸いにも、今回はマス数も、クエリ数も小さいため、愚直に一つ右にi番目のコマが無いか...というようにして調べていくこともできますが、C++のsetというデータ構造を使うことに高速に求めることができます*1。

C++のsetは、同一の値を最大1まで格納することができるデーターであり、大きく分けて次に3つの機能があります。

  • insert(a) : aという値を追加する
  • find(a) : aという値があるか探索する、(name).end()が出れば存在せず、それ以外の値が出れば、存在する。
  • erase(a) : aという値を削除する。

これを使うと、次のように実装することができます。

  1. i番目のコマがある位置を格納する配列:A,コマがある位置を格納するset:dictを準備する
  2. Aに値を格納しながら、A[i]をdictを追加する。
  3. 各クエリごとにA[L[i]]!=Nかつ、dictにA[L[i]]+1が存在しなければ、つぎを行う:
    1. dictにA[L[i]]+1を追加する
    2. A[L[i]]を1加算する
    3. dictからA[L[i]]を削除する
  4. Aの各要素を出力する

(提出URL) : https://atcoder.jp/contests/abc257/submissions/32720667

note : insertにも、追加が成功したかの真偽値が帰るため、もっと簡略に書くことができます。

C問題

(問題URL) : atcoder.jp

ポイント

  • 単調に直して考える
  • 端の結果を固定する

この問題では、しきい値:Xを決め、W[i] >= Xの結果ができるだけS[i]になるように決める必要があります。しかし、愚直に実装すると、1つのXに対して判定がO(N)になるので、合計の計算量はO(N2)となり、間に合いません。

しかし、今回はXを増加するとき、Xが変化するときに大小関係が変わらないWについては結果が変わらないので、Wを小さい順にソートして、XをWの小さい順に変更します。

すると、f(X)は次のように遷移します。

  • X=min(W) のとき　... f(X)= #(S|S_i==0) (#(A)はAの要素数)　
  • X=w[i] -> w[i+1] と変更した時、(wはWを昇順にソートしたもの) ... f(X)= f(w[i]) + 1 (s[i]=0のとき), f(w[i])- 1 (s[i]==1のとき)

そうすると、XがWの要素を取る時、f(X)はO(N)で求めることができるので、(これをしゃくとり法といいます)あとはf(X)の最大値を取ればOKです。

note　実際はWの値が同じである場合があるため、mapなどを使って同じ値をまとめると便利です。

(提出URL) : https://atcoder.jp/contests/abc257/submissions/32730259

(これ以降は解けなかったので、考えたことを羅列しておきます)

D問題

(問題URL) :

atcoder.jp

考えたこと

i->jを重みマンハッタン距離(i,j)/P_iの切り上げの重みではられたグラフである頂点から初めてすべての頂点に行くまでの通る必要ある重みの最小値を求める問題、

当初はグラフの重みが無向辺ではられると勘違いしてしまい、クラシカル法で実装したが、WAが出て解決策が思いつかず、パス。コンテスト終了後に読み間違えが発覚kする

E問題

(問題URL) :

atcoder.jp

考えたこと

X=0の状態から$C_i$を払って"X"iにする動作を最大N円でどこまで大きくできるかを求める問題。

桁数をできるだけ大きくしたいので、Cの最小値で染め上げて、残りはCの最小値のインデックスよりも大きくなるCを選んで変更することを考えたが、WA.結局そのまま時間切れ

コンテストを通して

(コンテスト中の提出):

atcoder.jp

最終的に、A+B+Cの600点の57:10+2WAで2510位のperf932でした...

1年近くのブランクがあるのでそんなもんだろうと思います。

また、その間にパソコンを買い替えたのでライブラリの以降が済んでいなかったので、ライブラリの移行を急ぎたいです。

また、自分が趣味で作っている、ブラウザを開かずにコンテストに参加できるモジュールがなぜか動かなく、また、D問題でコンパイラーの調子が悪かったので、その原因解明をします...

*1:厳密にはO(log N)で求めることができます