yukicoder contest 218 E - ヘビの日光浴
E問題の解説です。
問題
問題文、説明が難しいのでこっち読んでね。
さて、ヘビの移動について実際にシミュレーションしていきましょう。
各ヘビについて、正面のヘビとぶつかるか?は簡単に求められるかと思います。
同じ座標のヘビについて簡単に判定できれば良いので、座圧しておけばインデックスと対応します。
次に、左右のヘビとぶつかるかを考えます。
これは、左右のヘビそれぞれについて、自分とぶつかる長さ以上のヘビのうち最も近い位置のヘビがぶつかる位置ならぶつかります。
これはセグメント木上の二分探索を行うとで判定することができます。
よってアルゴリズムとしては解くことができます。
実装に関しては、セグメント木4本を左右それぞれ二分探索する必要があるなどかなり重い実装を要求するので注意してください。
yukicoder contest 218 D - 公平なりんご分配
D問題の解説です。
問題
No.854 公平なりんご分配 - yukicoder
問題文(要約)
問題文
個のクエリが与えられるので、各クエリについてがで割り切れるか判定してください。制約
この手の連続部分列のクエリ系問題は、累積和で高速にするのが有効ですよね!
ただ、このままだと逆元が無いので良い感じにクエリの判定ができないし、値をそのまま計算すると大きくなりすぎてしまいます……。
そこでを素因数分解すると、各素因数については単にその個数だけ素因数を含むか判定する問題になります。
これならば累積和上で個数は管理できるので、無事に解けました。
感想
まぁ典型よりですかね、これは普通に解かれる問題と思っていました。
実際に解かれている模様なので、こんなものかなと。
yukicoder contest 218 B - 連続部分文字列
B問題の解説です。
問題
No.852 連続部分文字列 - yukicoder
問題文(要約)
問題文
文字列が与えられます。
の空でない連続な部分文字列における、文字の種類数の平均を求めてください。
絶対誤差はまで許容されます。制約
- はアルファベット小文字のみで構成される
典型問題ですね!
連続な部分文字列と言われているので、まずは左から決め打っていくDPを考えましょう!
また、連続な部分文字列の個数が個あるのは自明なので、平均ではなく総和で考えて最後に割ることにしましょう!
さて、左から考えるときに必要な情報はなんでしょうか?
やはり、ある文字まで見た時に、を右端とする連続部分文字列の文字の種類数の総和が求められると楽そうです。
まず、を右端とする連続部分文字列は明らかにを右端とする連続部分文字列(と空文字列)の右にをくっつけたものなので、直前の計算結果を利用できそうです。
直前の部分文字列と比べて、答えがどのくらい増えるか考えてみましょう。
すると、下の図のように増えることが分かります。
つまり、1個前の同じ文字との距離だけ増えた値が入ることが分かりますね。
これが分かれば後はそのまま実装するだけで答えが分かりますね。
感想
ei1333という答えになる問題が作りたくて作りました。
1.333=4/3なので、なんかそれっぽいのにならないかなーって思ったら思いついた問題です。
正直まぁやるだけなので、個人的には★2だと思っていました。★2.5らしいですね、難易度分からない
ちなみに当初は絶対誤差をまで許容していましたが、テスターに乱択を通されてどうやっても落ちなさそうだったので変えました。
流石にマラソン解法が通るのは……うん……。
yukicoder contest 218 A - テストケース
A問題の解説です。
問題
No.851 テストケース - yukicoder
問題文(要約)
問題文
個の数字が与えられる。
そのうちつを足した値として考えられるもののうち、番目に大きいものを出力せよ。
ただし改行区切りではなく空白区切りで与えられた場合、代わりに"assert"
を出力せよ。制約
まず、改行区切りで正しく与えられた場合の答えを考えてみましょう。
全探索するのも一つの手であり、実際に全部のパターンを網羅すれば良さそうです。
ここでは、もう少し賢い考え方で解く方法を説明します。
まず、かつである、つまり全ての値が異なるときを考えます。
この時、最小値+中央値<最小値+最大値<中央値+最大値なので、答えは最小値+最大値、すなわちに他なりません。
また、がどちらかの値と等しい場合を考えます。
この時は最小値を出力する問題であり、これはを選ぶということに等しいです。
は必ずどちらかとは等しいので、両方でと等しい値を選ぶようなパターンも存在するため問題がありません。
これで全てのパターンを網羅してるので、答えが求まりました。
さて、後は改行区切りか空白区切りか判定する方法ですが、一番楽なのは1行読み込んでみる方法ではないでしょうか。
1行読み込んでみて、それを空白区切りにsplitできれば"assert"を出力するようにすると楽そうです。
感想
この問題は、★1の簡単な問題をとりあえず作るか―と思って作ってみました。
AtCoderとかでもうっかり改行区切りのテストケースが混入してたとかで問題になったりするので、それをどう対処するかという感じの問題にしてみました。
これでC++やJavaなど普段区切り記号を意識しない言語でも判定ができるようになったので、writerをやる人は区切り記号をちゃんとチェックできるようになったと思います。(ほんとか?)
なお、かなり問題の制約が意地悪い感じになっていますが、それはこの後の問題も罠があるよーという警告です。
そういうwriterだよって自己紹介を兼ねてる感じ、かな?
まぁやったら★1.5になったんですが
全国統一プログラミング王決定戦決勝 参加記
全国統一プログラミング王決定戦本戦に参加しました!
全国統一プログラミング王決定戦本戦
ここでは実際に参加した時の感想などを書いていきます。
また、問題の解説は後日上げます。
- 11:30 開場
現地到着。
正面にホテルが見えているのに右側に曲がり始める方向音痴と化していて、流石に自分で笑ってしまったw
その後会場入りし、設営を開始
11:45には設営が終わったので他の競プロerと話しに移動
- 12:30 開会式
全員が着席し、試験の注意事項などが話される
なぜか紙の問題用紙が配られて、隣の人と一緒に困惑
その後、今書いてるこのブログなどを準備し、時間になるまで待機
カウントダウンとともに開始
- 12:45 決勝開始
まずはA問題を読み、累積和上のスライド最小値であると確信
実装して提出、12:49にAC(現時点133位)
次にB問題
これ、単に上から比較で終わるので終了
大文字小文字に気を付けて提出、12:56にAC(現時点116位)
12:57 C問題読み始め
まず、そのあるマスがだったとする
そうすると、移動させるマスの合計数は空欄以外のすべてのマスであり、これは数学でで求まる
だがこれだと計算量に問題があるね
ところで、これ移動距離はマンハッタン距離だから縦横独立に求められないか
後はそれの和で出せそう
お、なら答え出るな
まず、縦の位置をに決め打つと、移動させる距離はから各取り除いたコマとの絶対値の和に等しい
これは予めの小さい順にソートしてあればならし、これを計算すれば解けるね
ちょっと遅くなったけど13:39提出、WA
……オーバーフローか?
問題見直してたらxy逆にするミスを発見、修正して13:54提出でAC(181位)
13:55 D問題読み始め
遅延セグ木の問題にしか見えないので遅延評価セグメント木について - beet's soilを貼りました
自分で作ってなかったのミスです、まぁAC(164位)
14:33 E問題とF問題を同時に読む
F問題について考察開始
まず、そのままならDijkstra法になるが辺が多すぎるのでTLE
そこで、何らかの方法で辺を減らせないか考察
まず、順にソートすると、前の方から後の方へ向かうことができるわけだ
が無いとするとこれは自由に行き来できることになるが、例えばこの小問題について解くことができるかを考えてみる
すると、金額は大きい方の国が決めているので、大きい方から見ると
- 直接向かう、かかる金額は自分と同じ
- 自分より大きい中で最小の国を経由する、かかる金額はその国の金額x2
の2通りしかないことが分かる
ということはこれはを大きい順にみていって、その時の上の条件のうち小さい方を求めていけばいいのでで求められることが分かる
この性質をなんとか一般化できないか考えてみよう
まず、まずいのは同じ法則ではいけない場所があるということ
まずx順にソートしておく
この時、各頂点についてDAGでそのようなものを見つけられると便利そう
自分よりX, Yともに大きいもので、まだ繋がってないようなものを経路として持ちたい
もちろんDAGなので辺の数は簡単に抑えられて、この上でならクラスカル法を用いることができる
後はこのDAGの作り方を考える
DAGはx昇順に考えたときy座標に対してsetを使いつつ繋ぐ先が分かって、辺の数がに抑えられたからあとはやるだけ
……とか言ってたら時間になってしまったので終了
- 15:45 コンテストが終わったので隣の人とFの考察
なんか話がかみ合わないので終了、たぶん私の考察が間違えているのですね
その後はトークショーだが聞き流しつつ更に考察
S, Tを固定しながら考えたら楽かと思ったが、みたいな点が与えられると絶望せざるを得ないのでやっぱりクラスカル法か?
- 16:50 表彰式
やっぱ上位勢強いなー
- 17:00 エキシビション
Chokudai SpeedRun 002じゃん
A問題、開幕トラブルで開始時間ずれてるの大変そう……ってか順位に響かないかそれ
……えー、準急さん速すぎませんか
めっちゃ速いんだが、上位陣になるならあの速解きしろとか言われても困るぞ……
後で問題読んでみたら自明だったので確かにあの速度も納得できるけど、でも速すぎた
- 17:30 懇談会
えー知らない人が多すぎて話すの難しいですね(?)
分かりやすいようにチルノグッズを揃えて歩いたけど、話したい人に話すのが困難だった
あ、でも直大さんからサインとステッカーもらった!
後はきゅうりさんと話したり、いつもTLで話してる人とリアルで話したりと楽しかった
食事は全然食べられなくて、19:20すぎて人が減ってから早食いチャレンジしました()
ちょっと500人は多すぎなので、次回はコンテスト会場が4倍の大きさか人数が1/4のコンテストで話したいですね~
というか二次会したかったです、次があったら企画するか
ちなみに、最終順位は167位です
ABCDやってFに挑んでるので妥当な結果ですかね
AtCoder Grand Contest 029
AtCoder Grand Contest 029 (AGC029)に参加しました!
AtCoder Grand Contest 029 旧版
AtCoder Grand Contest 029 beta版
解けた問題だけ解説をしていきますー
続きを読む