1234 Ball Toss 学生が輪になって並んで規則に従ってボールを投げる。やるだけ。最初に投げる生徒は初めはボールを受け取っていないことに注意！！！

2777 Count Color 線分があって、「ある範囲をある色で塗りつぶせ」というクエリと「ある範囲には何種類の色が使われているか」というクエリが与えられるから処理せよという問題。色は高々30種類。Segment Tree。割と楽に書ける。色の処理はビット演算を使う…

最悪でした。問題についてはパスワードが今ないので書けないのですが。 問題は概して簡単（8,9除く） 開始早々ログインできない。そのおかげで終了が１時間遅延する ログインできても、ろくに送信できない。２〜３問送ったらすぐに繋がらなくなる（ただ、こ…

ちょっと遅いかもだけど。 Day 0 (成田) 成田エクスプレス。速いけど遠い IOIなどの問題の解説。APIOの問題の解答に驚愕 「ルービックキューブみたいなもの」が好評 Day 1（成田−トロント−ウォータールー） ホテルはよかった。朝食に「うどん」があったぱな…

3181 Dollar Dayz 1ドルからKドルまでの品物がある。あなたはNドル持っている。Nドル丁度使って品物を買う方法（同じ品物をいくら買ってもよい）は何通りあるか？という問題。多倍長+DP。 2838 Graph Connectivity 無向グラフに対して、「辺の連結」「辺の削…

1717 Dominoes 1000個以下のドミノがあって、横に並んでる。何個かひっくり返して上下の数の和の差を最小にしたい。最低何個ひっくり返せばいい？DPやるだけ 3041 Asteroids 危険な小惑星があるらしい。それをスターライトブレイカーかレールガンか知らない…

ひさしぶりのPKU。

JOI夏季セミナーでなぜかスリザーリンクを解くプログラムを作ってしまったので、スリザーリンクをプログラムで解く手法について説明したいと思います。 下準備 人間はスリザーリンクの問題をループの線ベースで考えて解いているが、これはプログラムに実装し…

Memory 50枚のカードで神経衰弱をやる。100回までひっくり返していい。ばかにーするなー！ Traffic Congestion 簡単な木DP Maze プログラムで効率よく解きづらい問題。プログラム＋手作業で安定？ Saveit ボス問題。部分点狙い安定 どうやら全域木を使うと簡…

いろいろとカオスな問題。 Cluedo 最初見たときはスルーしたけどめちゃくちゃ簡単。本当にやるだけ Hotter Colder 50点は簡単で、75+α点は気がつけばいける。満点は無理(満点取った人はいない)。 Quality of Living 二分探索やるだけ。 Language 今回で一番…

アルゴリズム擬人化なんてやるひとそんないない。そもそもやるもんじゃない。完全にいろいろとおかしい気がする。 各キャラはどうやってアルゴリズムを発動するんだろう。 クイックソートたん 自明なツンデレ。最悪計算量がO(N^2)的な意味で。 ツインテール…

250 CarrotJumping x -> 4x+3, 8x+7という移動が許されてるうさぎ。うさぎは10万回までしか動けない（疲れちゃうから）。1,000,000,007の倍数の場所に着いたらクリア。クリアするまで何回動く？x' := x+1という変換をやるとわりとうれしかったりする。あとは…

IOI 2005 Mean Sequence 範囲についてやるだけ IOI 2005 Garden 2つの重ならない長方形を取るので、ある直線で2つのregionにぶった切ってそれぞれに長方形が1つずつ入ってるとして考える。 長方形の周の長さの最短は、縦の位置を固定して、左から走査して見…

3419 Difference Is Beautiful 予め、perfect sequenceの左端を固定したときに右端をどこまで伸ばせるかを配列に持っておく。この操作はだいたいO(N)でできる。 各クエリーについて、ある点を境に「クエリーの右端まで達しない」「クエリーの右端で右端でつ…

好ましかった！ 250 正六角形を単位とする平面があって、池と島？がある。境界線の長さは？正六角形でも正方形とほとんど変わらないやるだけ。場合分けぐらい。 500 整数の長さをもつ木のスティックがたくさんある。 そいつらから、2本組をできるだけ多く作…

ぷきゅるのもひさしぶり…

まっさかさま→青 250 なんか動物が餌を貪欲に食べる。頭数が増えるほどよく食べる。普通にgreedyで通る。なんで二分探索なんて書いたんだろう。二分探索で間違いということはないんだけどさあ 550 プロフィール。プロフィールには友人のうちK人がランダムに…

問題 従属関係が根付き木な、N(1 Q(1 解法

やっぱり赤色って目立つよね。はやくsemiexpになりたい。このままだと青色になりそう。 250 ポテトゲーム。1,4,16,64,…個ぐらい取れる石取りゲーム。取れなくなったら負け。両者最善を尽くす。どっちが勝つ？4で割って余り足して(ryってやってればいいんじゃ…

そんなものこの世にない 250 整数を2で割って（小数点以下切り捨て）、素数じゃなくなるまで続ける。素数がK個以上できるような整数で、N以下で最大のものを求めよ。Nは1000万以下。 問題文の理解に時間を食う。エラトステネス＋DP。Nが大きいのでやたらとメ…

APIO（アジア太平洋情報オリンピック）を受けてきました。 問題概要は公式サイトにあるので省略。難易度的には、「ぱない」としか形容のしようがありません。 1. Commando 50点まではO(n^2)のDPで取れる（取れた）。そこから先がわからない。 2. Patrol 非常…

死にました。 250 すごく広い映画館に、２人が隣りあって座る。いくつかの椅子は埋まってる。座る位置は何通りあるか答えよ。喩えて言うなら、教室に入ろうとしたら黒板消し(long long)が挟まってて、それは避けたけど油断してたら地面に張ってあった黒板消…

「やるだけ」な問題ばっかり。 2559 Largest Rectangle in a Histogram 前回O(n log n)のコードを書いていたので解き直し。 左から見ていって、高さが常に広義単調増加になるようにスタックに積んでいく。 もし、前の高さより低くなったら、広義単調増加にな…

250 0と、約数が奇数個ある数が当選番号で（前に余計な0がついているかもしれない）、今ある券に何回か変更（ある１桁を任意の他の桁に変える）を施して当選番号にする。最小の変更の回数を求めよ。 当選番号は平方数。ある程度の範囲の平方数に対して全探査…

2001 Shortest Prefixes Trie 2769 Reduced ID Numbers 差をとって約数をとる 2530 Tetris Alphabet やるだけ 2008 Moo University - Team Tryouts まずheightでソート。 そして各height以上の牛を列挙し、weightでソート。 weightの大きい方から順になめて…

情報オリンピック、数学オリンピック合宿（６泊７日×２）より帰還しました。 各日について Day0：とくになし Day1：90分で解ける問題 Day2：時間が余る問題 Day3：Output Onlyに戦慄 Day4：「高速道路」が面白かった。でも時間余る Day5：代表発表会。JOI合…

IOIカナダ大会の日本代表になりました。 合宿の感想 １日目：２時間半余って退屈 ２日目：あれ去年より簡単？ ３日目：コーナーケースで落として萎え ４日目：楽しかったです ５日目：合宿一番の難問、「記者会見」が襲い掛かってきました 失敗したこと ・表…

1. 概要 すたっきゅん数とは、 【定義】10^N 未満の自然数 n であって、 n^2 を10進法表記して同じ数が連続で N+1 個以上並ぶ数のうち、 n≡0 (mod 10) でないものを「すたっきゅん数」と定義する こんな数です。 2. 普通に見つける方法 nを小さい方から試し…

はじめてTopCoderに参加しました。 250 赤球と青球と赤箱と青箱があって、球を箱に入れる。やるだけ、でも8分ぐらいかかった。表を書いたら一発だった… 焦ってたのかな。 500 文字列の桁数nが与えられたとき、辞書順に並べたときにm番目にくるカラフルな文字…