青い厚揚げ杯2019 ヤジリン部門に投稿した問題を解説
はじめに
9, 38, 39, 43の問題を投稿しました。
ヤバリンもどきを2問も投稿してしまいすみませんでした。
難易度は、9が「ふつう〜やや難しい」、38が「ふつう」、39が「難しい」、43が「やや難しい〜難しい」想定でした。
問題9
この問題のキモ(厚揚げポイント)は、一見応用手筋が必要に見えて実際にはいらないため初心者でも簡単に解けることです。
自明なマスを埋めていくと、SP1さんの配信のように下図の盤面になります。
SP1さんはここで左上を強引に解いていましたが、8R6Cから8R5Cに線が引けます。
そして、7R5Cから8R5Cへは明らかに手筋が伸びないため、上(6R5C)への線が続きます。
以降は線を書ける場所が限定されるので、自然と問題が解けます。
大きい数字で黒マスが確定し、応用手筋を使わないけれど解いた感が得られる部分に主眼を置いた問題でした。
問題38
この問題は「ふつう」らしく、気持よく解いてもらおうと思って作成しました。盤面の形状もそこそこ綺麗に揃えたつもりです。
特に、R1, 2(上2段)とR9, 10(下2段)の部分で一気に線が書ける爽快感が一番の厚揚げポイントです。
また、そこに向かうまでの過程も悩むこと無く線が引けるが若干の厚揚げポイントかなと思います。
問題39
ヤバリンです。いいえ、ヤバリンではありません。
まず始めに自明な手を書きます。
すると、嬉しいことに(?)下の22は応用手筋に似た形になりましたね。
C1はどちらもドットマスなので、応用手筋通りの2パターンと、これの派生系(C4の黒マスをC3に移動した形)2パターン、以上の4パターンを考えれば良いことが分かります。
まずは派生系から見ていきましょう。
これらはどちらも黒マスを置いて自明な線引きをしようとするとすぐ破綻することが分かります。
(それぞれR5C2での分岐とR7C2の少ループ禁)
次に普段の2パターンについて考えます。
どちらかが破綻するはずなので仮置きをしてしまいましょう。
不正解の手を置くとこうなります。
R1C5の↓4の黒マスはR9, 10に1つしか置けないので、R2C5とR4C5の黒マスが確定します。
しかし、この時点でR5C4に分岐が生じてしまうので破綻します。
よって、もう一つの置き方が正着となることが分かります。
不正解を引け続けないと少し大変ですが、正解手を進んでも「正解手かな?」となって不正解手を潰しに行くのでロスしても数十秒でしょう。
先ほどと同様の考察により、R2C5とR4C5の黒マスが確定します。
少し形は変則的ですが、R(3, 4)C3の→22は応用手筋と同じ考え方により、黒マスが確定します。
ここで、R3C9が上(R2C9)に伸びてしまうと出口が1つ(R2C6)なので小ループ禁となってしまい、下(R4C9)へと伸びることが分かります。
また、左上も一気に線が引けること(ここ厚揚げポイント!)が分かっているので引いてしまいましょう。
C9, 10に関しては偶奇則でドットとR8C8からR8C9への線が確定し、R9C3に関しては黒マスが置かれるとR8C3で少ループ禁が発生してしまうためドットが確定します。
すると、R9C8の←2の黒マスが壁際定理からR9C5, R9C8に確定することが分かります。
R7C6は偶奇則から下(R8C6)へと伸びることが分かります。
以降流れに従ってマスを埋めていけば、この問題は終了です。
一見難しいし解いていても難しい問題ですが、本質はここ↓の発展手筋です。
手筋集(ヤジリン) - ペンシルパズルWiki
最初の4パターン考察はやや大変ですが、破綻はかなり浅く済むようになっていると思います。
問題43
盤面が風車の様で綺麗(当社比)な問題。
青い厚揚げさんだったら盤面を綺麗にしてくる問題を入れてくるだろうという読みのもと作問しました。
これは難易度「やや難しい〜難しい」想定だったので、間違いなくヤバリンではないはずなのですがなぜか問題39と共に黒い三連星的な悪名を頂くことになってしまいました。
解法ですが、まずは自明な手筋を書いていきましょう。
R7C1はR7C8の←3から黒マスが確定します。
次に、考察するパターンが少なそうなR7C8の←3を考えていきます。
通常では、C3, 4とC6, 7の計4パターンを考える必要がありますが、この問題では実はそれぞれ独立して破綻します。(C3, 4は左下の遇奇則から、C6, 7はR3C(6, 7)の↓2↓2の黒マスが置ききれないため)
よって、盤面は以下の様に決定します。
次に、R3C(6, 7)の↓2↓2の入るマスを考えれば、下図のようになることが分かります。
同様に、R(4, 5)C2の→2→2も下図の状態まで確定します。
R2C8はR8C8の↑2から黒マスが確定、C10の未確定マスもR10C10の↑1によりドットマスが確定します。
R9C9の線はは遇奇則によって上(R8C9)に伸びることが分かります。
これによってR10C1の→1の黒マスが確定するなどして下図の状態まで一気に盤面が進みます。
そして、ここでこの問題最大の厚揚げポイントです。
R9C4の↑2のヒントを使うのが筋が良さそうなのでこれを頼りに仮置きを進めて行きますが、正着手以外はR1C10の←1が上手くいかずくそぅとなるような配置になっています。
最終的には下図のように解き終わります。
おわりに
厚揚げ杯2019とても楽しかったですね。
逆張りで選んで頂けたのかもしれませんが、9番6票、38番10票、39番2票、43番5票とそこそこの得票数が得ることができました。
私の問題に投票して頂いた皆様、また厚揚げ杯2019にご参加頂いた皆様本当にありがとうございました。
ちなみに、この記事はSP1さんが39, 41, 43番の問題をまとめて「やってんねぇ」と評価したため、ヤバリンを寄稿してしまい申し訳ございません用の記事のつもりでした。(蓋を開けてみれば……茶番乙)
CODE FESTIVAL 2015 参加記
※今コンテストは(心境的に)写真を撮ってる余裕がなかったので、文字のみです。
(追記)まとまりのない文章になってしまったし、書き終ってからあれも書けば良かったなということが思い浮かぶ……。まぁ、いいや。
予選前
9月2日に某社からメールが来たので、その日のうちにレジった。
しかし、今年に入ってから参加した競プロのコンテストは、
- Donutsプロコン 2015
- ARC 035
- ABC 020, 023
……(・ω・)スクナイ
「去年はTHANKS B日程で9位とれたし、今年も最悪でもTHANKSには参加できるように頑張ろう」って思ったけど、これではTHANKS出場すら怪しいのではないかと不安になる。
予選A
コンテスト開始直前にPCがフリーズして再起動。
結局、10分弱遅れて参加。
順位は44分3完で385位で、案の定予選通過ならず。
この段階で本選出場は諦めて目標をTHANKS出場にシフトしていた。
予選B前
某K研究室に遊びに行った。
そこで、ICPCにチームkonohaで出場している先輩との接触に成功。
先輩は予選A全完で本戦出場が決定していると聞き、本戦参加へのモチベが少し回復した。
予選B
前述通りモチベは少し回復したものの、特に練習をすることもなく当日を迎える。
結果は、101分3完+部分点で144位。
全完できるとは思っていなかったし、THANKSの出場権もほぼ確定したので個人的には及第点。
ただ、もう少し早くから部分点を取れていればとは感じた。
予選後
某社からのメールがくることを祈るだけの簡単なお仕事。
しかし1回目の通知では、自分の1つ上の順位の人までしかメールが送られずTwitter上で軽く発狂してた。
最終的には次の通知で本戦の参加権を得られたので良かった。
本選前(~11/10)
実験レポートに全力出してたので、さすがに競プロどころではなかった。
個別指導塾のバイトの方も、丁度教え子がテスト前で色々と準備しなくてはならなかったので余計に時間が足りなかった。
人間的な生活を送りたかった(´ー`)
本戦数日前
ゴルフの問題に目を通す。とりあえず、Aだけはやってみようと思いプログラム書いてた。
ショートコーディングの記事読み進めるほど闇を感じ、数日でどうこうできる分野ではないなと思いB以降は戦略的撤退をした。
0日目(準備/睡眠フェイズ)
オンサイト経験が少ないので、何を準備すればよいのか戸惑っていた。
あと交通費の紙を書こうとしたところ、「交通費は自宅と会場の往復分を上限」云々という記述を見つけ、1日目で一旦自宅に帰る人はどうするの?ってなった。
とりあえず1往復分のみ記載して、翌日某社の人に直接聞くことに。
1日目
起床フェイズ
普段朝弱いのに、こういう時はサッと起きれる不思議。
移動フェイズ
10時過ぎに会場に着けるように自宅を出発。
ほとんど予定通りに六本木一丁目駅に到着。
駅から会場までも、こどふぇ 2014パーカーの人の後ろをつけていったので迷うことなく会場入り。
準備フェイズ
受付と諸準備を済ませて、会場の写真を撮り終えてからTシャツとリストバンドを貰いにいった。
リストバンドは赤を選んでしまったので、人権を失いました。
本戦
パーカーは5問ということで、ちょっと頑張るかーってなった。
あと、去年はFA賞とLA賞があったぽい(?)ので、B問題でFAを、A問題でLAを狙う作戦にした。
B問題は、2分14秒でAC。これはFA賞貰ったでしょと思ったら128番の人も2分14秒でACしていて、コンマ秒での戦いの末2番手という悔しい結果になりました。
A問題に関しては残り2分で提出して無事LAだったものの、LA賞なんてなかったというね(´・ω・`)
他はC問題のみACで3完197位(198位中)でした。
パーカーもらうためにC問題終わってからずっとE問題解いていたのだけど、テストケースが1つだけACしなくてそのまま時間が過ぎてしまいました。
D問題は解説中に解いてACしました。
本選解説
かなり飛ばし気味の解説だった。
F問題以降は問題文読めてなかったので後日スライドを確認することにして、D問題解いてた。
自由時間
私が参加したのは、
- チームUnagiのトークライブ
- 秋葉さんのトークライブ
- エキシビションマッチの観戦
でした。
両トークライブとも面白い内容でしたが、もう1つのブースのトークライブも聞きたかったですね。
あと、この日はゲーム系のブースに全く参加できなかったのが心残りでした。
帰宅フェイズ
チームリレーの組み分けは04でした。
メンバーにフォロワーさんとか、他にもTwitter上でみたことのある人がいて少しテンションが上がりました。
その後、1時間半ほどかけて自宅へ。
2日目
朝プロ
Easyに参加。
ABは普通に解けたものの、C問題でソートが上手くいかず2完。
終了後、qsort()を使っていたところをsort()とreverse()に変えたら何の問題もなくACして真顔になった。
D問題は完全に知識不足。要練習。
自由時間
2日目はスタンプ目的で、色んなブースに顔を出した。
書道コーディングは、C++のソースコードをバイナリエディタで表示したものを書きました。
THANKSの時の様に、普通に書道すればと今になって後悔中。
音ゲーは嗜んでいないため、残念ながら簡単な譜面でもCOMBOが途切れてしまった。
それでも、面白かったしやってよかった。
chokudaiさんのトークライブは得られることが多くてとてもためになった。
やっぱり基本的なアルゴリズムの知識不足を痛感させられた。
時間が足りなかったし、一緒にやる人もいなかったので、ボードゲームをやれなかったのが残念でした。
来年本戦行けたらやりたいと思います。
チーム対抗リレー
この2日間で自分の実力不足を酷く痛感させられたので、足を引っ張らないかびくびくしてた。
私はA問題を担当した。リレー開始とともにコーディング場所に行って、そこで問題確認しコーディングした。
結果が全て一緒になるということに気づかずforループで結果を出すというクソ面倒なことをしてしまった。
緊張してたとはいえさすがに気付けないといけなかったと思うので、反省。
あとはF問題の図形を探すのを手伝ったりしました。
大学内に競プロについて話せる人がいないので、こうやって他の人と協力して問題に取り組むことは今までに経験が無かったのでとても楽しかったです。
ただ、G問題以降は全く役に立てなかったのでもっと頑張らないとなーって思いました。
ハッピーアワー
チームメンバーとの交流時間。
ハッピーアワー始まるまでの休憩時間に皆で十分盛り上がってたので、ハッピーアワーは表彰式に等価でした。
帰宅フェイズ
帰り際、秋葉さんに蟻本へサインをお願いしました。
去年のTHANKSでchokudaiさんからサインを書いてもらった蟻本ですが、ようやく本当の著者にサインをもらうことに成功しました。
社交辞令とはいえ、これからも頑張って下さいと言われたので頑張りたいと思います╭( ・ㅂ・)و ̑̑ グッ !
総括
とにかく自分の実力不足に嘆く2日間になってしまいました。
それでもこの2日間はとても充実した面白いものであったし、本当に参加出来て良かったと思います。
交通費等も全額支給ですし、Tシャツやトートバックも貰ってしまって、某社には頭が上がらないですね。
参加基準も、私程度で参加出来ているのでそう高くはないですし、初心者でも楽しめるコンテンツも多いので、競プロに少しでも興味がある人は来年の予選に挑戦してほしいと思います。
私自身も来年も本戦に参加できるように精進したいと思います。
CODE THANKS FESTIVAL B日程参加しました
※ブログを書くのは初めてなので、文章構成等雑ですがご容赦ください。
※気付いたらめちゃ長い&画像多くなってしまいました。適当に読み飛ばしてください。
自己紹介
横浜国立大学 理工学部 数物・電子情報系学科 電子情報システムEPに所属しています。
横国には情報工学EPなるものが存在してるので、電子情報という名前ですが、ほぼ電子電気系の勉強しかしていないです。
そのため普段はプログラミングはしていないので、日曜大工ならぬ土曜競プロerです。
移動フェイズ
開催地はテレコムセンター コワーキングスペースMONO。
受付が10:30~ということで、10:20前には到着して外で写真を撮ってました。
そして、エレベーターで14階に上がると……
CODE THANKS FESTIVALの看板と、強そうな雰囲気の参加者達がいました。
実は、私はテレコムセンターに行くのは2回目(1回目はCode Formula本選)でしたので、会場にも迷うことなく辿り着けました。
ただ、Code Formulaの時はテレコムセンター駅の改札を出てすくのところに看板と人が立って誘導してたのでだいぶ分かりやすかったですが、CODE THANKS FESTIVALではそういったものあったんですかね?
自分は写真撮るために遠回りしてたので詳しく知らないですけど、参加者の中で数人エレベーターの位置が分からずに苦労してたようですので。
昼食フェイズ
ささっと受付(一番乗りでした)を済ませ た後、色々と貰うものを貰って、いざお昼タイム……とはいかず、やはり写真を撮りまくっていたり、某サイコロ部の方とお話をしていたりしました。
その後ようやく、お昼タイム(主に開会式中に食べてました、ごめんなさい)。
お弁当が4種類ほどありそのうち1つを選ぶ形でしたが、私は迷わず叙々苑焼肉弁当を選びました!
この日はお食事会と、お弁当を食べることが主目的だったので、この時点で4割ほど満足してました。←ォィ
コンテストフェイズ
問題形式等は他の参加者が沢山言及してるので、割愛します。
以下私の方針等をつらつらと書いていきます。
↓問題はこちら↓
Tasks - code thanks festival 2014 B日程 | AtCoder
↓私の解答はこちら↓ (WAとかは恥ずかしいので見ないでください><)
Sign in - code thanks festival 2014 B日程 | AtCoder
A問題
max(a,b)するだけ。
FA狙っていたけど、入出力ミスって(変数宣言はa, bなのに、入出力がA, B……orz)38秒で提出したけれどCEでした。
まぁ、FAの人が32秒ほどで提出していたので、どのみちFAは取れていませんでしたが。
B問題
max(max(max(A + B + C, (A + B)*C), (A*B) + C), A*B*C)するだけ。
C問題
forループでif ((V[i]/2)<F[i]) count++;していくだけ。
chokudaiさんはこの方法だと危ないといっていたけれど、int型なら小数点以下切り捨てなので問題ないのでは?
例えば、V=5, F=3のとき、V/2=2, F=3となるので。
D問題
適当な配列を要素数T+1以上で取っておき、forループでA[i]の定数倍の要素をインクリメントしていき、最後に配列の中で一番大きい数を出力した。
もっと賢いやり方はあるだろうけれど、制約が緩かったので気にせず実装した。
E問題
4方向について全探索するだけ。
A~D問題を解いてる時は大分空気に飲まれていたけれど、この問題を1発(間違って入力例を提出してしまって1回CEはしているがw)で通せた上にこの時点で6~9位くらいだったので、入賞できるのではと思い始めていた。
F問題
dp問題。文字列の比較さえできれば、まぁ普通にいける(?)
自分は最初再帰で解こうとしていたが、途中からforループで解く方針に切り替えた。
この時、再帰関数自体とmain関数内の再帰関数の呼び出しを消し忘れていたため、ずっとTLEになってしまっていた。
そのため、一旦途中で諦めてG問題を解いていた。
再帰関数のことに気づいたのは終了5分前だったので、これに気付けていなかったら、最終順位は20位前後だった。
G問題
こちらもdp問題。
着想までに時間がかかってしまったが、思いついてしまえば実装はさほど難しくない問題。
2人ゲームは割と典型的な問題のようなので、次出てきたら即提出できるようにならなくては。
ペナルティが無いことをいいことに、最初の20分くらいは全部の問題に対してFirstを出力させて解答がどうなっているかのチェックや、N, Pの偶奇によってFirstを出力させたりしてN, Pによって答えが決まる通りがないか(N, Pが共に偶数の時Firstにならないか等)をチェックしていました。
運営側としてはあまりしてほしくない行為ですよね、すみませんでした。
H問題
オイラー路の問題。
時間が無くて、コンテスト中に問題が見れなかった。
私は、木やグラフの問題が苦手なので、これが最後の問題で良かった。
総評
焦ってしまい、しょうもないミスを連発してしまった。
また、コンテスト開始前にお菓子をもっと持ってくるべきだった。
F, Gが通らなくてイライラしていたところに、食べようと手を伸ばしたじゃがりこの箱が空だった時のやるせなさ……Code Formulaの時も似たようなことしてたので、進歩がみられない(^^;)
とは言っても、9位入賞することができたので、概ね満足でした。
1月下旬にある焼肉会が今から楽しみです。
休憩・表彰・解説フェイズ
無事5問以上正解できたので、トートバック貰いました!
A~E問題は全探索まで知ってれば解ける問題だったので、ほぼ全員がトートバック貰えるかなと思っていたけど、51/79人しか500点以上の人いなくてちょっと意外でした。ちなみに、初心者(プロ)のつねならずさん(@tsunenarazu)も500点越えてました。
本当にプログラミング自体初めて数週間ですよね……?
休憩時間の間に、chokudaiさんとツーショット&蟻本にサインを頂きました。
ネタに付き合って頂きありがとうございました。
ちなみに、このために蟻本を購入したのですが、
@"chokudai さんにサイン貰うための蟻本が届いた←作者違うェ……
— toto (@2557_letters) 2014, 12月 11
こんなツイートしたらchokudaiさんご本人に拡散&「著者違うからね」ツイートされましたorz
その後表彰式。
競プロで初めて表彰されました!
参加者のレベルが自分と同じくらいの人だけという条件下なので、自分の実力などプロの方々の足元にも及ばないですが、それでもこういった場で実力が認められたのはとても嬉しく、良い経験ができたなと思ってます。
お食事会フェイズ
そして、本日のメインイベント(プログラミングコンテスト?あれは余興でしょ?) 懇親会の時間となりました。
目の前に現れたのは、肉!寿司!ピザ!
いやー。最高でしょ、これ。
ただ、一言言いたい。
何 故 お 酒 が な い の か !
肉・ピザがあったら、お酒あると思うじゃないですか。
ピザにコークもまぁ定番ですけど、アルコールが欲しかったです、はい。
何はともあれ、懇親会スタートです。
コミュ障の私ですけど、某サイコロ部氏のおかげで、某Phytonの方などとお話できたので良かったです。
(ちなみに、案の定サイコロ部氏が早退した後はあまり話せてません(;´∀`) )
そして、アレです……
始まりはつねならずさんとhyonさん(名前間違ってたらごめんなさい)との会話でした。
書道コーディングの話になり色々と話が弾んだ結果、
実はつねならずさんとの会話の時点では、 class chokudaiにsanagippメソッドがあり、chokudai.sanagippで"LOVE"がreturnされるとかいう話になってた…… #codefes #chokudaiさん #本当にすみませんでした
— toto (@2557_letters) 2014, 12月 14
こんなことを書道コーディングで書いたらどうかと言われ、結局こうなりました。
Twitter上でも、
本日の書道コーディングです。この文字の意味はわかりませんが、綺麗な字だなと思います #codefes pic.twitter.com/1H8mMvIM43
— けんしょー(デコキュート♥️) (@akensho) 2014, 12月 14
など色々と話題にして頂きました。
が、
(元カノで弄るの、ネタになるから程ほどはいいんだけど、実は自分が彼女いるの隠してるだけとかだった場合、すっごい気まずいから、ある程度空気読んでほどほどにしてね!)
— 高橋 直大(chokudai) (@chokudai) 2014, 12月 14
や、
AtCoder ID:letterさんが全て悪い。覚えた。覚えたよ。ちゃんと覚えたよ。
— 高橋 直大(chokudai) (@chokudai) 2014, 12月 14
など、度が過ぎておりました。chokudaiさん誠に申し訳ありませんでした。
そんなこんなあった書道コーディングですが、優秀作品はコード(コンセントを差し込むやつ)を書いた作品でした。
個人的には、
「猫でもわかる」書きました。(ちなみに書道部です) #codefes pic.twitter.com/toe69sYgOQ
— 内海トオカ (@Hacoris_) 2014, 12月 14
副優秀作品に選ばれた「猫でもわかる」を書いた@Hacoris_さんの、
この作品がとても印象深かったです。
また、競プロと親和性の高いとされている音ゲーでは、DDRでおしょーゆさんが、太鼓の達人ではno15_renneさんが優勝しました。
自分は音ゲーは友人に連れられて行った以外は全くしたことがないので、プレイはせず、観戦だけしていました。
自分としてはゲーセンは全く興味ないので、本選へ行けていたとしても音ゲーはやってなかったと思います。
帰宅フェイズ
Code Formulaではそのまま帰宅してしまったことを後悔していたので、お酒も飲んでないし時間もまだ早かったので、お台場を散策してから帰りました。
夜のお台場です。 #codefes pic.twitter.com/WVRMZxSEOP
— toto (@2557_letters) 2014, 12月 14
綺麗な夜景を見れましたが、 カップルが沢山いて心の中で呪詛を唱えまくっていました。
総括
14日の目標として、
・つねならずさんからのハラスメント回避
・10位(できれば5位)以内入賞
・FA賞
を挙げていました。
9位入賞は果たしたものの、FA賞は全く取れなかったので残念でした。
今後も少しずつ実力を付けていきたいと思います。
また、今回はこんなにも素晴らしいコンテストを開催して頂き、更には焼肉にも招待して頂き、リクルートさんにはとても感謝をしています。
ありがとうございました。
おまけ
ちなみに、書道コーディング用では元々下の写真のを書く予定でした。
この写真のやつは、前日に家で筆ペンで書いたものです。
当日も持ってきていて、これを見ながら筆で清書するつもりでした。
結局書いたのは、"沙凪"と、"高度"(Code→コード→こうど→高度)というね……