6pm(日本では9:30pm〜翌9:30pmまで)に開催されたTLEの参戦メモです。いっても参加308チーム(※個人参戦可)のうち205が地元インドからで、残りのうち37チームが日本(Countryが"yokohama"の人を入れると38)、ロシア・ウクライナ・ベラルーシ・カザフスタンで計31チーム。http://felicity.iiit.ac.in/tle/問題は7問(大会終了後に問題文見れなくなってますね)で、10000からコードサイズ(bytes)を引いた数を得点とし(※問題によっては引くのがコードサイズの1/5だったり)、7問の得点の合計で競われます。golfはご存知かと思います。1打でも少なくする(=1バイトでも短いコードを書く)系の競技です。題意を満たすプログラムが普通に(golfせずに)書けることは必須条件ですが、競技としてはパズル的要素が大きいです。はい、こういうの大好きです。今年は全問に回答できて66484点で6位でした。いうかこれインドの大会って嘘ですよね?みたいなランクリストですが毎年こんな感じです。今年はkinabaさんに軍配が上がりました。自分の回答コード(自動生成したものについてはそのコードを生成したコードを含む)はgithubに上げてます。golf的にも計算機科学的にも大した技術は使っていないと思いますが)記事内でのネタバレは避けたいのでコード閲覧はgithubでどうぞ。こんな所を見てないで今回優勝されたkinabaさんのコードhttp://www.kmonos.net/wlog/sub/TLE12/とかshinhさんのhttp://shinh.skr.jp/dat_dir/tle2012/を参考にされることを強く推奨する次第です。BST与えられた数値リストから2分探索木を構築し、上下左右をひっくり返して表示するコードを書く。問題文のとおりにスペース区切りで表示したのに理不尽にWA食らい続けて諦めていたのだけれど、後でForumに最後にもスペースがないと駄目みたいな情報があって微修正したらAC。HASHING与えられた文字列に対するハッシュ値を計算して出力し、最後にその自分自身のコードのハッシュ値を出力するコードを書く。(ハッシュ関数は与えられている)コードに埋め込む(自分自身の)ハッシュ値の変動がハッシュ値に影響するのでいくつも試してみました。PALINDROME与えられた文字列が回文(palindrome)になっているか否かをYES/NOで返すコードを書く。そのコード自体も回文となっていなければならない。Cのコードを回文にするのは簡単です*1が後は純粋ゴルフ。RECURRENCE与えられた数値(※1e18とか来るかも)に対し演算を行い結果を返すサンプルコードが与えられているが、このコードは再帰しまくっていて巨大な数値に対し時間もメモリも食いまくるため現実的な実行は不可能である。コードの計算量を減らし、時間内に結果が出るように書きなおすのがこの問題。求めているのにほぼ等しい。いうのはfib(n)のnが2以下の場合に0を返すようになっている点が異なるため。巨大な数値に対するフィボナッチ数の演算は行列の累乗とかすれば速いのでまあそうするのですがそのコードをどれだけ短くできるかという点で経験豊富な強豪の皆さんと差がついてしまった感じ。COMPOSITE自分自身のコードを出力するQuineの変形で、自分自身のコードの先頭から合成数(=素数以外)番目の文字のみを出力するコードを書く。(先頭を0番目とする)素数か素数でないかを表すスケール**--*-*-***-*-***-*-***-*****-*-*****-***-*-***-*****-*****-*-*****-***-*-*****-***-*****-*******-***-*-***-*-***-*************-***-*****-*-*********-*-*****-*****-***-*****-*****-*-*********-*-***-*-***********-***********-***-*-***-*****-*-*********-*****-*****-*****-*-*****-***-*-*********-*************-***-*-***-*************-*****-*********-*-***-*****-*******-*****-*****-***-*****-*******-***-*******-*********-*-*********-*-*****-***-*****-*******-***-*-***-***********-*******-***-*******-***-*****-***********-*-*********...とか用意*2して、表示したくない文字が素数番目に行くように調整しながら手書きしました。OUTPUT入力データと出力データがあらかじめ与えられ、入力データを受けて出力データを返すコードを書く。出力データをまるまる埋め込んでも10000バイト未満なので点は貰えるんだけど、パターンを読み解いてできるだけ短いコードを書く勝負。誰かが9000台後半の得点を出している時点でパターンがあることが示唆されるわけで。WONDERWOMAN与えられたアスキーアート(を上下反転したもの)を出力するコードを書く。(データは6086バイトなのでそのまま埋め込んでも点は貰えるんだけど)これはデータ圧縮合戦。今年はハフマン符号化にこだわりすぎて一定以上に縮まらなかった。kinabaさんみたいにデータの特性に合ったopコードみたいなのを設計する方が良かったりするのですね。圧縮データをバイナリのまま文字列としてコードに埋め込んでいます。literalとかwarning出されますけど、そのまま表示するわけではないしデータ長もわかってるし実行には支障ありません。パラメータを替えて色々試したいので、コードは自動生成です。»@naoya_t自然言語処理とか機械学習とか競技プログラミングとか。競プロ精進記録は別ブログ🔒に移しました。yukicoder遅延伝搬セグメント木の復習をしたので、beetさん作問のセグ木コンテスト(2019/9/6開催)の問題を解いてみた。サウスタワー23Fなんで自分に参加権が来たのかよく分からないオンサイトイベントに参加してきた話。146のQ4でN個の点の3次元マンハッタン距離の最大値を求める問題が出たのでメモ。"なお、接尾辞配列を構成するアルゴリズムは他にも多数存在しています。14:00-FORCIAさんで開催されたオンサイトのゆるふわコンテストに参加。過去問コンテスト後に読んだ問題たち。ここで出てくるテクニックもこの機会にぜひ身につけておきたい。