ラッキー空間空間

AtCoderブログ

Codeforces Round #533 B. Dima and a Bad XOR

 今まで参加したコンテストやイベントのことしか記事にしてなかったのでたまには個人的に面白いと思った問題を記事にしようと思います。

 

問題概要(自分で和訳したので誤っている可能性あり)

Problem - B - Codeforces

 各項が非負整数のn*mの行列aが与えられる。数列c1,c2,...,cnであってa(1,c1) xor a(2,c2) xor ... a(n,cn) > 0となる数列はあるか?なければ”NIE"をあれば出力し、あれば”TAK"、そして数列c1,c2,...,cnを出力せよ。(文字を80%より小さくする方法がわからなかったのでa(i,j)でaのi行j列目を表しています。リンク先の問題本文を読んだ方がわかりやすいかも)

 

着目点

 xorを取って>0、と言っているが非負整数でxorを取ると0より小さくはならないので≠0と言い換えられる。a(1,c1) xor a(2,c2) xor ... a(n,cn)が0になったとするとこのうちの整数を一つ変えるとxorを取った値が0ではなくなる(これはある数xとxorを取って0になる数はx自身以外に存在しないことを考えるとわかりやすい(?))。

 

解法

 まずは数列cを1,1,...1としてxorをとる。これが0でなければそのまま出力。0であって全ての行が単一の整数で構成されている行だったら”NIE"、そうでなければ複数の整数で構成されている行のうち1つをx行目とするとcx=1をa(x,1)≠a(x,cx)となるcxに変更する。

KUPC 2019

 オンラインから参加しました。

A問題

 ソートして最大-Xの要素を数える。

B問題

 200点問題なので簡単ですね()。まずUnionFindして次に根以外は根に重み、価値を付加して自信の重み、価値を0にする。最後に普通のナップサック。

C問題

 今回一番面白かった問題。とりあえず1gのやついっぱい欲しい!と思ったので1gをk個は確定。これでkgまでは測れる。次に2k+1gが欲しい(1gをk個反対側に置けばk+1~測れるので)!となるので2k+1gを用意する。いっぱいあった方がお得感あるのでまたk個用意する。これでk(2k+2)gまでは測れる。・・・、とやっていくと答えが出る。2倍とかkの累乗とかが出てくるので(語彙力不足)時間が足りる。

D問題

 とりあえず0が連続している部分と1が連続している部分に分けて考えればいいことがわかる(0と1の境目のところで両者の持っている枚数が等しくなる必要があるので)。次に分け方を例えば1~6をAが勝つように分配するならBBBAAAとかBABBAAとか、Aの数が途中でBを超えない並べ方を数え上げればいいことがわかる(かっこの並べ方みたいに)。ここでよく考えるとカタラン数、という言葉がふと頭の中に浮かび上がったのでググるとまさにこれだということがわかる。OEISより天啓の方が早くて楽なのでオススメですよ。modの逆元めんどくさいけど10^5は流石に埋め込めないのでちゃんと計算する。

 

 E問題結構考えたけどわからなかったので撤退し4完。順位表見た感じまあまあいい結果(その後のこどふぉ爆死したけど)。

AtCoderで水色になるまでにやったこと

 9月28日のABCで水色になったのでかなり今更感ありますがAtCoderでは色が変わったら記念ブログを書くことが通例(?)なので水色になるまでのことをまとめようと思います。

はじめに

 

f:id:nkrnkr3:20191010003618p:plain

 既に水色になってからもう1コンテストあったので画像の通り現レートは1227になってます。他の方の記事だとこのアルゴリズムは必須だよね、とかこのアルゴリズムはなくてもいけるよね、とかいうのが多いので被らないように僕はアルゴリズム等以外の要素のやったことについてまとめます。

競プロ始めてからの時系列まとめ

プログラミング関連の講義を取る(4月頃:体感パフォ100上昇)

 アルゴリズムの授業を取ったのですが深さ優先探索やら幅優先探索やらDPやら競プロでガッツリ使うようなアルゴリズムが多く取り上げられていたのでここで割と強くなりました。競プロ関連の講義は競プロの精進にもなって単位も楽に取れていいですね。

競プロを始める(5月下旬:体感パフォ100上昇)

 競技プログラミングを始めました。競プロを始めるとパフォーマンスが上がります。

VSCodeを入れる(7月頃:体感パフォ10上昇)

 コード書きかけで別の問題に移る時とか便利です。あと自動補完があったりタブの切り替えが紛らわしくなくなったり背景を好きに変えられるのでモチベが上がったりします。()

テンプレートを整備する(7月頃:体感パフォ200上昇)

 今までは全部インクルードとstd::省略をAtCoder公式のチュートリアルページからコピペしていましたがせっかくVSCodeを入れたのでテンプレートを作りました。

f:id:nkrnkr3:20191010011237p:plain

 intのINFはmodで代用しています。dx[4]とdy[4]は使ったことないですがそれ以外は全てかなりの頻度で使ってます。

オンサイトに行く(9月中旬:体感パフォ300上昇)

 強い人に会ってモチベが上がりました。あと思考が詰まった時みんなどうしてるのかとかちょっと観察して参考にしました。

ツイッターで競プロerをフォローする(オンサイト後:体感パフォ100上昇)

 オンサイトに行った時にお会いした人をフォローして、せっかくなので競プロerを大勢フォローしたら入ってくる情報量もライバルの人数も格段に増えました。ツイッターは偉大ですね。

ペイントツール考察を始める(オンサイト後:体感パフォ100上昇)

 これより前は脳内考察だったのですがオンサイトで隣の方が紙考察してたので試しにペイントツールで考察してみたら法則見つけやすくなって良かったです。紙ではなくペイントツールを使ったのはレイヤー分け、色分けができるというメリットがあったからですがどちらも全く使いませんでした。

蟻本を買う(9月末:体感パフォ300上昇)

 AtCoderやってる人々から推されているバイブルです。このとき既に水色になっていますが細かいことは気にしない。

CodeForceを始める(9月末:体感パフォ100上昇)

 AtCoderで適切な難易度の問題が少なくなってきたので始めました。AtCoderであんだけ苦労した水色に一瞬でなれたので複雑な気持ちになりましたがAtCoderとは問題傾向やシステムがちょっと違うので守備範囲が広がった気がします。もうすぐCodeForceで青色になるまでにやったこと、の記事を書けるような気がします。

ライブラリを整備する(10月〜:体感パフォ100上昇)

 せっかく蟻本を買ったのでry。

紙考察を始める(この前:体感パフォ300上昇)

 マウスのついていないノーパソでお絵かき考察するよりも紙の方が描きやすかったです。

 

これからの目標

 青色になりてぇ。

AtCoder Grand Contest 039

A問題

 絶対に許さない。

B問題

 紙にテストケース3つ全てを書いて考察。どうやら長さ奇数の閉路があるとダメ、それ以外なら可能、らしい。最大のkは元のグラフの端から端までの長さだな、と思ったのでとりあえず先述の可能かどうかの条件は置いといて(この時点では適当な点からBFSして既に深さが書き込まれている所に新しく深さが上書きされるようなシチュエーションがあったらダメ、とかで考えていたがめんどくさいので後回しにした)、ワーシャルフロイドで全点間距離を求める。ワーシャルフロイド書き終わった時点である点AからB,Cへの距離が同じで、B,Cに辺が張られていると奇数の閉路になることに気づいたのでそれを奇数閉路検出に使った。

第一回日本最強プログラマー学生選手権参加記

 予選落ちなのでセミナーから参加しました。

 

予選

A問題

 正直あまり印象に残っていませんでしたがコード見た感じ全探索です。

B問題

 天才なので数列Aの内部にある転倒数とAを並べた際にできる転倒数を分けて数えて、最後に足し合わせれば良いとわかる。転倒数を数える方法をググるバブルソートすればいいことがわかる。ネット上のソース見ながらバブルソートを実装する。WAする。完。

 

 コンテスト後によく見てみるとバブルソート部分が厳密なバブルソートではない(隣接項ではなくても交換できる)コードになっていたので、うまくいかなかった。1完の2333位でAt Coder初参加回を含めてもパフォーマンスが自己ワースト1位となった。本戦は無理でも懇親会参加したかったので絶望して泣いた。招待メール来て本当に良かった。

 

勝戦当日

セミナー

 電通のグループ企業(?)の方が講演してくださった。これが45分続くのかあとため息をついていたら丁度いいくらいの長さだったので良かった。内容は電通がどんなことしてるのかとかプログラミングがどう企業で役立ってるのかとか知れて面白かった。

表彰式

 聞いたことある名前ばかりが呼ばれていてすげえ(語彙力皆無)ってなった。

休憩時間

 交流が始まる気配がなかったので蟻本を購入するか検討していたので近くの本屋にいってざっと立ち読み。購入を決意するもお金が足りなかったので店を出る(今日買った)。現場がどうなってるか知りたくてツイッターをみるとすでに交流が始まっているっぽかったので急いで戻る。

 名札とか見ながら知ってる人探してたらゆるふわオンサイトで話した方がいたので会話する。色々話した後でchokudaiさんのハンドスプリングを見ていないことに気づき、ロビー的なところに戻る。ハンドスプリングはしてなかったが、紙芝居のおじさんみたいにchokudaiさんが真ん中で喋ってて周りで人々が聞いていたので混じる。At Coderのレートが最近きつくなってきてる理由とか色々聞けた(ハンドスプリングは結局終了後にツイッターで見た)。その後ツイッターアカウントの教え合いみたいなのが始まったのでツイッターを交換していると会場に入れるようになる。

懇親会

 ツイッターのFFがいたので喋った。飯解禁された瞬間寿司に向かったけど寿司早解き勢が強すぎて遅れをとったので並んでいると隣にyosupoさんがいたのでレート差のあまり気絶した。決勝進出者と同じ飯食べてるの申し訳ねぇと思いながら胃ナップザックをしていくと胃の容量を超えてしまったのでうずくまった。終了間際に会場隅でうずくまってる人いたら僕です。

その他

 今週末はこれ以外にも水色になったりこどふぉ初参加したりイベント過多だったのでそれについても後日書きたいです。

AtCoder Beginner Contest 142

 レート1190なので入水を狙って参加。

A問題

 (n+1)/2/nですがうっかり入力の時点でnをdoubleにしてた。そしてdouble型の出力不安だから桁数指定しようかな、でも桁数指定わからないからググろう、桁数指定になってないぞ!?、fixed必要なのか、とか色々やってたら4分かかった。フレンド内最遅。小数点以下出る問題やめて・・・。

B問題

 特に問題なくパス。

C問題

 問題文ざっと読んでなんとなくx[a[i]-1]=i+1を出力してみたら行けた。

D問題

 とりあえずまず公約数考えるなら最大公約数の約数考えればいいだろ、と考えて、その中で小さい順に取ればよくね→素因数分解、という思考の流れ。

E問題

 Nがかなり小さい、Mもそこそこ小さいのでそこから考えるんだろうけど何も思いつかない。青以上は大体みんな一瞬で通してたので典型問題なのかと思って調べてみたけど何も見つからず、リタイア。ac-predictorで1200にだんだん近づいていく終了後のレート予想を見ながらヒヤヒヤする。22:40現在の予想レートは1202。正式に出るまでわかりませんがおそらく入水しました!

AtCoder Grand Contest 038

 700点問題は解ける気しないがA早解きすれば入水できるかもしれないのでとりあえず参加。提出してWAのまま沈没が一番怖い。

 

A問題

 問題文を読んで列の交換、行の交換ができることに気づく。フィーリングで

111000・・・

111000・・・

・・・・・・・・・

・・・・・・・・・

みたいに1を左上に寄せてみる。ただしこれだと右側と下側が0だけになってしまうのでダメ。ここでなんとなく右下にも1を詰めてみる。テストケース1でいうと

100

011

011

みたいになる。いける!だけどこれでどこまでいけるのかわからないのでテストケース2もやってみる。

00000

になる。いけない><。ここでA,Bが逆だったことに気づく。頭の中で考えてみたら全ケースこれでいけるので出す。なんか出力を間違えて数字と数字の間にスペースを入れてたので1WA。

B~D問題

とりあえず目を通したけど無理そう。ここで粘ってもしょうがなさそうだし暇つぶし程度にE,Fを見ることにする。

E,F問題

Eは見た瞬間ヤバいとわかったので無視。F問題はなんとなくP[P[i]]=iになる組は入れ替え可能なので入れ替えたほうが良くなるなら入れ替える、という方針で一応やってみるがテストケース2が合わない。順列の3つの要素A,B,Cがあった時にB,C,Aに入れ替えることが可能なケースを見逃してた。これは有向グラフを張って閉路を検出すればできる気がしたがそんな能力はないし8の字とかになってたら処理できないので諦める。冷静に考えてF問題なんて見てる暇あったらB問題やったほうがいいことに気づいたのでB問題に戻ったけどわからないので順位表眺めながらのんびりしてコンテストを終える。