notepad.exe

つまり覚え書き

ABC105 D - Candy Distribution

復習日記

ABC105 D - Candy Distribution

ABC105 D - Candy Distribution

均等に配れる飴の個数を取り出す組み合わせの総数を求める問題

最初に、制約から全パターンを試すのは無理(105 * 105)

ということはまずパターンをどうやって少なくするかだが、
これは1番目からi、j番目(i ≦ j)までの和をそれぞれ B_i、B_jとするとi番目からj番目の和は B_j - B_iとあらわすことができる。 そのため先に先頭から累積和をもとめておけばパターンを網羅する計算量を落とすことができる。


次に、 B_i、B_jがMで割り切ることができるのはどのようなときか求める。

当然、 B_i、B_jがどちらもMの倍数であれば割り切ることができる。
B_iがMで割った時に1余る場合B_jがMで割って1余れば B_j - B_iがMで割り切ることができる。 つまりMで割った時にあまりが同じもの同士がlとrの組み合わせの候補となることがわかる。

このことから先に求めておいた累積和の配列を余りが同じ物ごとにまとめて数を数えたのち組み合わせを計算することで最終的な答えを求めることができる。

提出コード

ABC105参加記録

最近のABCはCで苦戦することが多いです(水色らしからぬ発言)

A - AtCoder Crackers

ケーキを均等に分けて差の絶対値を求める。 最大で差が1なのに気づくのが遅れて変なコードを書いてしまいました。
割り切れれば0で割り切れなければ1を出力するだけ。

提出コード

B - Cakes and Donuts

4ドルのケーキと7ドルのドーナッツをNドルで買う組み合わせがあるか。
解説では2重ループする方法でやっていましたが、自分は最初に0~100ドルまでの組み合わせで買うことができるものをすべて求めてしまいました。

提出コード

C - Base -2 Number

Nの-2進数表現を求める。 本番中は手作業で書いて、法則があることはわかりましたがうまくコードに落とせず。

結論は基底が負数であろうと基本的な進数変換とはほとんど変わらないので、同じようなことをすれば求めることができます。

提出コード(終了後)

D - Candy Distribution

本番中はCで苦戦してたので手を出さず。累積和とってmodでまとめるみたいな問題ですね。 D問題なので別記事にまとめます。

社内のプロコンで作った問題と思ったこと

6月に行われた社内のプロコンで初めて問題作成を行いました。 実際に作った問題と問題を作っている中で考えたことをまとめます。

前提条件

問題の作成をする際の条件はこんな感じでした。

  • コンテスト時間は3時間
  • 問題数は5問
  • 問題のレベル感はAtCoder Beginner Contest程度
  • 全体の得点がばらけるように部分点を多く設定する

部分点については最終的には全部の問題で細かく部分点が取れるようにしました。
ここから問題の概要を順番に説明しながら作成中に考えたことを説明していきます。

A - Convert Gengo

和暦(M, T, S, H, X)が与えられるので西暦に直して出力する問題。
Xは未来の新元号です。

これはいわゆるおまけ問題。
ほとんどの人は問題なく解いてくれますが、プログラミングに慣れていない人だと案外引っかかるようで思ってたより時間のかかる人もいました。この問題では元号ごとに部分点が入るようにしていて、ジャッジ結果から実装ミスの予想もできるような最終的にものすごいおまけの部分点になりました。

B - GCP

GCPの3種類の文字から構成される文字列の中で特定の文字列があれば消していき、最終的な長さを求めてくださいというような問題。(ちなみにGCPは「ぐー」「ちょき」「ぱー」の頭文字)
この問題はとある問題を参考にして難易度を上げました(AtCoderの問題をたくさん解いている人なら心あたりがあるかも?)

この問題は実はあまり作るときに悩まなかった問題。for文で回して部分点をとれるのとstackを使わないと満点をとれない2段階に分けただけでした。 この問題の基本的な考え方が、 f:id:mosmos_21:20180810224821p:plain
このような感じで見つかるまで参照をずらして対象の文字列が見つかったら、 削除 → 文字列を詰める → 参照を一つだけ戻して再度探索みたいなものを想定していました。

ただ純粋にこれを実装してしまうと時間がかかってしまってTLEするはずなのですが、どうやらC#のリストを使うとこのあたりの問題が解決されているようで、本番で部分点の想定解法で満点を取る人が出てしまいました。

作成側としては検証の対象がC、C++Javaだけなので、他の言語の仕様を知ることができた面白い機会だったと思います。

C - 10+10=23?

ざっくり言うと表記する文字のマッピングも与えられる進数変換をして足し算したものをさらに進数変換する問題。 どうゆうことかと言うと、例えば16進数 → 10進数の表記の変換をすると4e → 78

となりますが、これは16進数を表現する文字が

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F]

と与えられているのでそれを10進数に当てはめて計算することができるからです。 これの文字の順列を、例えば4進数の時に、[0, 1, 2, 3] ではなく [a, b, c, d]で表現されているとすれば、 前者で表現されている312という数値は後者で表現されているdbcと同値ということになります。 この時のN種類の文字列で表現されている数値をN種進数と呼んで、

S(A種進数) + T(B種進数) = ???(C種進数)

という計算をしてもらう問題でした。


解法自体は一般的な進数変換を少し変更するだけで答えを求めることが可能なので実装自体はそこまで難しくないです。これを作っているときに大変だったのが、この定義をいかに正確に問題文に反映させるかでした。 結果としては5問の中で問題文は一番長くなってしまいました。

おそらくそのせいもあって時間内に満点の解法を提出できたのは上位の3名だけでした。 ただ、終わった後に数学科の同期に「ここはどうなんだろうと思ったところが全部問題文にちゃんと定義されていた」と言ってもらえたので個人的には満足でした。

D - Sum of K

問題文は
「A以上かつBより小さい整数の中で、Kの倍数である整数のみを合計した数値を出力してください。」
以上です。

この問題は最初制約を 0 ≦A, B ≦ 3 * 109 にしていたのですがCで検証してみたらまさかの間に合ってしまって 急遽 -3 * 109 ≦A, B ≦ 3 * 109 にしました。そうしたら案の上想定解以外でACする人がいて終わってみてびっくりしました。

この問題の想定解は等差数列の和を求める公式で計算するだけなのですが、 たとえば -100 ~ 200までの和は-100 ~ 100の和が0なので100 ~ 200までの和を求めればいいのでfor文で間に合ってしまうんですね。

検証が甘くなってしまった問題でした。

E - XOOOX

M*Mの盤面でN目ならべをします。i手目で打ったての座標が (x_i, y_i)で与えられるので何手目で決着がついたか求める問題。

この問題だけ割と競プロ感が強い問題になりました(完全に趣味全開で問題を作ったため)。

Mの最大値が105なので配列すらとることができないようにしています。 もちろん部分点は制約がかなり少なく一番小さい部分点ではM = 4固定だったのでfor文で解くことができます。

満点の解法の想定解は同じ色の石が並んでいる部分をUnionFind木で管理してグループごとの大きさを持たせてそれを並んでる数として判定するみたいな感じです。

とはいえ部分点でかなりの点数を取ることが可能なので参加した人はそれを読み取ってもう少し部分点を取りに行ってほしかったなと思いました。

まとめ

問題文の全文と、今回の問題で自分の考えた想定解のソースはこちら GitHub - pgcon6/General

5問作ったまとめとして思ったのが

  • いかに勘違いさせない言葉で問題文を作るか
  • 検証中に問題文、データ、想定解のどこが間違っているのかを探す
  • いかにして点数をばらけさせるか

がかなり難しいということ 1つ目の言葉のチョイスは特にC問題で苦労しました。これは結果としてよかったと言ってもらえたので頑張ったかいがあったと思っています。

2つ目と3つ目は経験を積まないとなかなか難しいのでこれは次回の課題として取り組みます。 特に2つ目は鍛えると問題を解く能力も同時に上がるので一石二鳥でした。 競プロのプレイヤーとしてのスキルもまだまだで質の高い問題を作ることはなかなか難しいですが、 今後の勉強のきっかけとしてはいい機会だったと思います。

次回は11月なのでまた終わったら同じような記事を書きます。

twitterのbotを作りました

javascriptスクレイピングの練習のためにbotを作りました。

botはこちら ばちゃこんお知らせbot

ロジックはrequestで拾ってきたhtmlをcheerio使って解析しているだけ。 作っていて引っかかったのは配列の中に含まれるすべてのURLに対してリクエストをかけるところ。

Promiseチェーンで作るのはいいですが、全部の非同期通信が終わったら次のthenに行くのどうすればいいんだよと悩んでいたところで見つけたのがこれ Promise.all()

要はPromiseの配列を用意して渡してあげるとすべての評価が終わるまで待ってくれる便利な関数でした。
実際に使用している部分は↓ GitHub - vc-summary-bot/index.js

あと追加しようと思っているのが以下のロジック

  • スクレイピングした結果をDBに保存する
  • DBの結果を使って週間ランキングを作る
  • 定期的にサイトを見に行って新しいコンテストが出ていたらツイートする

DBに保存すればサイトを作って過去の結果を公開するもの面白そうですね。

ABC104 D - We Love ABC

解説を見ながら少しでもかみ砕こうとした記録

D - We Love ABC

ABC104 D - We Love ABC

全ての文字列のABC数の合計を求める問題

DPを使って解く
何らかの組み合わせの最大値や総数を10^{9} + 7で割った余りを求めるなどはDPを使う問題と連想できそう

今回の問題でのDPの考え方は「S の先頭から i − 1 文字目までに対する処理(? の置換と丸つけ)をすでに 行っていて、これまでに丸を j 個つけている場合の、S の残りの部分に対する処理を行う方法の個数」で、

  • j < 3で「次に丸を付けるべき文字or?」なら数え終わっている文字の次の文字に組み合わせの数を引き継ぐ
  • j = 3で「?」ならABCのどれでもいいので一つ前の組み合わせに3をかけるそうでなければ前の組み合わせを引き継ぐ

をDPすればよさそう

コード中の計算で

dp[i][j] = dp[i+1][j] * (s.charAt(i) == '?' ? 3L : 1L);

が3つ選び終わっていて今の対象の文字が「?」であればそれまでの組み合わせのすべてに「A, B, C」のいずれかをくっつけれるので3倍するところ。

if(j < 3 && (s.charAt(i) == '?' || s.charAt(i) == "ABC".charAt(j))) {
    dp[i][j] += dp[i+1][j+1];
}

ここが例えば2個つけていたら対象の文字が「A」または「?」のようにABC数を作れるかどうかで加算しているところ。

提出コード(写経しただけ)

ABC104参加記録

久しぶりにCで苦戦した回でした。

AtCoder Beginner Contest 104

A - Rated for Me

どのコンテストでレーティングが変化するか求める問題

  • 1200以下ならABC
  • 2800以下ならARC
  • それ以外ならAGC をif文で書いて出力すると解けます。

提出コード

B - AcCepted

入力された文字列が条件に当てはまるかチェックする問題

  • S の先頭の文字は大文字の A である。
  • S の先頭から 3文字目と末尾から2文字目の間(両端含む)に大文字の C がちょうど1個含まれる。
  • 以上の A , C を除く S のすべての文字は小文字である。

S の先頭の文字は大文字の A である。

この条件は1文字目がAでない時にWAを出力するだけ

S の先頭から 3文字目と末尾から2文字目の間(両端含む)に大文字の C がちょうど1個含まれる。

  • 文字列全体からCを空文字に置き換えたとき
  • 3~(末尾-2)文字目までの中でCを空文字で置き換えたとき

この二つをやってどちらも置き換え前と文字列の長さが1文字だけ違えば途中にCが一つだけあることがわかる。

以上の A , C を除く S のすべての文字は小文字である。

上記二つの条件に当てはまっている段階で先頭にA, それ以外にCが一つだけあることがわかっているので、 この二つを除いた残りが全部小文字であるかループして調べれば答えがでます。

提出コード

C - All Green

解くべき問題を最小にする問題
全部解くとボーナス点がついて処理が増えるので、最初に全部解く点数を決めてしまいます。

全部解く問題の組み合わせは最大でも 2^{10} = 1024通りなので全探索しても問題なさそうです。 全部解くと決めたものの得点をすべて足して点数が足りればその時も問題数を記録します。

すべて足りて点数が足りないときはすべて解くものではないものの中で点数が一番大きいものを何問か解く。 何問か解いて点数が届くのであればその時の問題数を記録する。 もしその点数を全部解いてしまうのであれば別の組み合わせのことを指しているのでこの時は無視します。

上記の二つの条件で記録されている問題数のうち最小のものが答えとなります。

アルゴリズム的にはbit全探索 + Greedyです。 本番中はbit全探索の部分で詰まってしまったので精進不足ですね…

提出コード

D - We Love ABC

本番中にほとんど手を出すことができなかったので省略

勉強会でお話したサイトの紹介

【サポーターズ勉強会】ゼロから始める競技プログラミング

こちらの勉強会でお話したサイトの紹介です
supporterzcolab.com

AtCoder

URL: https://beta.atcoder.jp/

日本語で競プロができる楽しいサービス。

AtCoder Problems

URL: http://beta.kenkoooo.com/atcoder/

AtCoderのコンテストと問題の一覧を見ることができます。
ユーザ名を入力すれば精進の記録として活用できます。

[Qiita] AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~

URL: https://qiita.com/drken/items/fd4e5e3630d0f5859067

何をすればいいかこれを見ればまとまっています。

[Qiita] AtCoder 版!蟻本 (初級編)

URL: https://qiita.com/drken/items/e77685614f3c6bf86f44

上記の記事と合わせて読むといいです。

AIZU ONLINE JUDGE

URL: https://onlinejudge.u-aizu.ac.jp/home

チュートリアルに使うもよし、実装の練習に使うもよしのサイトです。

Hacker Rank

URL: https://www.hackerrank.com/

コースがあるのでそれに沿って勉強できます。