ぷぇ

競技プログラミングとかについて書きます。

解いたけどよくわからなかった/苦手っぽい問題集

タイトルの通り。

やっぱり増えたり減ったり放置されたりする予定。

 

ここに解法を書いちゃうともう一回解こうとした時に悲しい気持ちになることに気付いたので問題名だけ列挙する。

 

SRM604 Div1Easy PowerOfThree

SRM610 Div1Easy MaxArea

SRM617 Div1Easy MyLongCake

SRM625 Div1Easy PalindromePermutations

SRM626 Div1Easy FixedDiceGameDiv1

D - Zabuton

E: Grouping - AtCoder Regular Contest 067 | AtCoder 数学嫌い

E: 高橋君とホテル / Tak and Hotels - AtCoder Regular Contest 060 | AtCoder

E: Snuke Line - AtCoder Regular Contest 068 | AtCoder

解けなかった問題集

解説を読んでもよくわからず、解けなかった問題を載せていき、気が向いた時にもしかしたら解き直すかもしれない問題たちの墓場。

増えていったり減ったり更新されなかったりするもよう。

 

POJ3040 Allowance 2017 7/18(火) 蟻本2章章末の練習問題

1, 5, 10, 50...みたいになってるコインから指定の額以上になる組み合わせをなるべく多く作る問題。

目的の金額Cとしたとき, C以上の価格のコインは1枚で解決(自明)

Cに対してCより安いコインを採用した時、

C' = C - coin[i]

となる。(自明)

これをCがなるべく小さくなるようにした後、今残っている最小金額のコインで残りの金額を調整するらしい。(非自明)

どうやって実装するんだ…

3040 -- Allowance

 

ABC020 LCM Rush 2017 7/30

解説を見た感じ難しいらしい。

けど典型らしい。そのうち解こう。

abc020.contest.atcoder.jp

ACB022 Big Bang 2017 7/30

幾何っぽい。こわい。

解説を見ていない。そのうち解こう。

abc022.contest.atcoder.jp

AGC014 B  2017 7/28?

バーチャルコンテストで扱った。

多分もしかするときっとそのうち解く。

agc014.contest.atcoder.jp

 

TopCoder SRM 607 Easy

回文+期待値

 

 

競プロはじめて2年なので振り返る。

 

競技プログラミングをはじめて2年とちょっとが経ったので現状を記録し、過去をちょっとだけ振り返る。

 

 

現在のレーティング

f:id:Ti11192916:20170715010709j:plain

↑はalgonさんのやつです。

algon-320.hatenablog.com

 

AtCoderのレーティング

f:id:Ti11192916:20170715010943j:plain

見事な青天井

前回のAGCで少し上向いた。

 

AC数

 2年で600問 1年300問と考えると圧倒的に少ない。 

 

 

以上が現状の確認

以下は語りです。

 

過去

はじめてのプログラミングコンテストICPC国内予選2015でした。

大学からプログラミングを始めた私はプログラミングの実習で最大値を計算したり素数を求めたりすることに喜びを覚える方で、ものづくりやゲーム制作の類よりは授業のプログラミングのほうがずっと楽しいと思っていました。

幸せなことに私の大学は競技プログラミングが盛んな方で、大学の実習中にICPCに出ませんか?というアナウンスがあったので友人を誘い出ることに。

コンテスト直前の授業中に友達とTax Rate Changedを解いていた記憶があります。

Tax Rate Changed | Aizu Online Judge

 

国内予選2015では2問を解いて200位前後だった気がします。チーム名はNBie:teamとかだった気がする。

競技プログラミングのことを実習中にTAにいろいろ聞いてAtCoderの存在を知る。夏とかから始める。AtCoderは実は一度アカウントを変えているので当時の芸術的スパゲッティソースコードは今となっては発掘困難なのでちょっと惜しい。

弊学ではAOJ埋めが盛んなので、AOJ埋めにも手を出してみる。友人があっという間に200ACしてしまった一方で私はやっと1年かけて100ACしたのだった。

だいたいこれが1年目。

精進が下手、というよりは精進のやり方をあまり知らない感じだった。twitterもあんまり盛んにはやっていなかったし。

 

そして競プロ歴1年が経ち、ICPC国内予選2016。

前年と同じチームで出場しまた2完。

チーム名はSeseragi

この頃、非常に優秀な後輩らと出会い刺激される。後輩はあっという間に私のAC数を爆足で追い抜かし2倍の差を付けられる。

このあたりから、やっと真面目に競プロやり始めた感じがある。実質競プロ歴1年を主張したい。しないけど。

 

特にICPC以外は語ることがなかったけど、

周りに影響されるタイプなので何かに便乗してこれからも自分を騙し騙し上手いことやっていきたいですね。

 

ここからは、今日の国内予選2017の話。

長くなったので別でまとめた。

 

ti11192916.hatenablog.com

 

以上!

また一年後にこういうの書くつもりなので、それが今から楽しみ。

 

ICPC国内予選2017参加記

ICPC国内予選2017に参加したので記録。

 

苦渋の選択で昨年までのチームメイトに別れを告げ、後輩とチームを組む。組んでくださいと後輩にお願いをした。昨年までのチームメイトは競プロからすっかり離れてしまっていたためである。

minami と oshibori と TIke(私) で aotenjou として出ました。

 

 結果は3完。

またアジア地区大会に行けなかった。悔しいなぁ。

 

前日まで の流れ

コンテスト1ヶ月前辺りに一気にDPの勉強をした。簡単なbitDPなら比較的するっとかけるようになったのでとても成果があったと思う。

2週間ほどまえから突然フローを学び始めたが、 minami にフロー全然出なくないですか、と言われ『そうなんだ〜』となる。そしてなぜか精進が途切れる。(←??????)

 

国内予選前日にインターンの面接があり、SAN値減少。1d100。出目が良くて23くらいの減少で済んだ。

その日の夜から配属が決定した研究室の懇親会。

懇親会の自己紹介タイムで競プロ布教をした結果ダダスベリ。SANチェックです。1d100。発狂。

 

当日朝、早起きしすぎて10時頃寝こけてしまって危うくプラクティスセッションに遅れかけたが、絶妙なタイミングで宅配便が来て見事起床。ありがとう佐川急便、ありがとうお中元(?)

 

当日

minami が A を見ながら oshibori と TIke で B を見る。

B読み終えて考察をする。" " で囲まれた中身だけ別にして残りを一つの文字列にして比較する方針を oshibori に伝えたくらいで minami が A AC。めっちゃはやーい。oshibori が B を minami に伝える。TIke は C を見る。Bも一瞬でAC。

Cで何故か愚直解の可能性を完全に捨てて考察をする私。引っ張られる minami 。絵に書いた戦犯プレイの結果コンテスト終了1時間前までかけてO(kn^2m logn)くらいの解法を編み出しバグらせる。kは張る池の深さ。池が張れる横の区間をsetかなんかに入れて始点と終点が一致するか、しなければその下が池を張る区間とかぶっていないかを考える感じ。なんとなくsnackdownを思い出した。

バグ取りが終わりACを取った時には残り8分。

隙間で oshibori がDの考察を進めてくれていたので n が小さい時は半分全列挙して大きくなったら0-1ナップサックで解く解法が生える。半分全列挙まで紙コーディングができていたので残りの8分でそれを写してコンテスト終了。

ICPC国内予選2017はあっけなく終わった。

 

総括

制約を見よう。大切なコンテストは、冷静に取り組もう。

精進をしよう。

 

競プロやめたくなるような体験だったけど不思議とそういう気持ちにはならないのでやっぱり競プロ好きなんだなぁと再確認した。

必至でやってないから好きのままでいられてるだけかもしれないけど!

 

AOJ0157 Russian Dolls / ABC038 プレゼント

 

全く同じ問題をACしたことがあるのにさっぱり解けないのはまずいでしょ。

 

 

ということで、反省の意味も込めて問題の解説記事を書きます。

 

 

問題

Russian Dolls | Aizu Online Judge

D: プレゼント - AtCoder Beginner Contest 038 | AtCoder

 

 

問題概要

制約以外はほとんど同じ問題なので、制約がよりゆるいAOJの問題の説明をします。

これは、AOJでACする解法を高速化することでABC038でACすることができ、

この記事では高速化の部分については深く触れないためです。

 

 

マトリョーシカが2つある。

それぞれ人形がn, m個入れ子になっている。

それぞれの人形のパラメータ(高さ、半径)が与えられるので

最大でいくつの人形からなる一つのマトリョーシカを作れるだろうか?

 

 

入力

n : 1つ目のマトリョーシカを構成する人形の数

m : 2つ目のマトリョーシカを構成する人形の数

h_i, r_i : i番目のマトリョーシカのパラメータ(高さ、半径)

 

 

考察

2つのマトリョーシカを別々に考える必要はなく、

(n+m)個の人形を使って1つのマトリョーシカを構成することを考えればよい。

この時点で、制約以外が ABC038 プレゼント と一致します。

上の考えに基づいて問題を言い換えると...

 

パラメータ(h, r)を持つ n+m 個の要素の中から

全ての i, j について h_i < h_j かつ r_i < r_j (ただし i < j )

を満たすような最長の要素の並びの長さ求める。

 

となります。

固く書くと逆にわかりづらいので、柔らかく書くと

人形の高さと半径の両方が左に行くほど小さくて、右に行くほど大きくなるように

並べた時、一番長くてどれくらいかな〜?って感じです。

これで伝わればいいなって思います。

 

 

解説

解説はAtCoder社のスライドがあり、それが完璧なので正直そっちでいいんですが、

スライドだけだとよくわからないという人もいると思うので(私です)、

説明下手マンなりにいい感じになるよう解説を頑張ります。

だんだん書くのがめんどくさくなってきました。

AtCoderの解説が悪いわけではありません、最高です。悪いのは私の頭です。)

 

 

表現が具体的でなかったり、実装と一致しない部分がありますが、

実装はひとまず置いといてイメージしてみてください。

 

まず、人形(上で言う要素、マトリョーシカ人形)の高さが重複しない

場合を考えます。

つまり、背の高さが同じ人形がない時のことを考えます。

 

人形(上で言う要素、マトリョーシカ人形)を背の順に並べます。

すると、左から小さい順に人形が並びますが、幅はまちまちです。

この人形をえいってやるのですが、えいってするために配列を用意します。

 

配列 dp[幅] = 個数

 

この配列に、人形を先頭から掴んで、

配列の添字が人形の幅の値と等しい場所に入れていくのですが、

この時、今入れる人形の幅よりも小さい幅の人形が既にどれくらい入っているかを

考慮します。

今掴んだ人形より先に配列に入れられた、既に配列に入っている人形は

必ず今掴んでいる人形より背が低いです。

さらに、今から入れる場所よりも添字が小さい場所に入っている人形は

必ず今掴んでいる人形より痩せています。(幅が小さいです。)

幅と配列の添字が対応しているので、

(添字が小さい)=(幅が小さい)

ということが必ず言えるので、

背の順に並べて、それを先頭から幅順にすると、

その時点でその人形より小さい人形(マトリョーシカできる人形)が分かる!

ということが分かります。

 

ここで、配列に代入する値ですが、

ある人形 A を手に取った時、それより小さい人形が全てわかるので、

何個マトリョーシカできるか分かる気がしてきませんか?

できるんです。

 

具体的には、

 人形 A より小さい人形 のなかで 一番マトリョーシカできる人形 + 1

が dp[Aの幅] の中に入る値です。

一番マトリョーシカできる人形を、人形 A でマトリョーシカするので

今までで一番多い + 1 になるのは分かるかと思います。

 

実際に値をいじってみましょう。

 

 

人形:

 A ( 1, 2 )

 B ( 3, 4 )

 C ( 4, 8 )

 D ( 2, 6 )

配列:

 int dp[10] = {0}      // 全て0で初期化されている

 

①まずソートする

 A ( 1, 2 )    A ( 1, 2 )

 B ( 3, 4 )    D ( 2, 6 )

 C ( 4, 8 ) →  B ( 3, 4 )

 D ( 2, 6 )    C ( 4, 8 )

 

②1番目の人形( A )を手に取る

 

③配列に入れる

A ( 1, 2 )

添字 |0|1|2|3|4|5|6|7|8|9|

dp  |0|0|1|0|0|0|0|0|0|0|

dp[2] = 1; となった。2より幅が小さい人形がないので、

人形1個目ということで、値は1。

 

④2番目の人形( D )を手に取る

 

⑤配列に入れる

D ( 2, 6 )

添字 |0|1|2|3|4|5|6|7|8|9|

dp  |0|0|1|0|0|0|2|0|0|0|

dp[6] = 2; となった。6より幅が小さい人形が1つ(Aのみ)あるので、

人形Dの中に人形Aを入れることができる、という意味で配列の値は2になる。

 

⑥3番目の人形( B )を手に取る

 

⑦配列に入れる

B ( 3, 4 )

添字 |0|1|2|3|4|5|6|7|8|9|

dp  |0|0|1|0|2|0|2|0|0|0|

dp[4] = 2; となった。4より幅が小さい人形が1つ(Aのみ)あるので、

人形Bの中に人形Aを入れることができる、という意味で配列の値は2になる。

この時、人形Dが既に配列に入っていて、人形Dのほうが幅が大きいので

人形Dの中に人形Bを入れられると思うかもしれないが、

今人形は背の順に処理されているため、配列に既に入っている人形は

今手に持っている人形を中に入れることができないことに注意。

 

⑧4番目の人形( C )を手に取る

 

⑨配列に入れる

C ( 4, 8 )

添字 |0|1|2|3|4|5|6|7|8|9|

dp  |0|0|1|0|2|0|2|0|3|0|

dp[8] = 3; となった。8より幅が小さい人形が2つ

(AとBもしくはAとD, 配列で見ると dp[4] か dp[6] それぞれ A in D, A in B の意味)

あるので、

人形Aが中に入った 人形Bか人形D を人形Cの中に入れることができる、という意味で配列の値は3になる。ここで、何個マトリョーシカできるか、が知りたいので、

どれがマトリョーシカするか(すなわち人形Bか人形Dか)は気にしなくて良い。

どっちが中に入っていようと、一番外側は人形Cにるので、

これから先により大きい人形が来ても

気にしなければならないのは、一番外側の大きさのみだから、である。

(一番外側のマトリョーシカのサイズ次第で入れられるかが決まるため)

 

操作は以上だが、出来上がった配列を見てみると何がメモされているか分かる。

添字 |0|1|2|3|4|5|6|7|8|9|

dp  |0|0|1|0|2|0|2|0|3|0|

 

dp[2] = 1; これは、一番外側が幅2の、中に何も入っていない人形がある

dp[4] = 2; これは、一番外側が幅4の、中に人形が1つ入った人形がある

dp[6] = 2; これは、一番外側が幅6の、中に人形が1つ入った人形がある

dp[8] = 3; これは、一番外側が幅8の、中に人形が2つ入った人形がある

 

それぞれ上記を示している。

これより先に入ってくる人形がもしあれば、それは

高さがいままでのどの人形よりも大きくなければならない。

 

ここまでが高さに重複がない場合。

高さに重複がある場合は、少し工夫が必要である。

 

 

高さが重複する場合

今までは全ての人形の高さが違ったため、

人形を背の順にならべて小さいものから操作することで、

既に配列に入っている人形が、必ず全て現在操作している人形より小さい、

という状況を作ることができていました。

しかし、高さが同じ人形が存在すると、

高さが同じ2つの人形をマトリョーシカすることはできないので、

既に配列に入っている人形の中にも、マトリョーシカできない

人形が存在してしまうかもしれない状況ができてしまいます。

 

上記のことが、一様に人形を操作できなくなる原因なので、それを取り除きましょう。

これはちょっとした工夫で可能です。

 

人形を背の小さい順にならべ、高さが同じ人形は幅が大きい順に並べます。

こうすることで上手く処理ができるようになります。

これはなぜかというと、

ある人形を操作する時、その人形の幅を見て配列に人形を入れます。

この時、その人形の幅よりも幅が小さい人形についてのみ、

最大で何個マトリョーシカできるかを調べます。

なので、幅が大きい物から処理をすれば、必ず配列のより添字がより小さい方には

高さが同じ人形が存在しなくなるのです。

 

実際に操作をしてみると、今配列が以下のようになっているとします。

添字 |0|1|2|3|4|5|6|7|8|9|

dp  |0|0|1|0|2|0|2|0|3|0|

ここに、A (10, 9 ), B (10, 6 ), C (10, 2 ) の人形を入れていくことを考えます。

人形の操作のルールに基づき、今既に配列に入れられた人形は、みな

高さが10より小さいです。

 

①まずA (10, 9 ) を入れます。

添字 |0|1|2|3|4|5|6|7|8|9|

dp  |0|0|1|0|2|0|2|0|3|0|

               ↑ ココに入る

人形の幅は9なので、 dp[9] が入れる箇所です。

操作のルールどおり、dp[0] ~ dp[8] の中で最大値を探すと、dp[8] = 3 が

最大である事が分かります。よってdp[9] = 4 となります。

 

②次にB (10, 6 ) を入れます。

添字 |0|1|2|3|4|5|6|7|8|9|

dp  |0|0|1|0|2|0|2|0|3|4|

            ↑ ココに入る

人形の幅は6なので、 dp[6] が入れる箇所です。

操作のルールどおり、dp[0] ~ dp[5] の中で最大値を探すと、dp[4] = 2 が

最大である事が分かります。よってdp[6] = 3 となります。

この時、高さが同じだった人形Aは、Bより幅が大きいので、

最大値を探す範囲 ( dp[0] ~ dp[5] ) に存在しない ( dp[9]にいる ) 事が言えます。

なので、今までどおり高さを気にせず操作することができます。

ちなみに、この時 dp[6] には既に2が入っていますが、

これから操作される人形は必ずいま配列の中にいるどの人形よりも背が高いので、

背の高さの条件を必ず満たすので幅についてだけ考慮すれば良く、

幅6の人形で、2マトリョーシカと3マトリョーシカなら、

どのような人形を上にかぶせても3マトリョーシカの人形にかぶせたほうが

必ずマトリョーシカ数が大きくなります。よって配列の中にはより大きい値

常に採用していけば良いのです。

 

③同様の操作で C ( 10, 2 ) を入れます。

添字 |0|1|2|3|4|5|6|7|8|9|

dp  |0|0|1|0|2|0|3|0|3|4|

       ↑ ココに入る

同様にするだけです。 dp[2] = 1となり値は変わりません。

 

 

解法のまとめ

①背が小さい順、背が同じなら幅が大きい順に人形を並べる。

②先頭から人形を手に取り、配列の添字がその人形の幅の値と一致する部分に人形を入れることを考える。

③その添字より小さい添字の中から、配列の中の値の最大値を調べる。

④調べた値 + 1 が配列のその人形が入る部分の値となる。

⑤人形がなくなるまで②に戻って繰り返し操作をする。

⑥人形がなくなったら、配列全体の最大値が答えとなる。

 

 

以下ソースコード

AOJ0157

 

 

AOJ1316/The Sorcerer's Donut

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1316

 

ドーナツに文字が刻み込まれているので、その中から複数回出現する部分文字列の中で最大の長さのものを出力する問題です。

 

入力は長方形に並べられた文字列ですが、端に行くと反対の端から出てくる仕様になっています。(ドーナツに刻み込まれているのを想像すればわかる)

 

長方形全ての文字をそれぞれ始点にした時、それぞれ8方向に探索して部分文字列を得る度にsetに突っ込んで既出だったら答えを更新します。

 

AOJ1316

AOJ2300/Calender Colors

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2300

 

n個の中からm個選んで

 

そのm個の中で作れる全通りのペアについて

 

それぞれの要素について二乗和を求めて

 

全て足した値の最大値を求める問題です。

 

バックトラックで解きましたがもう少し賢く解けそうですね…

 

n個の中でi番目について (選ぶ|選ばない) して

 

再帰的に解いています。

AOJ2300