Programmer's Playground

プログラミング周りでやりたいことをやる

AtCoder ABC132 参戦記

AtCoder の ABC 132 に参戦しました。

atcoder.jp

結果は 35 分弱で ABCD まで解けてパフォーマンスは 1496。E 問題が解けなかったわりにはパフォーマンスは伸びましたがまたしても水色落ちとなりました。

f:id:y_r:20190629235615p:plain

感想

A 問題

A 問題史上最難?if 文で比較するのも面倒だったので、各文字の出現回数をカウントして 0, 2 以外が出たら NG とした。

B 問題

単純に for ループ回すだけ。
A より簡単では...?

C 問題

ソートして  d_{n/2 + 1} -  d_{n/2} が答え。

D 問題

めんどくさい数え上げだが Red の数を  kr  (= n - k)、分割数を  i とおくと、

  • 分割数が  kr + 1 を超えてしまうと実現不能なので組み合わせ数は 0
  • Blue を分割する組み合わせ数 x それを可能にする Red の配置の組み合わせ数を [t]x: i] について出力する
  • Blue を分割する組み合わせ数は  _{k - 1}C_{i - 1}
  • Red の配置の組み合わせはめんどくさいが、 i - 1 個が拘束されていることを利用すると  kr - i + 1 個のボールを  i + 1 個の箱に分配する問題になって  _{kr + 1}C_{kr - i + 1}
  • nCk の計算が間に合わないと予想されるので階乗を前計算する。それを使って  nCk = n!/(k!*(n-k)! を高速に求める。(逆元はその都度求めたがこれも用意すればさらに早い)
E 問題

コンテスト中は3 hop 先への有向グラフを構築しようとして TLE が取れなかった。
最終的に AC した考え方は以下の通り。

  • ダイクストラ法がベース
  • ダイクストラ法だと一度到達した頂点からは探索しないが、本問題では S からの到達を  d とすると  d % 3 で到達したことがあればその頂点からは探索しない
F 問題

たぶん DP, きっと DP

AtCoder ABC 131 参戦記

AtCoder の ABC 131 に参戦しました。

atcoder.jp


結果は 40 分弱で ABCDE まで解けてパフォーマンスは 1837。青色復帰となりました。
酒が結構 *1 入っている状態でしたが、それほど致命的なミスはなくまずまずな結果でした。
まあたいていのミスはエディタさん *2 がすぐに赤線引いてくれるからではありますが...

f:id:y_r:20190622232322p:plain

感想

A 問題

瞬殺

B 問題

ちょい実装多め。

  •  l < 0 : 合計値 - l
  •  n + l - 1 < 0 : 合計値 - (n + l - 1)
  • それ以外 : 0 が含まれるので合計値が答え

なのだが手元で実装ミスを繰り返して時間消費した...実は素直に 2 重ループ書いたほうが手早かったかも...

C 問題
  •  count(n, x, y) n 以下の整数のうち  x でも  y でも割り切れない数とすると、答えは  cout(b, c, d) - count(a - 1, c, d)
  • count(n, x, y) の求め方は  n - (n/x + n/y - n/gcd(x,y))

だが、ここでも手元での WA を取るのに時間がかかる

D 問題

B でソート一発。あとは順に A を足していって B を超えないかを見るだけ。B 問題、C 問題より早くできた。

E 問題
  • 明らかに最大数は  1 を中心として残りの  n - 1 個に辺を張ったとき
  • あとは 1 本辺を足すたびに 1 ずつ減る

のでこれを構築。

F 問題
  • (正) ちょうど 3 箇所に点が存在するような整数を選び残りの 1 箇所に点を追加
  • (誤) ちょうど 3 箇所に点が存在するような整数を選び <それらの点を消して> 残りの 1 箇所に点を追加

の読み間違いをやらかしたまま残り 2 分で実装完。手元で動かしてサンプルを見ると答えが最初の整数の数以上だったので ??? となり、もう一度問題文を読み直して読み間違いに気が付いて魂が消えたままタイムアップ...

*1:ビール 1 杯と日本酒 1.5 合

*2:Visual Studio

AtCoder ABC 130 参戦記

AtCoder の ABC 130 に参戦しました。

結果は 26 分で ABCD 4 完 (ただし 3WA : しかもつまらないミス) で E 問題が解けず...パフォーマンスも 1371 で伸びずレートも下がってしまいました。
次のコンテストで青色挑戦は少し厳しそうです。ただ、よく考えると数回前のレートは水色ぎりぎりだったので、パフォーマンス 1371 でがっかりするのは自分の中で要求水準が上がっただけのような...

f:id:y_r:20190622172546p:plain

感想

A 問題、B 問題

瞬殺

C 問題

一瞬ウッとなったがよく考えると長方形は確実に 2 分できる。さらに複数の分割法があるのは長方形の中心を選んだときのみ。
...なのだが

  • 長方形の面積の半分の計算を (int * int) / 2 でやって 1 WA
  • (x, y) が (w, h) の半分かを計算するときに (int / 2) でやって 1 WA

の 2 WA をくらう。

D 問題
  •  a_i を先頭にしたときに  a_j まで来たときに  K 以上になるなら  a_i が先頭になる組み合わせは  N - j - 1
  •  a_i + 1 先頭の時はあきらかにすでに足した値をもう一度足すのは無駄なのでしゃくとり法で処理

あとはこれを実装するのみ

E 問題

適当な DP をやってしまい手元で WA にしかならずにギブアップ。
コンテスト後 1 週間かけて考えたあげく、以下のようにすればよいことに気が付く。

求める値を  dp[i][j] とすると、この値は以下の和。

  •  dp[i][j-1]
    •  (i, j - 1) までの値をそのまま転写。 (i, j) は取らない。
  •  s[i] == t[i] の場合  dp[i-1][j-1] そうでない場合  0
    •  (i,j) を取る場合の数
  •  dp[i - 1][j] - dp[i - 1][j - 1]
    •  (i, j) を取らない場合の残りの値を足す。上記の値は  i - 1 列の計算中  (i - 1, j) で追加された値になるので、この値を足すべきであり、また足しても 2 重カウントされない

AtCoder diverta 2019 Programming Contest 2 参戦記

AtCoder の diverta 2019 Programming Contest 2 に参戦しました。

atcoder.jp


結果は ABC (1WA) を早解きして 424 位。D 問題に 1 時間半かけて解けなかったのは悔しいです。(なお +20 分で AC しました。)
パフォーマンスのほうはまずまずで 1819。レーティングはぎりぎり青復帰ならずです。

f:id:y_r:20190615235659p:plain

感想

A 問題

瞬殺した...はずだがまさかの WA。原因は他のコンテストの回答をなげていたため。

B 問題

n = 50 なので 4 重ループがまわせる。

  1. すべての点の組から p, q を求める 2 重ループ
  2. すべての点から p, q 先に点がある (あればスコアを -- できる) のをチェックする 2 重ループ

の 4 重ループをまわして AC

C 問題
  • まずソートする
  •  [a_2, a_{n-1}] の数に関して
    • マイナスならば  a_n にマイナスする
    • プラスならば  a_1 にマイナスする
  • 最後は  a_n - a_1

が最大値を構成する。

D 問題

最初の考察であっていたのは

  • B 地点でぜんぶどんぐりに変えるのが最善

のみ。最初は A, B で 1 種類しか金属に交換しない方法で当然ながら WA。以下のように実装をかえつつ粘ったがAC できたのはコンテスト終了後...さらに当然のごとく実装行数がかさんでるので、もっといい方法があるはず。

  • 3 種類の金属をうまく組み合わせれば最大になる -> 金と銀 (銅は移動先との価値比に応じて全ぶっぱ or 交換なし) に関する 2 重ループを実装して TLE。
  • 移動地点先の交換価が低い金属を交換しても無駄なので考慮しない -> TLE
    • B -> A の戻りで最大  (5000 * 5000)^2 ぐらいのループになる
  • B -> A は A -> B で交換できる金属の種類数に応じて最適化できる
    • A -> B で交換できない : B -> A でのループは  5000^2 なので A -> B と同じ計算
    • A -> B で 1 種類交換 : B -> A は 2 種類交換。全ループすると TLE なので以下の工夫をする
      • B でのどんぐり数を  n, 1 種類目の価値を  p1, 2 種類目の価値を  p2 とすると探索するのは  0 <= i * p1 <=p1 * p2 の間と  (n - p1 * p2 - p1 + 1) <=  i * p1 <= n の間でよいのでここに限って探索する
    • A -> B で 2 種類交換 : B -> A は 1 種類交換。全ぶっぱすればよい
    • A -> B で 3 種類交換 : B -> A は交換できないのでパススルー *1
  • これで AC

*1:最初の AC はこの考察が抜けてた

シェルスクリプトこう書いた

備忘録的に

乱数を生成して C の uint8_t 配列にしたい
$ openssl rand -hex 16 | fold -2 | awk '{print "0x"$0}' | tr "\n" "," | awk '{print "{"substr($0,0,(length($0)+1)-1)"}"}'

=> {0x94,0xdb,0xb4,0xaa,0xd2,0xda,0xc3,0x96,0xaf,0x98,0x74,0x46,0x95,0x47,

AtCoder AGC034 参戦記

AtCoder の AGC034 に参戦しました。

atcoder.jp

結果は A (1WA) のみ取れて 1377 位。パフォーマンスは当然伸びず 1096 であえなく水色に叩き落されました。

f:id:y_r:20190603000147p:plain

感想

A 問題
  • まずは A -> C, B -> D の遷移の可否を判定
  • D < C の場合、飛び越せるか判定。[B - 1, D + 1] で連続 3 個空白があればよい...が実装ミスにより [B - 1, D + 1) で判定して WA

かなり早く解け、1 WA あったもののこれによりパフォーマンスへの致命傷は避けられた。

B 問題

痛恨の考察ミス。BC -> X より置換だから A が端に寄って行くのに気が付いていなかったのが致命的。
愚直解を投げて TLE をくらい、その改善をしたところ WA が取れないところでタイムアップ。

C 問題

見てない、けど解いたほうがよい。

AtCoder M-SOLUTIONS プロコンオープン 参戦記

AtCoder の M-SOLUTIONS プロコンオープン に参戦しました。

atcoder.jp

結果は ABCE (1 WA) を取って 144 位。パフォーマンスも調子よく 2210 となりました。レーティングは爆上げで 1616 となり青色になりました。今年中に青色になれればいいなぐらいに思っていたのですが、想定外の伸び方です。
確かに始める前に前回のパフォーマンス (2332) 付近を取れば青色に手が届くというのはちらっと頭に思いうかんではいたのですが、まさか本当に取れてしまうとは...

f:id:y_r:20190601235316p:plain

今回取れた C, E はいずれも剰余の中での割り算が絡むので、

yrdev.hatenablog.com

で、 「mod の計算にちょっと強くなった気がする」といったのが実証できました。

感想

A 問題 B 問題

瞬殺

C 問題
  • 引き分けは決着を引き延ばす効果しかないのでまずは引き分けを除いて考えてよい
    • 引き分けの確率を  p とすると、最後に  1/(1 - p) を掛ければよい
    • 引き分けを考えない状態で A が勝つ確率を  q とする
  • A が最終勝利するには n 回勝つまでに B が  n - 1 回しか勝たなければよい
    • B が勝つ回数を  m (< n) とすると、この状態で決着する確率は  _{(n + m - 1)}C_mq^n(q-1)^m となる
    • 上記を  0 <= m < n ですべて足す。
  •  _{(n + m)}C_m をその都度求めていたら TLE するはずなので、  _{n-1}C_0 = 1,  _{(k+1)}C_l = _kC_{ l - 1} を利用して  (n - 1) <= k < 2n まであらかじめ計算しておく
  • B が最終勝利する確率も同じように求めれれる

でこれを愚直に実装すればよい。

D 問題

最初

  • 値をソートして辺の数が少ない頂点から割り付ける

を実装して WA をくらったので後回しにした。 C, E を解いてから

  • 木構造の中央から高い値を割り付ける

という方針に変えて (とはいえこの考察があっているかは未検証) 実装しようとしたがバグが取り切れなかった。

E 問題

Wikipedia 先生 等差数列 - Wikipedia に答えが書いてある。
 (x/d)^{\overline{n}} の計算は一見難しそうだが剰余上での演算なので、  x/d から n 個掛けた数を求めればよい。 x/d s とすると、 factorial(s + n - 1) / factorial(s - 1) で求まる。
ただし以下のコーナーケースに気を付けること。

  •  s + n - 1 が大きすぎると答えは 0 になる
    • 1000000007 の倍数になる (= 剰余が 0)
    • 閾値 1000000007 <=(s + n - 1)
  •  d = 0 のときは答えは  x^n
F 問題

見てもいない