2021-03-14

AHC001 参加記

暫定 58 位で、システムテスト待ち

方針

とりあえず常に各広告が (x, y) を含むとしよう。さもなければ少なくとも 0.5 点の損失となるし、N の分布からして平均的に1点はありそう。正確に計算できると思うが、よくわからなかった。実験してもよかったが、そこまで重要な数値ではないと思う。
常に s ≦ r としてよい。そうじゃないほうがいいケースも稀にあるが、たぶんほぼ無意味、ほんとか？と思って電車の中からスマホでそこだけ変えて再提出した。ちょっと伸びました。よって常に "ほぼ" s ≦ r としてよい。（幅 w のときに、wh < r < w(h+1) なる h が存在して 1-wh/r > w(h+1)/r-1 のとき、とか。）
とりあえず上記を満たしたまま最小の広告たちから山登り。機械的に焼きなましに移行する。最序盤は1位だった瞬間もあった。嬉しいねぇ。
変形操作は最終的なものだけ挙げると、「ある辺を内側に動かして、隣接するいずれかの辺を外側に動かす」「全体を動かす」の2択。実際には、内側に動かすのは確率=現時点でのスコアでやった。変形量は 0〜可能な最大値の範囲で一様ランダムに。0含めたほうが良かったんですよね。謎。分布がいい感じとかそういうアレかな。衝突チェックは毎回全部やった。
1-(1-0.9)² = 0.99 で、min(s/r) の最大化が肝要なことに気づく。（ここですべての広告が点 (x, y) を含むのはやはり正しそうだと思う。）どうするよ……と思ったが、r を ceil(min( (t/1.5+0.4)r, r) ) (t は時刻で、t in [0, 1])にすると良い感じだった。なぜかは、知りません……、そこまで上手くいっている気はしなかったが、いっか〜という感じ。

やってないこと

基本的に Introduction to Heuristics Contest の解説を頼りにやっていたのだけど、巨大近傍法を考えることはできず。
ビームサーチとかあり得るのかな。端っこから矩形充填みたいな感じでやっていく？
最初から充填された状態でやって、最後にオーバーしたやつを減らすのはかなりいい方針にみえる。上位こんなんなのかなー、ふつうに難しくて、できず。

2020-12-15

HTTF 2021 for Youth 参加記

予選

1時間以上参加した初のマラソン形式のコンテストでした。

Introduction to Heuristics Contestの解説が楽しかった
夜にコンテストに参加するのがしんどく、14:00-が嬉しかった
早解きが苦手なので向いてるかもなぁと思った
本選オンラインだし通ったら気軽に出れるなぁと思った

などが参加理由です。66位だったんですが、ユース枠のボーダーが250位ぐらいという情報を得てびっくり。Introduction to Heuristics Contestの解説を見ながらほぼそれに沿って進めていったのが勝因だったのかもしれません。

本選

よくわかりませんでした。いろいろ考えたんですが、これをあまり考えずにIntroduction to Heuristics Contestの解説に頼って進めるとユース優勝ぐらいは狙えたのかもしれません。瞬間最高順位は4位で、価値の高い順に鉱石を見て、外か既に掘った場所へ掘り進めてみて得点が上昇したら採用、を繰り返す方針で2時間ぐらいで1.67M点を得ていました。いろいろして2.03M点、33位で終了しました。

懇親会

解説部屋にいたのですが、フローの解説が始まって、何もわからなかったので部屋を渡り歩くと、解説部屋にしか人がいないことがわかりました。フューチャーのお仕事について聞ける部屋に少し人がいたので少し話して、終えました。もらえたごはんがおいしかったです。

2020-06-23

Rust で尺取り

Rust でこの問題が解きたいですが，C-style for は Rust では煩雑になりがちです．

問題 1

let ans = (0..a.len())
    .scan((0, 0), |(right, sum), left| {
        *right += a[*right..]
            .iter()
            .position(|&a| {
                *sum + a > k || {
                    *sum += a;
                    false
                }
            })
            .unwrap_or(a[*right..].len());
        *sum -= a[left];
        Some(*right - left)
    })
    .sum::<usize>();

問題 2

let ans = (0..a.len())
    .scan((0, 0), |(right, sum), left| {
        *right += a[*right..]
            .iter()
            .position(|&a| {
                *sum + a > k || {
                    *sum += a;
                    false
                }
            })
            .unwrap_or(a[*right..].len());
        *sum -= a[left];
        Some(a.len() - *right)
    })
    .sum::<usize>();

解説

なし

おわりに

cond && { expr; true } の良い感じの改善策を募集しています．

2020-06-07

第三回アルゴリズム実技検定 Rust で上級

Rust

第三回アルゴリズム実技検定（PAST 202005）を Rust で実装したものを、ごくかんたんな解説とともにおいておきます。上級を取得するのに必要な問題だけ解いています。つまり、A - L 問題だけです。

drive.google.com

2020-05-12

ABC167 解説

ABC167
解説は多くの省略を含みます。とくに添え字の範囲は、誤解がないと思われる場合ほぼすべて省略しています。
Rust を使用していますが、名前のインポートは省略されます。自作ライブラリも内容を書かずに使用します。Rust の文法をもった疑似コードだと思ってください。

解説PDF

解説を書いてみるの、けっこう楽しいです。かなりきれいな実装ができたと思います。F の証明をもう少し簡潔に済ませたいところなのですが、技術不足か、こういうものなのか、なかなか思うようにはいきませんね。

2020-05-11

AtCoder で青色(2級)になった、ときのコンテストの参加記

雑な参加記を雑に書く。これは青色になった瞬間の記事で、青色になるまでの記事はまた別に書くかもしれない。なにかの役に立つことはあまり想定していませんが、青色になったばかりの人間の一例の雰囲気をつかむためにでもお役立てください。ABC167です。提出

参加前

レートは1569で、参加回数は41回、ac-predictor によればパフォーマンス1839相当で青色を達成できるらしい。直近3回のパフォーマンスは1711、1789、1750だったので、いけるかな、という感じはあった。

ところで最近NimからRustに乗り換え、というか復帰しつつあったため、ライブラリが整っていない状態での参加だった。UnionFindぐらいあったほうがいいかな、と思って本番直前に書いた、使わなかったけど。

参加

A問題を開く、ほうほうわかった、と言いながら、なぜかDから解いてみたくなったため、Dを開く。どう見てもへんてこ辞書だなあ、と思いながら書いた。Dまで一気に提出するのにハマっていたため、提出を保留する。

C問題、proconioに感謝しながら入力を楽に突破し、全探索を書く。BとAもふつうに解いて、ABCDを提出しながらE問題を読む。

DのACを確認して3分ぐらいだろうか、Eが解けたので、書こうとする。あっしまった、Rustのmodintとか階乗前計算とかがない、と気づく。どっかにあった気がするな～と思いながら探すと、modintだけあった。そうだったなぁ、と思ってNimに切り替える。Nimのライブラリはそこそこ整っているため、すぐ書けた。

EのACを確認して、F問題を見る。この時点で34分経過していた。Eまで解かれやすそうな問題並んでたし微妙かな～とか思っていたのに、ac-predictorを確認してみるとその時点で暫定パフォーマンスが2000を超えていてびっくりした。難易度判定は難しいということですね。

Fは誤った解法をNimで実装してWAで終わりました。

参加後

TLでFの解法を探す、特別な知識が必要とされるタイプの問題ではなかったため、これは解いておきたかったなぁ、と思う。あっそうだそうだ、レートはどうなるのかな、とac-predictorを覗くと、1600を僅かに超えていた、やったね。レート更新が確定したので、ツイートした、リプライとかいいねとかリツイートとかがたくさん来た。にっこり。

おっやったね

cunitacさんのAtCoder Beginner Contest 167での成績：463位
パフォーマンス：1882相当
レーティング：1569→1605 (+36) :)
Highestを更新し、2 級になりました！#AtCoder https://t.co/yy3OKIqkfj
— cunitac (@CUteNeuron) May 10, 2020

翌日

復習～、深夜にFの解法に納得した（というより自身の解法の誤りに納得した）のでRustで実装してACした。Rustのmodintとか階乗前計算とかをライブラリ化してEをRustで実装してACした。

おわりに

青色になるというところまで来ても、言語が安定していなかったり、本番直前にUnionFind書いたり、本番中にライブラリを慌てて探したり、気まぐれで解く順番変えたりしてる人もいるんだよ、みたいな記事でした。だから何？と言われると、うーん。

2020-05-04

ABC166F を直感的なDFSで

直感的な、と書いていますが、計算が間に合うことは直感に反すると思います。

問題概要

F - Three Variables Game

非負整数の値をとる変数 $A,B,C$ に対して、操作を $N$ 回行います。 $i$ 番目の操作は、長さ $2$ の文字列 $S_i$ によって表され、指定された $2$ 変数のうち一方を $1$ 増やし、他方を $1$ 減らすというものです。すべての操作が可能かどうか判定してください。さらに、可能なら手順をひとつ提示してください。

解答

最も直感的な解法は、操作ごとに二通りに分岐して、すべてのパターンを試すことでしょう。手順の提示を省略し、疑似コードで示します。

procedure dfs( i ) =
  if i > N then 成功
  foreach S_i の意味する操作 do
    if 操作が可能 then
      操作
      dfs( i + 1 )
      逆操作
dfs( 1 )

これでは間に合うわけがありません。 $O(2^N)$ 個もの状態を考慮することになります。

……というのは嘘で、これで十分間に合います。以下にざっくり示します。

正当性（なぜ速い？）

$A=B=C=0$ のとき、明らかに即座に終了します。 $A+B+C= 1$ のとき、dfs(i) は高々 $1$ 回しか dfs(i+1) を呼び出さないため、このDFSは時間計算量 $O(N)$ で動作します。以下、 $A+B+C\ge 2$ を仮定します。

操作ができないとき、すなわち dfs(i) が dfs( i+1 ) を呼ばないとき¹を考えます。たとえば操作 'AB' が与えられたときに、 $A=B=0$ だったとします。

ひとつ前の状態がないとき、操作は不可能です。
ひとつ前の状態があるとき、ひとつ前の操作は確実に 'AC' か 'BC' であり、確実にかを減らしています。
- ひとつ前の操作で $C$ を減らすほうを選べる場合、そちらを選べば操作 'AB' は確実に可能です。
- ひとつ前の操作で $C$ を減らすほうを選べない場合、ひとつ前の状態は $(A,B,C)=(1,0,0),(0,1,0)$ のどちらかです。 $A+B+C\ge 2$ なのでありえません。

これをもとに考えると、各 i について dfs(i) が高々 $2$ 回しか呼ばれないことがわかります²。よってこのDFSは時間計算量 $O(N)$ で動作します。

もちろん、成功して終了する場合を除きます。↩
論証に穴がある可能性は否定できませんが、存在するテストケースについては正しいです。この提出で確認しています。↩