2019-07-27

yukicoder contest 218 A - テストケース

A問題の解説です。

問題

No.851 テストケース - yukicoder

問題文(要約)

問題文

$3$ 個の数字が与えられる。
そのうち $2$ つを足した値として考えられるもののうち、 $2$ 番目に大きいものを出力せよ。
ただし改行区切りではなく空白区切りで与えられた場合、代わりに"assert"を出力せよ。

制約

$N = 3$
$1 \leq A_i \leq 10^10$
$A_1 \neq A_N$

まず、改行区切りで正しく与えられた場合の答えを考えてみましょう。
全探索するのも一つの手であり、実際に全部のパターンを網羅すれば良さそうです。
ここでは、もう少し賢い考え方で解く方法を説明します。

まず、 $A_1 \neq A_2$ かつ $A_2 \neq A_3$ である、つまり全ての値が異なるときを考えます。
この時、最小値+中央値<最小値+最大値<中央値+最大値なので、答えは最小値+最大値、すなわち $\min(A_1,A_2,A_3)+\max(A_1,A_2,A_3)$ に他なりません。
また、 $A_2$ がどちらかの値と等しい場合を考えます。
この時は最小値を出力する問題であり、これは $\min(A_1, A_2)+\min(A_2,A_3)$ を選ぶということに等しいです。
$A_2$ は必ずどちらかとは等しいので、両方で $A_2$ と等しい値を選ぶようなパターンも存在するため問題がありません。
これで全てのパターンを網羅してるので、答えが求まりました。

さて、後は改行区切りか空白区切りか判定する方法ですが、一番楽なのは1行読み込んでみる方法ではないでしょうか。
1行読み込んでみて、それを空白区切りにsplitできれば"assert"を出力するようにすると楽そうです。

感想

この問題は、★1の簡単な問題をとりあえず作るか―と思って作ってみました。
AtCoderとかでもうっかり改行区切りのテストケースが混入してたとかで問題になったりするので、それをどう対処するかという感じの問題にしてみました。
これでC++やJavaなど普段区切り記号を意識しない言語でも判定ができるようになったので、writerをやる人は区切り記号をちゃんとチェックできるようになったと思います。(ほんとか？)
なお、かなり問題の制約が意地悪い感じになっていますが、それはこの後の問題も罠があるよーという警告です。
そういうwriterだよって自己紹介を兼ねてる感じ、かな？
まぁやったら★1.5になったんですが

2019-05-20

AtCoder Beginner Contest 126

AtCoder Beginner Contest 126 (ABC126)に参加しました！

解けた問題だけ解説をしていきますー

2019-02-17

全国統一プログラミング王決定戦決勝参加記

全国統一プログラミング王決定戦本戦に参加しました！
全国統一プログラミング王決定戦本戦

ここでは実際に参加した時の感想などを書いていきます。
また、問題の解説は後日上げます。

11:30 開場

現地到着。
正面にホテルが見えているのに右側に曲がり始める方向音痴と化していて、流石に自分で笑ってしまったｗ
その後会場入りし、設営を開始
11:45には設営が終わったので他の競プロerと話しに移動

12:30 開会式

全員が着席し、試験の注意事項などが話される
なぜか紙の問題用紙が配られて、隣の人と一緒に困惑
その後、今書いてるこのブログなどを準備し、時間になるまで待機
カウントダウンとともに開始

12:45 決勝開始

まずはA問題を読み、累積和上のスライド最小値 ${\rm O}(N^2)$ であると確信
実装して提出、12:49にAC(現時点133位)
次にB問題
これ、単に上から比較で終わるので終了
大文字小文字に気を付けて提出、12:56にAC(現時点116位)
12:57 C問題読み始め
まず、そのあるマスが $(0, 0)$ だったとする
そうすると、移動させるマスの合計数は空欄以外のすべてのマスであり、これは数学で ${\rm O}(1)$ で求まる
だがこれだと計算量に問題があるね
ところで、これ移動距離はマンハッタン距離だから縦横独立に求められないか
後はそれの和で出せそう
お、なら答え出るな
まず、縦の位置を $y$ に決め打つと、移動させる距離は $\frac{y(y+1)+(H-y-1)(H-y)}{2}$ から各取り除いたコマとの絶対値の和に等しい
これは予め $C_i$ の小さい順にソートしてあればならし ${\rm O}(H)$ 、これを計算すれば解けるね
ちょっと遅くなったけど13:39提出、WA
……オーバーフローか？
問題見直してたらxy逆にするミスを発見、修正して13:54提出でAC(181位)
13:55 D問題読み始め
遅延セグ木の問題にしか見えないので遅延評価セグメント木について - beet's soilを貼りました
自分で作ってなかったのミスです、まぁAC(164位)
14:33 E問題とF問題を同時に読む
F問題について考察開始
まず、そのままならDijkstra法になるが辺が多すぎるのでTLE
そこで、何らかの方法で辺を減らせないか考察
まず、 $X_i$ 順にソートすると、前の方から後の方へ向かうことができるわけだ
$Y_i$ が無いとするとこれは自由に行き来できることになるが、例えばこの小問題について解くことができるかを考えてみる
すると、金額は大きい方の国が決めているので、大きい方から見ると

直接向かう、かかる金額は自分と同じ
自分より大きい中で最小の国を経由する、かかる金額はその国の金額x2

の2通りしかないことが分かる
ということはこれは $X_i$ を大きい順にみていって、その時の上の条件のうち小さい方を求めていけばいいので ${\rm O}(N)$ で求められることが分かる
この性質をなんとか一般化できないか考えてみよう
まず、まずいのは同じ法則ではいけない場所があるということ
まずx順にソートしておく
この時、各頂点についてDAGでそのようなものを見つけられると便利そう
自分よりX, Yともに大きいもので、まだ繋がってないようなものを経路として持ちたい
もちろんDAGなので辺の数は簡単に抑えられて、この上でならクラスカル法を用いることができる
後はこのDAGの作り方を考える
DAGはx昇順に考えたときy座標に対してsetを使いつつ繋ぐ先が分かって、辺の数が ${\rm O}(N)$ に抑えられたからあとはやるだけ
……とか言ってたら時間になってしまったので終了

15:45 コンテストが終わったので隣の人とFの考察

なんか話がかみ合わないので終了、たぶん私の考察が間違えているのですね
その後はトークショーだが聞き流しつつ更に考察
S, Tを固定しながら考えたら楽かと思ったが、 $(i, 10^8 - i - 2(-1)^i)$ みたいな点が与えられると絶望せざるを得ないのでやっぱりクラスカル法か？

16:50 表彰式

やっぱ上位勢強いなー

17:00 エキシビション

Chokudai SpeedRun 002じゃん
A問題、開幕トラブルで開始時間ずれてるの大変そう……ってか順位に響かないかそれ
……えー、準急さん速すぎませんか
めっちゃ速いんだが、上位陣になるならあの速解きしろとか言われても困るぞ……
後で問題読んでみたら自明だったので確かにあの速度も納得できるけど、でも速すぎた

17:30 懇談会

えー知らない人が多すぎて話すの難しいですね(？)
分かりやすいようにチルノグッズを揃えて歩いたけど、話したい人に話すのが困難だった
あ、でも直大さんからサインとステッカーもらった！
後はきゅうりさんと話したり、いつもTLで話してる人とリアルで話したりと楽しかった
食事は全然食べられなくて、19:20すぎて人が減ってから早食いチャレンジしました()
ちょっと500人は多すぎなので、次回はコンテスト会場が4倍の大きさか人数が1/4のコンテストで話したいですね～
というか二次会したかったです、次があったら企画するか

ちなみに、最終順位は167位です
ABCDやってFに挑んでるので妥当な結果ですかね