ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

条件の作成

ABC050 C - Lining Up

問題 提出コード 人生初の嘘解法を通しました!!!割と条件を省いて書いたのですが通ってしまったので、サンプルが弱いと思います(ACしない凡例が存在します)。 例えば、自分のコードだと 5 0 0 0 2 2 という入力で答えが6になります(本来、このような入力…

ABC048 D - An Ordinary Game

問題 提出コード グランディ数を利用する問題は、ぱっとみで使うだろうなーというのがわかっても、そこから答えに結び付けるのが難しくていつも解くのに時間がかかります… 解法 お互いが操作できなくなる状態では、必ず2種類の文字になっていて、それが交互…

Tenka1 Programmer Contest (2017) C - 4/N

問題 提出コード 解法 について全探索をすると間に合わないです。ので、について全探索をして、そのときのを求めればよいです。 全てが以上以下になる解が存在するという保証があるので、はこの範囲で全探索をします。 を、となるような式にうまく変形します…

AOJ 2707 - 監獄

問題 提出コード 解法 まず、答えが仮にxであったとします。そのとき、xは1回目の操作でどこにいくか、ということを考えてみると、 x - 1 - x/k となります。k、2k、3k…の人が処刑されるので、その人数分引けばいい、ということです。 次に、後ろから考えま…

ARC103 E - Tr/ee

問題 提出コード 解法 考察は終わっていましたが実装が間に合いませんでした。 まず、木を作るのに必要な要素は3つあります。 sの最後の文字が0 辺を1つ選んだ時点で、サイズはnより小さくなってしまうので、条件を満たすことができません。 sの最初の文字が…

AOJ 2369 - CatChecker

問題 提出コード 解法 後ろから攻めていき、最後が空文字列になるかどうかで判定します。 猫の鳴き声をCATとすると、mCATeCATw となっているはずなので、まず両端がそれぞれmおよびwになっているかどうか判定します。この時点で辻褄があっていなければ答えは…

AOJ 2708 - ABC Gene

問題 提出コード 解法 この問題は、初期状態であるABCから2手分ぐらいを書き出し、あとは後ろから見ていくということに気づくと、うまく解くことができます。 後ろから見ていったとき、ABCと綺麗に並んでいる部分は、かならず1手前で1文字を置換した結果でき…

ABC086 D - Checker

問題 提出コード 解法 散らばっている情報を、まずはK×Kマスの中に押し込みます。 例えば、(x,y)がWという希望は、(x+K,y)、もしくは(x,y+K)がBという希望と同じであり、また(x+K,y+K)がWであるという希望とも同じです。 これを利用すると、白を0、黒を1と表…

ABC086 C - Traveling

問題 提出コード 解法 ぱっとみ幅優先、っぽくみえて全然違いました。 プランのi番目の位置と時刻から、i+1番目の時刻に、指定された位置に行くことができるかどうかを全部調べていきます。 i=0のときはt、x、y全て0とします。 i番目の情報をt[i],x[i],y[i]…

SnackDown 2016 - VCake

問題 縦と横が長さR,Cの長方形があり、それをいくつかの条件に基づいて切断し、指定された3つの面積(M,J,K)になるように分けろ、という問題です。 切断の条件は3つで、 長方形の辺と平行に切断する 一度切れ込みを入れたら、その部分は端から端まで切断する …

ABC014 D - 閉路

D - 閉路 提出コード 初めてLCAを扱う問題に触れました。 現在の木の根を適当に決めます。どこでもいいです。 新しく追加する辺の2つの頂点の番号をa,bとします。このとき、閉路の長さは、 (aの根からの深さ)+(bの根からの深さ)-2×(aとbの共通の祖先で最も近…

AOJ 2331 - 友だちの誘い方

友だちの誘い方 提出コード まずは脳死でいもす法を書いてみます。それぞれの入力に対し、 memo[a]に1を、memo[b+1]に-1を足して、memo[0]から累積和をとっていきます。 すると、i<=memo[i]+1のとき、i-1人を誘うことができるようになっていますので、この条…

ARC102 D - All Your Paths are Different Lengths

D - All Your Paths are Different Lengths 提出コード n進数を利用する、というところまではよかったのですがそこから歯が立ちませんでした。 結論から言うと2進数を利用します。 まずは大元となる2進数のグラフを作成します。 となるうちの最大のxを求めま…

ABC107 D - Median of Medians

D - Median of Medians 提出コード 初めてBITを使った問題です。 この問題では、中央値となる条件をうまく言い換えていき、最終的に転倒数を求める問題に帰着させます。転倒数を求める段階で、BITを利用します。蟻本をみたらそこにも載っていた問題になりま…

ABC006 C - スフィンクスのなぞなぞ

C - スフィンクスのなぞなぞ 提出コード つるかめ算の3つバージョンですね。 まず初めに、全て2本にしても余る(n×2>m)の場合と、全て4本にしても足りない場合(n×4<m)の場合は、答えが-1のパターンとなります。 次に、真ん中、つまり足が3本の老人に注目します。 とりあえず全員が老人だと仮定したときに、目標となるmとのずれを調べます。 もちろん、全て老人だった場合にmと一致する場合は、それが答えとなります。 n×3>mの場合 足を減らす必要があります。差の分だけ、老人を大人に置き換えてあげると、うまくいき</m)の場合は、答えが-1のパターンとなります。>…

AOJ 0601 - フクロモモンガ(JOI2013本戦4)

フクロモモンガ | Aizu Online Judge 提出コード けんちょんさんのブログに載っていたため解いたのですが、DP!と思って問題を読んでみたらむしろダイクストラ法の問題だな、という感想でした。条件がそこそこ複雑だったので、配列の要素を変数でいちいち置…

AOJ 1133 - Water Tank

Water Tank | Aizu Online Judge 提出コード そのまま実装するとかなり重くなりそうなので、なにかいい手がないかを調べます。 初見で解けなかったときに、こちらのブログ( Water Tank (AOJ1133) - sigma425のブログ )に一度目を通していたため、トップダウ…

ABC069

同学年の4人でバーチャルコンテストなるものを初めて開きました。 ABCの番号は100面ダイスを使いました。 A - K-City 提出コード サンプルの図とにらめっこして、をすれば終わりです。 B - i18n 提出コード 素直に、文字列の先頭、間の個数、最後の文字を出…

AGC26

二回目のAGCでした。 A - Colorful Slimes 2 提出コード まず入力時に、どの色のスライムがいるかを調べます。前から順番にスライムをチェックしていって、一個前のスライムと色が同じだったらその都度色を現時点で使ってない色に変えていけば、最短手数で合…

SoundHound Inc. Programming Contest 2018 -Masters Tournament-

コンテスト開始2分前ぐらいまでアイスを食べていて、乗り遅れそうになりました。 A - F 提出コード if文を使って、aとbの足し算、掛け算が15になるかどうかを調べます。どちらでもなければその時用の出力をして終わりです。 B - Acrostic 提出コード 入力用…

ICPC国内予選2018に参加してきました

というわけでとりあえず参加だけしてきました。 べるくんとやまさんの三人チームで出場しました。基本的にやまさんが考察をし、僕が実装して、困ったらべるくんがデバッグやほかの問題の実装をするというスタイルでいきました。 A問題 所得格差 提出コード …

AOJ 1197 - サイコロ職人

サイコロ職人の朝は早い。 サイコロ職人 | Aizu Online Judge 提出コード さて、立方体を転がしてある面が下になった回数をカウントしたときに、指定された6つの数字のグループと一致するように転がせ、という問題です。 転がす方向は東西南北の4通りであり…