ARC099/ABC101 D - Snuke Numbers
復習日記
D - Snuke Numbers
整数に対して
を
の各桁の和とする
この時、に対して
を満たす
をすぬけ数と呼ぶ
が与えられるのですぬけ数を小さいほうから
個出力する
とりあえずサンプルを見ると1桁の時だけルールが違いそうなので2桁以上を考えてみる。
何となく手計算すると下の方は必ず9になるような気がする。
実際にすぬけ数となる数は1桁目から
(
の桁数)桁目まではすべて9になる。(証明は略)
ただ、dが何桁目なのかは実際に計算してみないとわからないので計算をする。
これを小さいほうから順番に探していけば時間内に答えを求めることができる。
この問題は解説を読んでも理解がふわふわしたままでした。 もう少しいろいろな問題を解いた後にもう一回解きなおします…
ABC106参加記録
相変わらずDが安定しないです。
A - Garden
畑の面積を求める
で終わり
B - 105
１からまでの正の整数で約数がちょうど8個ある奇数の個数を求める
が200までなので愚直に全部やれば間に合います。
C - To Infinity
1日たつと2が22、3が333みたいに増えるので5000兆日後の左からK文字目を求める
5000兆日後は1以外の数字がなんかすごいいっぱい並ぶので元の文字のK文字目までの中に1以外の数字があればそれが答え、
なければ1が答えになります。
D - AtCoder Express 2
列車の走る区間とクエリの区間が複数与えられる。 クエリで与えられた区間の中に走る区間がすべて含まれている列車の個数をそれぞれ調べる。
おそらく事前に累積和とかとっておくんだろうなと考えていましたがうまく実装できず…
累積和の取り方が区間]を走る電車の本数の二次元配列の横をとって、
クエリごとの解を求めるごとに横区間の和を出すやり方でも十分間に合いました。
2次元累積和はあとで実装しなおした時にやってみることにします。
ARC100/ABC102 D - Equal Cut
復習日記
D - Equal Cut
区間を区切った時の和の差が最小になるようにする問題
区間の和については累積和を持っておくことでとある区間の和は簡単に求めることができます。
この問題の答えを求めるときのポイントは真ん中を決め打ちしてから左右をそれぞれ求めるということ。
真ん中が決まってしまえば残りの半分はできるだけ均等に分ければいいのでで位置を求めることができる。
(例えばこれを極端にバランスを悪く切ってしまうとそこの差が大きくなってしまう)
これに加えて真ん中を左から右へずらすと残りの2カ所も必ず左から右へずれる。 この性質を使うと尺取り法で効率よく切る位置を求めることができる。
ここまでわかれば後は実際にシミュレートして最小値を求めることができる。
計算量はになります。
この問題は比較的実装が楽でした。
どこか1カ所を決めれば残りがで求められるので、シミュレートできる性質がこの問題に似ている気がします。
ABC062 C - Chocolate Bar
ABC105 D - Candy Distribution
復習日記
ABC105 D - Candy Distribution
均等に配れる飴の個数を取り出す組み合わせの総数を求める問題
最初に、制約から全パターンを試すのは無理(105 * 105)
ということはまずパターンをどうやって少なくするかだが、
これは1番目からi、j番目(i ≦ j)までの和をそれぞれとするとi番目からj番目の和は
とあらわすことができる。
そのため先に先頭から累積和をもとめておけばパターンを網羅する計算量を落とすことができる。
次に、がMで割り切ることができるのはどのようなときか求める。
当然、がどちらもMの倍数であれば割り切ることができる。
がMで割った時に1余る場合
がMで割って1余れば
がMで割り切ることができる。
つまりMで割った時にあまりが同じもの同士が
の組み合わせの候補となることがわかる。
このことから先に求めておいた累積和の配列を余りが同じ物ごとにまとめて数を数えたのち組み合わせを計算することで最終的な答えを求めることができる。
ABC105参加記録
最近のABCはCで苦戦することが多いです(水色らしからぬ発言)
A - AtCoder Crackers
ケーキを均等に分けて差の絶対値を求める。
最大で差が1なのに気づくのが遅れて変なコードを書いてしまいました。
割り切れれば０で割り切れなければ１を出力するだけ。
B - Cakes and Donuts
4ドルのケーキと7ドルのドーナッツをNドルで買う組み合わせがあるか。
解説では2重ループする方法でやっていましたが、自分は最初に0~100ドルまでの組み合わせで買うことができるものをすべて求めてしまいました。
C - Base -2 Number
Nの-2進数表現を求める。 本番中は手作業で書いて、法則があることはわかりましたがうまくコードに落とせず。
結論は基底が負数であろうと基本的な進数変換とはほとんど変わらないので、同じようなことをすれば求めることができます。
D - Candy Distribution
本番中はCで苦戦してたので手を出さず。累積和とってmodでまとめるみたいな問題ですね。 D問題なので別記事にまとめます。
社内のプロコンで作った問題と思ったこと
６月に行われた社内のプロコンで初めて問題作成を行いました。 実際に作った問題と問題を作っている中で考えたことをまとめます。
前提条件
問題の作成をする際の条件はこんな感じでした。
- コンテスト時間は3時間
- 問題数は5問
- 問題のレベル感はAtCoder Beginner Contest程度
- 全体の得点がばらけるように部分点を多く設定する
部分点については最終的には全部の問題で細かく部分点が取れるようにしました。
ここから問題の概要を順番に説明しながら作成中に考えたことを説明していきます。
A - Convert Gengo
和暦(M, T, S, H, X)が与えられるので西暦に直して出力する問題。
Xは未来の新元号です。
これはいわゆるおまけ問題。
ほとんどの人は問題なく解いてくれますが、プログラミングに慣れていない人だと案外引っかかるようで思ってたより時間のかかる人もいました。この問題では元号ごとに部分点が入るようにしていて、ジャッジ結果から実装ミスの予想もできるような最終的にものすごいおまけの部分点になりました。
B - GCP
GCPの3種類の文字から構成される文字列の中で特定の文字列があれば消していき、最終的な長さを求めてくださいというような問題。(ちなみにGCPは「ぐー」「ちょき」「ぱー」の頭文字)
この問題はとある問題を参考にして難易度を上げました(AtCoderの問題をたくさん解いている人なら心あたりがあるかも?)
この問題は実はあまり作るときに悩まなかった問題。for文で回して部分点をとれるのとstackを使わないと満点をとれない2段階に分けただけでした。
この問題の基本的な考え方が、
このような感じで見つかるまで参照をずらして対象の文字列が見つかったら、
削除 → 文字列を詰める → 参照を一つだけ戻して再度探索みたいなものを想定していました。
ただ純粋にこれを実装してしまうと時間がかかってしまって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手目で打ったての座標がで与えられるので何手目で決着がついたか求める問題。
この問題だけ割と競プロ感が強い問題になりました(完全に趣味全開で問題を作ったため)。
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に保存すればサイトを作って過去の結果を公開するもの面白そうですね。
